प्रतिस्थापन (तर्क): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 29: Line 29:
== प्रथम क्रम तर्क ==
== प्रथम क्रम तर्क ==


पहले क्रम के तर्क में, एक प्रतिस्थापन कुल माप है  {{nowrap|''σ'': ''V'' → ''T''}} पद (तर्क) से कई शब्दों तक<ref name="Duffy.1991"/>{{rp|73}}<ref name="Baader.Snyder.2001"/>{{rp|445}} लेकिन सब नहीं<ref name="Dershowitz.Jouannaud.1990">{{cite book | author1=N. Dershowitz |author2= J.-P. Jouannaud | contribution=Rewrite Systems | pages=243–320 | editor=Jan van Leeuwen | title=औपचारिक मॉडल और शब्दार्थ| publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990}}</ref>{{rp|250}} लेखकों को अतिरिक्त रूप से σ (x) = x सभी के लिए लेकिन बहुत से चर x की आवश्यकता होती है। संकेतन { x<sub>1</sub>↦ t<sub>1</sub>, …, x<sub>''k''</sub>↦ t<sub>''k''</sub> }<ref group=note>Some authors use [ ''t''<sub>1</sub>/''x''<sub>1</sub>, …, ''t''<sub>''k''</sub>/''x''<sub>''k''</sub> ] to denote that substitution, e.g. {{cite book| author=M. Wirsing| title=Algebraic Specification| year=1990| volume=B| pages=675–788| publisher=Elsevier| editor=Jan van Leeuwen| series=Handbook of Theoretical Computer Science}}, here: p. 682.</ref>
पहले क्रम के तर्क में, एक प्रतिस्थापन कुल माप है  {{nowrap|''σ'': ''V'' → ''T''}} पद (तर्क) से कई शब्दों तक<ref name="Duffy.1991"/>{{rp|73}}<ref name="Baader.Snyder.2001"/>{{rp|445}} किन्तु सब नहीं<ref name="Dershowitz.Jouannaud.1990">{{cite book | author1=N. Dershowitz |author2= J.-P. Jouannaud | contribution=Rewrite Systems | pages=243–320 | editor=Jan van Leeuwen | title=औपचारिक मॉडल और शब्दार्थ| publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990}}</ref>{{rp|250}} लेखकों को अतिरिक्त रूप से σ (x) = x सभी के लिए किन्तु बहुत से चर x की आवश्यकता होती है। संकेतन { x<sub>1</sub>↦ t<sub>1</sub>, …, x<sub>''k''</sub>↦ t<sub>''k''</sub> }<ref group=note>Some authors use [ ''t''<sub>1</sub>/''x''<sub>1</sub>, …, ''t''<sub>''k''</sub>/''x''<sub>''k''</sub> ] to denote that substitution, e.g. {{cite book| author=M. Wirsing| title=Algebraic Specification| year=1990| volume=B| pages=675–788| publisher=Elsevier| editor=Jan van Leeuwen| series=Handbook of Theoretical Computer Science}}, here: p. 682.</ref>


