प्रतिस्थापन (तर्क)

एक प्रतिस्थापन औपचारिक भाषा के भावों पर एक वाक्य रचना (तर्क) परिवर्तन है।

किसी अभिव्यक्ति (गणित) के लिए प्रतिस्थापन प्रायुक्त करने का अर्थ है उसके चर या प्लेसहोल्डर प्रतीकों को लगातार अन्य व्यंजकों से बदलना।

परिणामी अभिव्यक्ति को मूल अभिव्यक्ति का प्रतिस्थापन उदाहरण या संक्षेप में उदाहरण कहा जाता है।

प्रस्तावपरक तर्क

परिभाषा

जहां ψ और φ प्रस्तावात्मक तर्क के अच्छे प्रकार से गठित सूत्रों का प्रतिनिधित्व करते हैं, ψ φ का एक प्रतिस्थापन उदाहरण है यदि और केवल यदि φ को φ में प्रतीकों के लिए सूत्रों को प्रतिस्थापित करके प्राप्त किया जा सकता है, उसी प्रतीक की प्रत्येक घटना को उसी सूत्र की घटना से प्रतिस्थापित किया जा सकता है। उदाहरण के लिए:

(R → S) & (T → S)

का एक प्रतिस्थापन उदाहरण है:

P & Q

और

(A ↔ A) ↔ (A ↔ A)

का एक प्रतिस्थापन उदाहरण है:

(A ↔ A)

प्रस्तावपरक तर्क के लिए कुछ कटौती प्रणालियों में, व्युत्पत्ति की एक पंक्ति पर एक नई अभिव्यक्ति (एक प्रस्ताव) दर्ज किया जा सकता है यदि यह व्युत्पत्ति की पिछली पंक्ति का प्रतिस्थापन उदाहरण है (हंटर 1971, पृष्ठ 118)। कुछ स्वयंसिद्ध प्रणालियों में इस प्रकार नई लाइनें पेश की जाती हैं। उन प्रणालियों में जो अनुमान के नियम का उपयोग करते हैं, एक नियम में व्युत्पत्ति में कुछ चरों को प्रस्तुत करने के उद्देश्य से एक प्रतिस्थापन उदाहरण का उपयोग शामिल हो सकता है।

पहले क्रम के तर्क में, हर जमीनी अभिव्यक्ति जिसे प्रतिस्थापन द्वारा एक खुले प्रस्तावक सूत्र φ से प्राप्त किया जा सकता है, को φ का प्रतिस्थापन उदाहरण कहा जाता है। यदि φ एक बंद प्रस्ताव सूत्र है तो हम φ को ही इसके एकमात्र प्रतिस्थापन उदाहरण के रूप में गिनते हैं।

टॉटोलॉजी

एक प्रस्तावपरक सूत्र एक तनातनी (तर्क) है यदि यह उसके विधेय प्रतीकों के प्रत्येक मूल्यांकन (तर्क) (या व्याख्या (तर्क)) के तहत सही है। यदि Φ एक तनातनी है, और Θ Φ का प्रतिस्थापन उदाहरण है, तो Θ फिर से एक तनातनी है। यह तथ्य पिछले खंड में वर्णित कटौती नियम की सुदृढ़ता का तात्पर्य है।

प्रथम क्रम तर्क

पहले क्रम के तर्क में, एक प्रतिस्थापन कुल मानचित्रण है σ: V → T पद (तर्क) से # औपचारिक परिभाषा से पद (तर्क); अनेक,^[1]^: 73^[2]^: 445 लेकिन सब नहीं^[3]^: 250 लेखकों को अतिरिक्त रूप से σ (x) = x की आवश्यकता होती है, लेकिन बहुत सारे चर x के लिए। अंकन { एक्स₁↦ टी₁, …, एक्स_k↦ टी_k }^{[note 1]} प्रत्येक चर x के प्रतिस्थापन मानचित्रण को संदर्भित करता है_i इसी अवधि के लिए टी_i, i=1,…,k, और हर दूसरे चर के लिए; एक्स_i जोड़ीदार अलग होना चाहिए। उस प्रतिस्थापन को एक शब्द t पर प्रायुक्त करना पोस्टफिक्स नोटेशन में t { x के रूप में लिखा गया है₁↦ टी₁, ..., एक्स_k↦ टी_k }; इसका अर्थ है (एक साथ) प्रत्येक x की प्रत्येक घटना को प्रतिस्थापित करना_i टी द्वारा टी में_i.^{[note 2]} किसी पद t पर प्रतिस्थापन σ प्रायुक्त करने के परिणाम tσ को उस पद t का उदाहरण कहा जाता है। उदाहरण के लिए, शब्द में प्रतिस्थापन { x ↦ z, z ↦ h(a,y) } प्रायुक्त करना

