प्रतिस्थापन (तर्क): Difference between revisions
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> | ||
प्रत्येक चर x | |||
प्रत्येक चर 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 ↦ z, z ↦ h(a,y) } प्रायुक्त करना | उदाहरण के लिए, शब्द में प्रतिस्थापन { x ↦ z, z ↦ h(a,y) } प्रायुक्त करना | ||
:{| | :{| | ||
| Line 48: | Line 50: | ||
|| . | || . | ||
|} | |} | ||
एक प्रतिस्थापन σ के डोमेन डोम (σ) को | एक प्रतिस्थापन σ के डोमेन डोम (σ) को सामान्यतः वास्तव में प्रतिस्थापित चर के सेट के रूप में परिभाषित किया जाता है, अर्थात डोम (σ) = { x ∈ V | xσ ≠ x }. | ||
एक प्रतिस्थापन को ग्राउंड प्रतिस्थापन कहा जाता है यदि यह अपने डोमेन के सभी चर को शब्द (तर्क) | |||
एक जमीनी प्रतिस्थापन का प्रतिस्थापन उदाहरण tσ एक | एक प्रतिस्थापन को ग्राउंड प्रतिस्थापन कहा जाता है यदि यह अपने डोमेन के सभी चर को शब्द (तर्क) ग्राउंड और रैखिक शर्तों, अर्थात् चर-मुक्त, शब्दों में मैप करता है। | ||
एक प्रतिस्थापन σ को एक रैखिक प्रतिस्थापन कहा जाता है यदि tσ एक शब्द (तर्क) | |||
एक जमीनी प्रतिस्थापन का प्रतिस्थापन उदाहरण tσ एक ग्राउंड टर्म है यदि सभी t के चर σ के डोमेन में हैं, अर्थात् यदि vars(t) ⊆ dom(σ)। | |||
एक प्रतिस्थापन σ को एक रैखिक प्रतिस्थापन कहा जाता है यदि tσ एक शब्द (तर्क) ग्राउंड और कुछ (और इसलिए प्रत्येक) रैखिक शब्द टी के लिए रैखिक शब्द शब्द है जिसमें ठीक से σ{{'}}s के चर होते हैं डोमेन, अर्थात् vars(t) = dom(σ) के साथ। | |||
एक प्रतिस्थापन σ को समतल प्रतिस्थापन कहा जाता है यदि xσ प्रत्येक चर x के लिए एक चर है। | एक प्रतिस्थापन σ को समतल प्रतिस्थापन कहा जाता है यदि xσ प्रत्येक चर x के लिए एक चर है। | ||
उदाहरण के लिए, { | एक प्रतिस्थापन σ को पुनर्नामित प्रतिस्थापन कहा जाता है यदि यह सभी चरों के सेट पर समूह सिद्धांत में क्रमचय क्रमपरिवर्तन है। हर क्रमचय की तरह, नाम बदलने वाले प्रतिस्थापन σ का हमेशा एक व्युत्क्रम प्रतिस्थापन σ<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σ = xτ प्रत्येक चर x ∈ V के लिए मैप करते हैं। | |||
दो प्रतिस्थापनों | दो प्रतिस्थापनों की संरचना σ = { 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}} | ||
σ और τ की संरचना को στ द्वारा निरूपित किया जाता है। रचना एक साहचर्य संक्रिया है, और प्रतिस्थापन अनुप्रयोग के साथ संगत है | |||
पहचान प्रतिस्थापन, जो प्रत्येक चर को अपने आप में मैप करता है, प्रतिस्थापन संरचना का तटस्थ तत्व है। एक प्रतिस्थापन σ को idempotent कहा जाता है यदि σσ = σ, और इसलिए प्रत्येक पद t के लिए tσσ = tσ। प्रतिस्थापन { | |||
उदाहरण के लिए, { x ↦ 2, y ↦ 3+4} {y ↦ 3+4, x ↦ 2} के बराबर है, लेकिन { x ↦ 2, y ↦ 7} से अलग है। प्रतिस्थापन { x ↦ y+y } उदासीन है, | उदाहरण के लिए, { 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} है। | ||
== [[बीजगणित]] == | == [[बीजगणित]] == | ||
| Line 76: | Line 81: | ||
प्रतिस्थापन को प्रतीकों से निर्मित अन्य प्रकार की औपचारिक वस्तुओं पर भी प्रायुक्त किया जा सकता है, उदाहरण के लिए [[मुक्त समूह]]ों के तत्व। प्रतिस्थापन को परिभाषित करने के लिए, एक उपयुक्त [[सार्वभौमिक संपत्ति]] के साथ एक बीजगणितीय संरचना की आवश्यकता होती है, जो अद्वितीय [[समरूपता]] के अस्तित्व पर जोर देती है जो विशिष्ट मानों को अनिश्चित भेजती है; प्रतिस्थापन तब ऐसी समरूपता के अनुसार छवि को खोजने के लिए होता है। | प्रतिस्थापन को प्रतीकों से निर्मित अन्य प्रकार की औपचारिक वस्तुओं पर भी प्रायुक्त किया जा सकता है, उदाहरण के लिए [[मुक्त समूह]]ों के तत्व। प्रतिस्थापन को परिभाषित करने के लिए, एक उपयुक्त [[सार्वभौमिक संपत्ति]] के साथ एक बीजगणितीय संरचना की आवश्यकता होती है, जो अद्वितीय [[समरूपता]] के अस्तित्व पर जोर देती है जो विशिष्ट मानों को अनिश्चित भेजती है; प्रतिस्थापन तब ऐसी समरूपता के अनुसार छवि को खोजने के लिए होता है। | ||
प्रतिस्थापन संबंधित है, लेकिन फ़ंक्शन संरचना के समान नहीं है; यह लैम्ब्डा कैलकुस में β-कमी से निकटता से संबंधित है। इन धारणाओं के विपरीत, | प्रतिस्थापन संबंधित है, लेकिन फ़ंक्शन संरचना के समान नहीं है; यह लैम्ब्डा कैलकुस में β-कमी से निकटता से संबंधित है। इन धारणाओं के विपरीत, चूंकि, बीजगणित में जोर प्रतिस्थापन संचालन द्वारा बीजगणितीय संरचना के संरक्षण पर है, तथ्य यह है कि प्रतिस्थापन हाथ में संरचना के लिए एक समरूपता देता है (बहुपदों के मामले में, [[अंगूठी (गणित)]] संरचना) .{{cn|date=March 2023}} | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 10:43, 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] प्रतिस्थापन के एक सामान्य मामले में बहुपद सम्मिलित होते हैं, जहां एक अविभाज्य बहुपद के अनिश्चित के लिए एक संख्यात्मक मान (या अन्य अभिव्यक्ति) का प्रतिस्थापन उस मूल्य पर बहुपद का मूल्यांकन करने के लिए होता है। वास्तव में, यह संक्रिया इतनी बार-बार होती है कि बहुपदों के लिए अंकन अक्सर इसके अनुकूल हो जाता है; पी जैसे नाम से एक बहुपद को नामित करने के बजाय, जैसा कि कोई अन्य गणितीय वस्तुओं के लिए करेगा, कोई भी परिभाषित कर सकता है
ताकि X के लिए प्रतिस्थापन P(X) के अंदर प्रतिस्थापन द्वारा नामित किया जा सके, कहें
या
प्रतिस्थापन को प्रतीकों से निर्मित अन्य प्रकार की औपचारिक वस्तुओं पर भी प्रायुक्त किया जा सकता है, उदाहरण के लिए मुक्त समूहों के तत्व। प्रतिस्थापन को परिभाषित करने के लिए, एक उपयुक्त सार्वभौमिक संपत्ति के साथ एक बीजगणितीय संरचना की आवश्यकता होती है, जो अद्वितीय समरूपता के अस्तित्व पर जोर देती है जो विशिष्ट मानों को अनिश्चित भेजती है; प्रतिस्थापन तब ऐसी समरूपता के अनुसार छवि को खोजने के लिए होता है।
प्रतिस्थापन संबंधित है, लेकिन फ़ंक्शन संरचना के समान नहीं है; यह लैम्ब्डा कैलकुस में β-कमी से निकटता से संबंधित है। इन धारणाओं के विपरीत, चूंकि, बीजगणित में जोर प्रतिस्थापन संचालन द्वारा बीजगणितीय संरचना के संरक्षण पर है, तथ्य यह है कि प्रतिस्थापन हाथ में संरचना के लिए एक समरूपता देता है (बहुपदों के मामले में, अंगूठी (गणित) संरचना) .[citation needed]
यह भी देखें
- समानता में प्रतिस्थापन संपत्ति (गणित)#समानता के कुछ बुनियादी तार्किक गुण
- पहले क्रम का तर्क#अनुमान के नियम
- सार्वभौमिक तात्कालिकता
- लैम्ब्डा कैलकुस # प्रतिस्थापन
- सत्य-मूल्य शब्दार्थ
- एकीकरण (कंप्यूटर विज्ञान)
- मेटावैरिएबल
- यथोचित परिवर्तन सहित
- प्रतिस्थापन का नियम
- स्ट्रिंग प्रक्षेप - जैसा कि कंप्यूटर प्रोग्रामिंग में देखा गया है
- प्रतिस्थापन द्वारा एकीकरण
- त्रिकोणमितीय प्रतिस्थापन
टिप्पणियाँ
- ↑ 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.
- ↑ 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 at the nLab