प्रत्येक चर x<sub>''i''</sub> के प्रतिस्थापन मानचित्रण को संदर्भित करता है इसी अवधि के लिए t<sub>''i''</sub>, i=1,…,k, और हर दूसरे चर के लिए; x<sub>''i''</sub> जोड़ीदार अलग होना चाहिए। उस प्रतिस्थापन को एक शब्द t पर प्रायुक्त करना [[पोस्टफिक्स नोटेशन]] में t { x<sub>1</sub>↦ t<sub>1</sub>, ..., x<sub>''k''</sub>↦ t<sub>''k''</sub> के रूप में लिखा गया हैं}; इसका अर्थ है (एक साथ) प्रत्येक x<sub>''i''</sub> t द्वारा t<sub>''i''</sub> में की प्रत्येक घटना को प्रतिस्थापित करना है।<ref group="note">From a [[term algebra]] point of view, the set ''T'' of terms is the [[Free object#Definition|free term algebra]] over the set ''V'' of variables, hence for each substitution mapping σ: ''V'' → ''T'' there is a unique [[Universal algebra#Basic constructions|homomorphism]] {{overline|σ}}: ''T'' → ''T'' that agrees with σ on ''V'' ⊆ ''T''; the above-defined application of ''σ'' to a term ''t'' is then viewed as applying the function {{overline|''σ''}} to the argument ''t''.</ref> किसी पद t पर प्रतिस्थापन σ प्रायुक्त करने के परिणाम tσ को उस पद t का उदाहरण कहा जाता है।
प्रत्येक चर x<sub>''i''</sub> के प्रतिस्थापन मानचित्रण को संदर्भित करता है इसी अवधि के लिए t<sub>''i''</sub>, i=1,…,k, और हर दूसरे चर के लिए; x<sub>''i''</sub> जोड़ीदार अलग होना चाहिए। उस प्रतिस्थापन को एक शब्द t पर प्रायुक्त करना [[पोस्टफिक्स नोटेशन]] में t { x<sub>1</sub>↦ t<sub>1</sub>, ..., x<sub>''k''</sub>↦ t<sub>''k''</sub> के रूप में लिखा गया हैं}; इसका अर्थ है (एक साथ) प्रत्येक x<sub>''i''</sub> t द्वारा t<sub>''i''</sub> में की प्रत्येक घटना को प्रतिस्थापित करना है।<ref group="note">From a [[term algebra]] point of view, the set ''T'' of terms is the [[Free object#Definition|free term algebra]] over the set ''V'' of variables, hence for each substitution mapping σ: ''V'' → ''T'' there is a unique [[Universal algebra#Basic constructions|homomorphism]] {{overline|σ}}: ''T'' → ''T'' that agrees with σ on ''V'' ⊆ ''T''; the above-defined application of ''σ'' to a term ''t'' is then viewed as applying the function {{overline|''σ''}} to the argument ''t''.</ref> किसी पद t पर प्रतिस्थापन σ प्रायुक्त करने के परिणाम tσ को उस पद t का उदाहरण कहा जाता है।
Line 50: Line 50:
|| .
|| .
|}
|}
एक प्रतिस्थापन σ के डोमेन डोम (σ) को सामान्यतः वास्तव में प्रतिस्थापित चर के सेट के रूप में परिभाषित किया जाता है, अर्थात डोम (σ) = { x ∈ V | xσ ≠ x }.
एक प्रतिस्थापन σ के डोमेन डोम (σ) को सामान्यतः वास्तविक में प्रतिस्थापित चर के सेट के रूप में परिभाषित किया जाता है, अर्थात डोम (σ) = { x ∈ V | xσ ≠ x }.


एक प्रतिस्थापन को ग्राउंड प्रतिस्थापन कहा जाता है यदि यह अपने डोमेन के सभी चर को शब्द (तर्क) ग्राउंड और रैखिक शर्तों, अर्थात् चर-मुक्त, शब्दों में मैप करता है।
एक प्रतिस्थापन को ग्राउंड प्रतिस्थापन कहा जाता है यदि यह अपने डोमेन के सभी चर को शब्द (तर्क) ग्राउंड और रैखिक शर्तों, अर्थात् चर-मुक्त, शब्दों में मैप करता है।
Line 62: Line 62:
एक प्रतिस्थापन σ को पुनर्नामित प्रतिस्थापन कहा जाता है यदि यह सभी चरों के सेट पर समूह सिद्धांत में क्रमचय क्रमपरिवर्तन है। हर क्रमचय की तरह, नाम बदलने वाले प्रतिस्थापन σ का हमेशा एक व्युत्क्रम प्रतिस्थापन σ<sup>−1</sup> होता है, जैसे कि tσσ<sup>−1</sup> = t = tσ<sup>−1</sup>σ प्रत्येक पद t के लिए। चूंकि, स्वैच्छिक प्रतिस्थापन के लिए व्युत्क्रम को परिभाषित करना संभव नहीं है।
एक प्रतिस्थापन σ को पुनर्नामित प्रतिस्थापन कहा जाता है यदि यह सभी चरों के सेट पर समूह सिद्धांत में क्रमचय क्रमपरिवर्तन है। हर क्रमचय की तरह, नाम बदलने वाले प्रतिस्थापन σ का हमेशा एक व्युत्क्रम प्रतिस्थापन σ<sup>−1</sup> होता है, जैसे कि tσσ<sup>−1</sup> = t = tσ<sup>−1</sup>σ प्रत्येक पद t के लिए। चूंकि, स्वैच्छिक प्रतिस्थापन के लिए व्युत्क्रम को परिभाषित करना संभव नहीं है।


उदाहरण के लिए, { x ↦ 2, y ↦ 3+4 } एक ग्राउंड प्रतिस्थापन है, { x ↦ X<sub>1</sub>, y ↦ y<sub>2</sub>+4 } नॉन-ग्राउंड और गैर-समतल, लेकिन रैखिक, { x ↦ y<sub>2</sub>, y ↦ y<sub>2</sub> +4} गैर-रेखीय और गैर-समतल है, {x ↦ y<sub>2</sub>, y ↦ y<sub>2</sub>} समतल है, लेकिन गैर-रैखिक है, { x ↦ X<sub>1</sub>, y ↦ y<sub>2</sub>} रैखिक और सपाट दोनों है, लेकिन नामकरण नहीं, क्योंकि मानचित्र y और y<sub>2</sub> से y<sub>2</sub> दोनों हैं; इनमें से प्रत्येक प्रतिस्थापन में {x, y} को इसके डोमेन के रूप में सेट किया गया है। पुनर्नामकरण प्रतिस्थापन के लिए एक उदाहरण {x ↦ X<sub>1</sub>, X<sub>1</sub> ↦ y, y ↦ y<sub>2</sub>, y<sub>2</sub> ↦ x} है, इसका व्युत्क्रम {x ↦ y<sub>2</sub>, y<sub>2</sub> ↦ y, y ↦ X<sub>1</sub>, x<sub>1</sub> ↦ x} है। समतल प्रतिस्थापन { 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 ↦ 2, y ↦ 3+4 } एक ग्राउंड प्रतिस्थापन है, { x ↦ X<sub>1</sub>, y ↦ y<sub>2</sub>+4 } नॉन-ग्राउंड और गैर-समतल, किन्तु रैखिक, { x ↦ y<sub>2</sub>, y ↦ y<sub>2</sub> +4} गैर-रेखीय और गैर-समतल है, {x ↦ y<sub>2</sub>, y ↦ y<sub>2</sub>} समतल है, किन्तु गैर-रैखिक है, { x ↦ X<sub>1</sub>, y ↦ y<sub>2</sub>} रैखिक और सपाट दोनों है, किन्तु नामकरण नहीं, क्योंकि मानचित्र y और y<sub>2</sub> से y<sub>2</sub> दोनों हैं; इनमें से प्रत्येक प्रतिस्थापन में {x, y} को इसके डोमेन के रूप में सेट किया गया है। पुनर्नामकरण प्रतिस्थापन के लिए एक उदाहरण {x ↦ X<sub>1</sub>, X<sub>1</sub> ↦ y, y ↦ y<sub>2</sub>, y<sub>2</sub> ↦ x} है, इसका व्युत्क्रम {x ↦ y<sub>2</sub>, y<sub>2</sub> ↦ y, y ↦ X<sub>1</sub>, x<sub>1</sub> ↦ x} है। समतल प्रतिस्थापन { 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σ = xτ प्रत्येक चर x ∈ V के लिए मैप करते हैं।
Line 68: Line 68:
दो प्रतिस्थापनों की संरचना σ = { x<sub>1</sub> ↦ t<sub>1</sub>, …, x<sub>k</sub> ↦ t<sub>k</sub> } और τ = { y<sub>1</sub> ↦ u<sub>1</sub>, …, y<sub>l</sub> ↦ u<sub>l</sub> } को प्रतिस्थापन से हटाकर प्राप्त किया जाता है { x<sub>1</sub> ↦ t<sub>1</sub>τ, …, x<sub>k</sub> ↦ t<sub>k</sub>τ, y<sub>1</sub> ↦ u<sub>1</sub>, …, y<sub>l</sub> ↦ u<sub>l</sub> } उन युग्मों y<sub>i</sub> ↦ u<sub>i</sub> जिनके लिए y<sub>i</sub> ∈ { x<sub>1</sub>, …, x<sub>k</sub>}। σ और τ की संरचना को στ द्वारा निरूपित किया जाता है। रचना एक साहचर्य संक्रिया है, और प्रतिस्थापन अनुप्रयोग के साथ संगत है अर्थात (ρσ)τ = ρ(στ) और (tσ)τ = t(στ) प्रत्येक प्रतिस्थापन ρ, σ, τ, और प्रत्येक शब्द t के लिए क्रमशः। पहचान प्रतिस्थापन, जो प्रत्येक चर को अपने आप में मैप करता है, प्रतिस्थापन संरचना का तटस्थ तत्व है। एक प्रतिस्थापन σ को idempotent कहा जाता है यदि σσ = σ, और इसलिए प्रत्येक पद t के लिए tσσ = tσ। प्रतिस्थापन { x<sub>1</sub> ↦ t<sub>1</sub>, …, x<sub>k</sub> ↦ t<sub>k</sub> } उदासीन है यदि और केवल यदि कोई भी चर x<sub>i</sub> किसी भी t<sub>i</sub> में नहीं होता है। प्रतिस्थापन संरचना क्रमविनिमेय नहीं है, अर्थात, στ, τσ से भिन्न हो सकता है, तथापि σ और τ उदासीन हों।<ref name="Duffy.1991">{{cite book| author=David A. Duffy| title=स्वचालित प्रमेय साबित करने के सिद्धांत| year=1991| publisher=Wiley}}</ref>{{rp|73–74}}<ref name="Baader.Snyder.2001">{{cite book| author=[[Franz Baader]], [[Wayne Snyder]]| title=एकीकरण सिद्धांत| year=2001| pages=439–526| publisher=Elsevier| editor=[[John Alan Robinson|Alan Robinson]] and [[Andrei Voronkov]] |url=http://www.cs.bu.edu/~snyder/publications/UnifChapter.pdf}}</ref>{{rp|445–446}}
दो प्रतिस्थापनों की संरचना σ = { x<sub>1</sub> ↦ t<sub>1</sub>, …, x<sub>k</sub> ↦ t<sub>k</sub> } और τ = { y<sub>1</sub> ↦ u<sub>1</sub>, …, y<sub>l</sub> ↦ u<sub>l</sub> } को प्रतिस्थापन से हटाकर प्राप्त किया जाता है { x<sub>1</sub> ↦ t<sub>1</sub>τ, …, x<sub>k</sub> ↦ t<sub>k</sub>τ, y<sub>1</sub> ↦ u<sub>1</sub>, …, y<sub>l</sub> ↦ u<sub>l</sub> } उन युग्मों y<sub>i</sub> ↦ u<sub>i</sub> जिनके लिए y<sub>i</sub> ∈ { x<sub>1</sub>, …, x<sub>k</sub>}। σ और τ की संरचना को στ द्वारा निरूपित किया जाता है। रचना एक साहचर्य संक्रिया है, और प्रतिस्थापन अनुप्रयोग के साथ संगत है अर्थात (ρσ)τ = ρ(στ) और (tσ)τ = t(στ) प्रत्येक प्रतिस्थापन ρ, σ, τ, और प्रत्येक शब्द t के लिए क्रमशः। पहचान प्रतिस्थापन, जो प्रत्येक चर को अपने आप में मैप करता है, प्रतिस्थापन संरचना का तटस्थ तत्व है। एक प्रतिस्थापन σ को idempotent कहा जाता है यदि σσ = σ, और इसलिए प्रत्येक पद t के लिए tσσ = tσ। प्रतिस्थापन { x<sub>1</sub> ↦ t<sub>1</sub>, …, x<sub>k</sub> ↦ t<sub>k</sub> } उदासीन है यदि और केवल यदि कोई भी चर x<sub>i</sub> किसी भी t<sub>i</sub> में नहीं होता है। प्रतिस्थापन संरचना क्रमविनिमेय नहीं है, अर्थात, στ, τσ से भिन्न हो सकता है, तथापि σ और τ उदासीन हों।<ref name="Duffy.1991">{{cite book| author=David A. Duffy| title=स्वचालित प्रमेय साबित करने के सिद्धांत| year=1991| publisher=Wiley}}</ref>{{rp|73–74}}<ref name="Baader.Snyder.2001">{{cite book| author=[[Franz Baader]], [[Wayne Snyder]]| title=एकीकरण सिद्धांत| year=2001| pages=439–526| publisher=Elsevier| editor=[[John Alan Robinson|Alan Robinson]] and [[Andrei Voronkov]] |url=http://www.cs.bu.edu/~snyder/publications/UnifChapter.pdf}}</ref>{{rp|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} है।
उदाहरण के लिए, { 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} है।


== [[बीजगणित]] ==
== [[बीजगणित]] ==


प्रतिस्थापन बीजगणित में एक बुनियादी संक्रिया है, विशेष रूप से [[कंप्यूटर बीजगणित]] में।<ref name="HoftHoft2002">{{cite book|author1=Margret H. Hoft|author2=Hartmut F.W. Hoft|title=गणित के साथ कम्प्यूटिंग|url=https://books.google.com/books?id=5bQRX0w0gtAC&q=substitution|date=6 November 2002|publisher=Elsevier|isbn=978-0-08-048855-4}}</ref><ref name="HECK2012">{{cite book|author=Andre Heck|title=मेपल का परिचय|url=https://archive.org/details/introductiontoma0000heck|url-access=registration|quote=प्रतिस्थापन।|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4684-0484-5}}</ref>
प्रतिस्थापन बीजगणित में एक बुनियादी संक्रिया है, विशेष रूप से [[कंप्यूटर बीजगणित]] में।<ref name="HoftHoft2002">{{cite book|author1=Margret H. Hoft|author2=Hartmut F.W. Hoft|title=गणित के साथ कम्प्यूटिंग|url=https://books.google.com/books?id=5bQRX0w0gtAC&q=substitution|date=6 November 2002|publisher=Elsevier|isbn=978-0-08-048855-4}}</ref><ref name="HECK2012">{{cite book|author=Andre Heck|title=मेपल का परिचय|url=https://archive.org/details/introductiontoma0000heck|url-access=registration|quote=प्रतिस्थापन।|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4684-0484-5}}</ref>
प्रतिस्थापन के एक सामान्य मामले में [[बहुपद]] सम्मिलित होते हैं, जहां एक अविभाज्य बहुपद के अनिश्चित के लिए एक संख्यात्मक मान (या अन्य अभिव्यक्ति) का प्रतिस्थापन उस मूल्य पर बहुपद का मूल्यांकन करने के लिए होता है। वास्तव में, यह संक्रिया इतनी बार-बार होती है कि बहुपदों के लिए अंकन अक्सर इसके अनुकूल हो जाता है; पी जैसे नाम से एक बहुपद को नामित करने के बजाय, जैसा कि कोई अन्य गणितीय वस्तुओं के लिए करेगा, कोई भी परिभाषित कर सकता है
प्रतिस्थापन के एक सामान्य मामले में [[बहुपद]] सम्मिलित होते हैं, जहां एक अविभाज्य बहुपद के अनिश्चित के लिए एक संख्यात्मक मान (या अन्य अभिव्यक्ति) का प्रतिस्थापन उस मूल्य पर बहुपद का मूल्यांकन करने के लिए होता है। वास्तविक में, यह संक्रिया इतनी बार-बार होती है कि बहुपदों के लिए अंकन अधिकांश इसके अनुकूल हो जाता है; P जैसे नाम से एक बहुपद को नामित करने के बजाय, जैसा कि कोई अन्य गणितीय वस्तुओं के लिए करेगा, कोई भी परिभाषित कर सकता है
:<math>P(X)=X^5-3X^2+5X-17</math>
:<math>P(X)=X^5-3X^2+5X-17</math>
ताकि X के लिए प्रतिस्थापन P(X) के अंदर प्रतिस्थापन द्वारा नामित किया जा सके, कहें
ताकि X के लिए प्रतिस्थापन P(X) के अंदर प्रतिस्थापन द्वारा नामित किया जा सके, कहें
Line 79: Line 79:
या
या
:<math>P(X+1) = X^5 + 5X^4 + 10X^3 + 7X^2 + 4X - 14.</math>
:<math>P(X+1) = X^5 + 5X^4 + 10X^3 + 7X^2 + 4X - 14.</math>
प्रतिस्थापन को प्रतीकों से निर्मित अन्य प्रकार की औपचारिक वस्तुओं पर भी प्रायुक्त किया जा सकता है, उदाहरण के लिए [[मुक्त समूह]]ों के तत्व। प्रतिस्थापन को परिभाषित करने के लिए, एक उपयुक्त [[सार्वभौमिक संपत्ति]] के साथ एक बीजगणितीय संरचना की आवश्यकता होती है, जो अद्वितीय [[समरूपता]] के अस्तित्व पर जोर देती है जो विशिष्ट मानों को अनिश्चित भेजती है; प्रतिस्थापन तब ऐसी समरूपता के अनुसार छवि को खोजने के लिए होता है।
प्रतिस्थापन को प्रतीकों से निर्मित अन्य प्रकार की औपचारिक वस्तुओं पर भी प्रायुक्त किया जा सकता है, उदाहरण के लिए [[मुक्त समूह|मुक्त समूहों]] के तत्व। प्रतिस्थापन को परिभाषित करने के लिए, एक उपयुक्त [[सार्वभौमिक संपत्ति]] के साथ एक बीजगणितीय संरचना की आवश्यकता होती है, जो अद्वितीय [[समरूपता]] के अस्तित्व पर जोर देती है जो विशिष्ट मानों को अनिश्चित भेजती है; प्रतिस्थापन तब ऐसी समरूपता के अनुसार छवि को खोजने के लिए होता है।


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


== यह भी देखें ==
== यह भी देखें ==
*समानता में प्रतिस्थापन संपत्ति (गणित)#समानता के कुछ बुनियादी तार्किक गुण
*समानता में प्रतिस्थापन संपत्ति (गणित) समानता के कुछ बुनियादी तार्किक गुण
*पहले क्रम का तर्क#अनुमान के नियम
*पहले क्रम का तर्क अनुमान के नियम
* [[सार्वभौमिक तात्कालिकता]]
* [[सार्वभौमिक तात्कालिकता]]
* लैम्ब्डा कैलकुस # प्रतिस्थापन
* लैम्ब्डा कैलकुस # प्रतिस्थापन

Revision as of 10:45, 20 April 2023

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

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

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

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

परिभाषा

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

(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 की आवश्यकता होती है। संकेतन { x1↦ t1, …, xk↦ tk }[note 1]

प्रत्येक चर xi के प्रतिस्थापन मानचित्रण को संदर्भित करता है इसी अवधि के लिए ti, i=1,…,k, और हर दूसरे चर के लिए; xi जोड़ीदार अलग होना चाहिए। उस प्रतिस्थापन को एक शब्द t पर प्रायुक्त करना पोस्टफिक्स नोटेशन में t { x1↦ t1, ..., xk↦ tk के रूप में लिखा गया हैं}; इसका अर्थ है (एक साथ) प्रत्येक xi t द्वारा ti में की प्रत्येक घटना को प्रतिस्थापित करना है।[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 के चर σ के डोमेन में हैं, अर्थात् यदि vars(t) ⊆ dom(σ)।

एक प्रतिस्थापन σ को एक रैखिक प्रतिस्थापन कहा जाता है यदि tσ एक शब्द (तर्क) ग्राउंड और कुछ (और इसलिए प्रत्येक) रैखिक शब्द टी के लिए रैखिक शब्द शब्द है जिसमें ठीक से σ's के चर होते हैं डोमेन, अर्थात् vars(t) = dom(σ) के साथ।

एक प्रतिस्थापन σ को समतल प्रतिस्थापन कहा जाता है यदि xσ प्रत्येक चर x के लिए एक चर है।

एक प्रतिस्थापन σ को पुनर्नामित प्रतिस्थापन कहा जाता है यदि यह सभी चरों के सेट पर समूह सिद्धांत में क्रमचय क्रमपरिवर्तन है। हर क्रमचय की तरह, नाम बदलने वाले प्रतिस्थापन σ का हमेशा एक व्युत्क्रम प्रतिस्थापन σ−1 होता है, जैसे कि tσσ−1 = t = tσ−1σ प्रत्येक पद t के लिए। चूंकि, स्वैच्छिक प्रतिस्थापन के लिए व्युत्क्रम को परिभाषित करना संभव नहीं है।

उदाहरण के लिए, { x ↦ 2, y ↦ 3+4 } एक ग्राउंड प्रतिस्थापन है, { x ↦ X1, y ↦ y2+4 } नॉन-ग्राउंड और गैर-समतल, किन्तु रैखिक, { x ↦ y2, y ↦ y2 +4} गैर-रेखीय और गैर-समतल है, {x ↦ y2, y ↦ y2} समतल है, किन्तु गैर-रैखिक है, { x ↦ X1, y ↦ y2} रैखिक और सपाट दोनों है, किन्तु नामकरण नहीं, क्योंकि मानचित्र y और y2 से y2 दोनों हैं; इनमें से प्रत्येक प्रतिस्थापन में {x, y} को इसके डोमेन के रूप में सेट किया गया है। पुनर्नामकरण प्रतिस्थापन के लिए एक उदाहरण {x ↦ X1, X1 ↦ y, y ↦ y2, y2 ↦ x} है, इसका व्युत्क्रम {x ↦ y2, y2 ↦ y, y ↦ X1, x1 ↦ x} है। समतल प्रतिस्थापन { 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 के लिए मैप करते हैं।

दो प्रतिस्थापनों की संरचना σ = { x1 ↦ t1, …, xk ↦ tk } और τ = { y1 ↦ u1, …, yl ↦ ul } को प्रतिस्थापन से हटाकर प्राप्त किया जाता है { x1 ↦ t1τ, …, xk ↦ tkτ, y1 ↦ u1, …, yl ↦ ul } उन युग्मों yi ↦ ui जिनके लिए yi ∈ { x1, …, xk}। σ और τ की संरचना को στ द्वारा निरूपित किया जाता है। रचना एक साहचर्य संक्रिया है, और प्रतिस्थापन अनुप्रयोग के साथ संगत है अर्थात (ρσ)τ = ρ(στ) और (tσ)τ = t(στ) प्रत्येक प्रतिस्थापन ρ, σ, τ, और प्रत्येक शब्द t के लिए क्रमशः। पहचान प्रतिस्थापन, जो प्रत्येक चर को अपने आप में मैप करता है, प्रतिस्थापन संरचना का तटस्थ तत्व है। एक प्रतिस्थापन σ को idempotent कहा जाता है यदि σσ = σ, और इसलिए प्रत्येक पद t के लिए tσσ = tσ। प्रतिस्थापन { x1 ↦ t1, …, xk ↦ tk } उदासीन है यदि और केवल यदि कोई भी चर xi किसी भी ti में नहीं होता है। प्रतिस्थापन संरचना क्रमविनिमेय नहीं है, अर्थात, στ, τσ से भिन्न हो सकता है, तथापि σ और τ उदासीन हों।[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 के लिए प्रतिस्थापन P(X) के अंदर प्रतिस्थापन द्वारा नामित किया जा सके, कहें

या

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

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

यह भी देखें

टिप्पणियाँ

  1. ↑ Some authors use [ t1/x1, …, tk/xk ] 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.
  2. ↑ 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. ↑ 1.0 1.1 David A. Duffy (1991). स्वचालित प्रमेय साबित करने के सिद्धांत. Wiley.
  2. ↑ 2.0 2.1 Franz Baader, Wayne Snyder (2001). Alan Robinson and Andrei Voronkov (ed.). एकीकरण सिद्धांत (PDF). Elsevier. pp. 439–526.
  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.
  4. ↑ Margret H. Hoft; Hartmut F.W. Hoft (6 November 2002). गणित के साथ कम्प्यूटिंग. Elsevier. ISBN 978-0-08-048855-4.
  5. ↑ Andre Heck (6 December 2012). मेपल का परिचय. Springer Science & Business Media. ISBN 978-1-4684-0484-5. प्रतिस्थापन।


संदर्भ


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=प्रतिस्थापन_(तर्क)&oldid=141326’