f(	z	, a, g(	x	), y)	yields
f(	h(a,y)	, a, g(	z	), y)	.

एक प्रतिस्थापन σ के डोमेन डोम (σ) को आमतौर पर वास्तव में प्रतिस्थापित चर के सेट के रूप में परिभाषित किया जाता है, अर्थात डोम (σ) = { x ∈ V | xσ ≠ x }. एक प्रतिस्थापन को ग्राउंड प्रतिस्थापन कहा जाता है यदि यह अपने डोमेन के सभी चर को शब्द (तर्क) # ग्राउंड और रैखिक शर्तों, यानी चर-मुक्त, शब्दों में मैप करता है। एक जमीनी प्रतिस्थापन का प्रतिस्थापन उदाहरण tσ एक बुनियादी शब्द है यदि सभी t's चर σ में हैं's डोमेन, यानी यदि var(t) ⊆ dom(σ). एक प्रतिस्थापन σ को एक रैखिक प्रतिस्थापन कहा जाता है यदि tσ एक शब्द (तर्क) # ग्राउंड और कुछ (और इसलिए प्रत्येक) रैखिक शब्द टी के लिए रैखिक शब्द शब्द है जिसमें ठीक से σ के चर होते हैं's डोमेन, यानी vars(t) = dom(σ) के साथ। एक प्रतिस्थापन σ को समतल प्रतिस्थापन कहा जाता है यदि xσ प्रत्येक चर x के लिए एक चर है। एक प्रतिस्थापन σ को पुनर्नामित प्रतिस्थापन कहा जाता है यदि यह सभी चरों के सेट पर समूह सिद्धांत में क्रमचय # क्रमपरिवर्तन है। हर क्रमचय की तरह, नाम बदलने वाले प्रतिस्थापन σ का हमेशा एक व्युत्क्रम प्रतिस्थापन σ होता है⁻¹, जैसे कि tσσ^{−1</सुप> = टी = टीσ⁻¹σ प्रत्येक पद t के लिए। हालांकि, मनमाने प्रतिस्थापन के लिए व्युत्क्रम को परिभाषित करना संभव नहीं है।}

उदाहरण के लिए, { x ↦ 2, y ↦ 3+4} एक ग्राउंड प्रतिस्थापन है, { x ↦ x₁, और ↦ और₂+4} गैर-जमीनी और गैर-समतल है, लेकिन रैखिक है, { एक्स ↦ वाई₂, और ↦ और₂+4 } गैर-रैखिक और गैर-फ्लैट है, { x ↦ y₂, और ↦ और₂ } सपाट है, लेकिन गैर-रैखिक है, { x ↦ x₁, और ↦ और₂ } रेखीय और सपाट दोनों है, लेकिन नाम बदलने वाला नहीं है, क्योंकि मानचित्र y और y दोनों हैं₂ यह वाई है₂; इनमें से प्रत्येक प्रतिस्थापन में {x, y} को इसके डोमेन के रूप में सेट किया गया है। नाम बदलने के प्रतिस्थापन का एक उदाहरण { x ↦ x है₁, एक्स₁↦ और, और ↦ और₂, और₂↦ x}, इसका व्युत्क्रम {x ↦ y है₂, और₂↦ वाई, वाई ↦ एक्स₁, एक्स₁↦ एक्स}। समतल प्रतिस्थापन { x ↦ z, y ↦ z } का व्युत्क्रम नहीं हो सकता, क्योंकि उदा. (x+y) { x ↦ z, y ↦ z } = z+z, और बाद वाले शब्द को वापस x+y में रूपांतरित नहीं किया जा सकता है, क्योंकि मूल az के बारे में जानकारी खो जाती है। भूमि प्रतिस्थापन { x ↦ 2 } का व्युत्क्रम नहीं हो सकता है क्योंकि मूल सूचना का एक समान नुकसान होता है उदा. in (x+2) { x ↦ 2 } = 2+2, भले ही चरों द्वारा स्थिरांकों को प्रतिस्थापित करने की अनुमति कुछ काल्पनिक प्रकार के सामान्यीकृत प्रतिस्थापनों द्वारा दी गई थी।

दो प्रतिस्थापनों को समान माना जाता है यदि वे प्रत्येक चर को शब्द (तर्क) # संरचनात्मक समानता परिणाम शर्तों के लिए मैप करते हैं, औपचारिक रूप से: σ = τ यदि xσ = xτ प्रत्येक चर x ∈ V के लिए। दो प्रतिस्थापन की संरचना σ = { x₁↦ टी₁, …, एक्स_k↦ टी_k } और τ = { y₁↦ में₁, …, और_l↦ में_l } प्रतिस्थापन {x से हटाकर प्राप्त किया जाता है₁↦ टी₁टी, …, एक्स_k↦ टी_kटी, वाई₁↦ में₁, …, और_l↦ में_l } वे जोड़े y_i↦ में_i जिसके लिए वाई_i ∈ { एक्स₁, …, एक्स_k }. σ और τ की संरचना को στ द्वारा निरूपित किया जाता है। रचना एक साहचर्य संक्रिया है, और प्रतिस्थापन अनुप्रयोग के साथ संगत है, अर्थात (ρσ)τ = ρ(στ), और (tσ)τ = t(στ), प्रत्येक प्रतिस्थापन ρ, σ, τ, और प्रत्येक पद t के लिए क्रमशः . पहचान प्रतिस्थापन, जो प्रत्येक चर को अपने आप में मैप करता है, प्रतिस्थापन संरचना का तटस्थ तत्व है। एक प्रतिस्थापन σ को idempotent कहा जाता है यदि σσ = σ, और इसलिए प्रत्येक पद t के लिए tσσ = tσ। प्रतिस्थापन { एक्स₁↦ टी₁, …, एक्स_k↦ टी_k } idempotent है यदि और केवल यदि कोई भी चर x नहीं है_i किसी भी टी में होता है_i. प्रतिस्थापन संरचना क्रमविनिमेय नहीं है, अर्थात, στ τσ से भिन्न हो सकता है, भले ही σ और τ उदासीन हों।^[1]^: 73–74^[2]^{: 445–446}

उदाहरण के लिए, { x ↦ 2, y ↦ 3+4} {y ↦ 3+4, x ↦ 2} के बराबर है, लेकिन { x ↦ 2, y ↦ 7} से अलग है। प्रतिस्थापन { x ↦ y+y } उदासीन है, उदा. ((x+y) {x↦y+y}) {x↦y+y} = ((y+y)+y) {x↦y+y} = (y+y)+y, जबकि प्रतिस्थापन { x ↦ x+y } गैर-उदासीन है, उदा. ((x+y) {x↦x+y}) {x↦x+y} = ((x+y)+y) {x↦x+y} = ((x+y)+y)+y . गैर-कम्यूटिंग प्रतिस्थापन के लिए एक उदाहरण है { x ↦ y } {y ↦ z } = { x ↦ z, y ↦ z}, लेकिन { y ↦ z} { x ↦ y} = { x ↦ y, y ↦ z} .

बीजगणित

प्रतिस्थापन बीजगणित में एक बुनियादी संक्रिया है, विशेष रूप से कंप्यूटर बीजगणित में।^[4]^[5] प्रतिस्थापन के एक सामान्य मामले में बहुपद शामिल होते हैं, जहां एक अविभाज्य बहुपद के अनिश्चित के लिए एक संख्यात्मक मान (या अन्य अभिव्यक्ति) का प्रतिस्थापन उस मूल्य पर बहुपद का मूल्यांकन करने के लिए होता है। वास्तव में, यह संक्रिया इतनी बार-बार होती है कि बहुपदों के लिए अंकन अक्सर इसके अनुकूल हो जाता है; पी जैसे नाम से एक बहुपद को नामित करने के बजाय, जैसा कि कोई अन्य गणितीय वस्तुओं के लिए करेगा, कोई भी परिभाषित कर सकता है

P(X)=X^{5}-3X^{2}+5X-17

ताकि X के लिए प्रतिस्थापन P(X) के अंदर प्रतिस्थापन द्वारा नामित किया जा सके, कहें

P(2)=13

या

P(X+1)=X^{5}+5X^{4}+10X^{3}+7X^{2}+4X-14.

प्रतिस्थापन को प्रतीकों से निर्मित अन्य प्रकार की औपचारिक वस्तुओं पर भी प्रायुक्त किया जा सकता है, उदाहरण के लिए मुक्त समूहों के तत्व। प्रतिस्थापन को परिभाषित करने के लिए, एक उपयुक्त सार्वभौमिक संपत्ति के साथ एक बीजगणितीय संरचना की आवश्यकता होती है, जो अद्वितीय समरूपता के अस्तित्व पर जोर देती है जो विशिष्ट मानों को अनिश्चित भेजती है; प्रतिस्थापन तब ऐसी समरूपता के तहत छवि को खोजने के लिए होता है।

प्रतिस्थापन संबंधित है, लेकिन फ़ंक्शन संरचना के समान नहीं है; यह लैम्ब्डा कैलकुस में β-कमी से निकटता से संबंधित है। इन धारणाओं के विपरीत, हालांकि, बीजगणित में जोर प्रतिस्थापन संचालन द्वारा बीजगणितीय संरचना के संरक्षण पर है, तथ्य यह है कि प्रतिस्थापन हाथ में संरचना के लिए एक समरूपता देता है (बहुपदों के मामले में, अंगूठी (गणित) संरचना) .^{[citation needed]}

यह भी देखें

समानता में प्रतिस्थापन संपत्ति (गणित)#समानता के कुछ बुनियादी तार्किक गुण
पहले क्रम का तर्क#अनुमान के नियम
सार्वभौमिक तात्कालिकता
लैम्ब्डा कैलकुस # प्रतिस्थापन
सत्य-मूल्य शब्दार्थ
एकीकरण (कंप्यूटर विज्ञान)
मेटावैरिएबल
यथोचित परिवर्तन सहित
प्रतिस्थापन का नियम
स्ट्रिंग प्रक्षेप - जैसा कि कंप्यूटर प्रोग्रामिंग में देखा गया है
प्रतिस्थापन द्वारा एकीकरण
त्रिकोणमितीय प्रतिस्थापन

↑ Some authors use [ t₁/x₁, …, t_k/x_k ] to denote that substitution, e.g. M. Wirsing (1990). Jan van Leeuwen (ed.). Algebraic Specification. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 675–788., here: p. 682.
↑ From a term algebra point of view, the set T of terms is the free term algebra over the set V of variables, hence for each substitution mapping σ: V → T there is a unique homomorphism σ: T → T that agrees with σ on V ⊆ T; the above-defined application of σ to a term t is then viewed as applying the function σ to the argument t.

उद्धरण

↑ ^1.0 ^1.1 David A. Duffy (1991). स्वचालित प्रमेय साबित करने के सिद्धांत. Wiley.
↑ ^2.0 ^2.1 Franz Baader, Wayne Snyder (2001). Alan Robinson and Andrei Voronkov (ed.). एकीकरण सिद्धांत (PDF). Elsevier. pp. 439–526.
↑ N. Dershowitz; J.-P. Jouannaud (1990). "Rewrite Systems". In Jan van Leeuwen (ed.). औपचारिक मॉडल और शब्दार्थ. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 243–320.
↑ Margret H. Hoft; Hartmut F.W. Hoft (6 November 2002). गणित के साथ कम्प्यूटिंग. Elsevier. ISBN 978-0-08-048855-4.
↑ Andre Heck (6 December 2012). मेपल का परिचय. Springer Science & Business Media. ISBN 978-1-4684-0484-5. प्रतिस्थापन।

संदर्भ

Crabbé, M. (2004). On the Notion of Substitution. Logic Journal of the IGPL, 12, 111–124.
Curry, H. B. (1952) On the definition of substitution, replacement and allied notions in an abstract formal system. Revue philosophique de Louvain 50, 251–269.
Hunter, G. (1971). Metalogic: An Introduction to the Metatheory of Standard First Order Logic. University of California Press. ISBN 0-520-01822-2
Kleene, S. C. (1967). Mathematical Logic. Reprinted 2002, Dover. ISBN 0-486-42533-9

बाहरी संबंध

Substitution in nLab

[4] Some authors use [ t₁/x₁, …, t_k/x_k ] to denote that substitution, e.g. M. Wirsing (1990). Jan van Leeuwen (ed.). Algebraic Specification. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 675–788., here: p. 682.

[5] From a term algebra point of view, the set T of terms is the free term algebra over the set V of variables, hence for each substitution mapping σ: V → T there is a unique homomorphism σ: T → T that agrees with σ on V ⊆ T; the above-defined application of σ to a term t is then viewed as applying the function σ to the argument t.

[Duffy.1991-1] 1.0 ^1.1 David A. Duffy (1991). स्वचालित प्रमेय साबित करने के सिद्धांत. Wiley.

[Baader.Snyder.2001-2] 2.0 ^2.1 Franz Baader, Wayne Snyder (2001). Alan Robinson and Andrei Voronkov (ed.). एकीकरण सिद्धांत (PDF). Elsevier. pp. 439–526.

[Dershowitz.Jouannaud.1990-3] N. Dershowitz; J.-P. Jouannaud (1990). "Rewrite Systems". In Jan van Leeuwen (ed.). औपचारिक मॉडल और शब्दार्थ. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 243–320.

[HoftHoft2002-6] Margret H. Hoft; Hartmut F.W. Hoft (6 November 2002). गणित के साथ कम्प्यूटिंग. Elsevier. ISBN 978-0-08-048855-4.

[HECK2012-7] Andre Heck (6 December 2012). मेपल का परिचय. Springer Science & Business Media. ISBN 978-1-4684-0484-5. प्रतिस्थापन।

[1]

[2]

[3]

[note 1]

[note 2]

[4]

[5]