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

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

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

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

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

परिभाषा

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

(R → S) & (T → S)

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

P & Q

और

(A ↔ A) ↔ (A ↔ A)

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

(A ↔ A)

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

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

टॉटोलॉजी

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

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

पहले क्रम के तर्क में, प्रतिस्थापन कुल माप है σ: V → T पद (तर्क) से कई शब्दों तक किन्तु सब नहीं लेखकों को अतिरिक्त रूप से σ (x) = x सभी के लिए किन्तु बहुत से चर x की आवश्यकता होती है। संकेतन { x₁↦ t₁, …, x_k↦ t_k }

प्रत्येक चर x_i के प्रतिस्थापन मानचित्रण को संदर्भित करता है इसी अवधि के लिए t_i, i=1,…,k, और हर दूसरे चर के लिए; x_i जोड़ीदार अलग होना चाहिए। उस प्रतिस्थापन को शब्द t पर प्रायुक्त करना पोस्टफिक्स नोटेशन में t { x₁↦ t₁, ..., x_k↦ t_k के रूप में लिखा गया हैं}; इसका अर्थ है (साथ) प्रत्येक x_i t द्वारा t_i में की प्रत्येक घटना को प्रतिस्थापित करना है। किसी पद 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 के लिए चर है।

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

उदाहरण के लिए, { x ↦ 2, y ↦ 3+4 } ग्राउंड प्रतिस्थापन है, { x ↦ X₁, y ↦ y₂+4 } नॉन-ग्राउंड और गैर-समतल, किन्तु रैखिक, { x ↦ y₂, y ↦ y₂ +4} गैर-रेखीय और गैर-समतल है, {x ↦ y₂, y ↦ y₂} समतल है, किन्तु गैर-रैखिक है, { x ↦ X₁, y ↦ y₂} रैखिक और सपाट दोनों है, किन्तु नामकरण नहीं, क्योंकि मानचित्र y और y₂ से y₂ दोनों हैं; इनमें से प्रत्येक प्रतिस्थापन में {x, y} को इसके डोमेन के रूप में सेट किया गया है। पुनर्नामकरण प्रतिस्थापन के लिए उदाहरण {x ↦ X₁, X₁ ↦ y, y ↦ y₂, y₂ ↦ x} है, इसका व्युत्क्रम {x ↦ y₂, y₂ ↦ y, y ↦ X₁, x₁ ↦ 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₁ ↦ t₁, …, x_k ↦ t_k } और τ = { y₁ ↦ u₁, …, y_l ↦ u_l } को प्रतिस्थापन से हटाकर प्राप्त किया जाता है { x₁ ↦ t₁τ, …, x_k ↦ t_kτ, y₁ ↦ u₁, …, y_l ↦ u_l } उन युग्मों y_i ↦ u_i जिनके लिए y_i ∈ { x₁, …, x_k}। σ और τ की संरचना को στ द्वारा निरूपित किया जाता है। रचना साहचर्य संक्रिया है, और प्रतिस्थापन अनुप्रयोग के साथ संगत है अर्थात (ρσ)τ = ρ(στ) और (tσ)τ = t(στ) प्रत्येक प्रतिस्थापन ρ, σ, τ, और प्रत्येक शब्द t के लिए क्रमशः। पहचान प्रतिस्थापन, जो प्रत्येक चर को अपने आप में मैप करता है, प्रतिस्थापन संरचना का तटस्थ तत्व है। प्रतिस्थापन σ को idempotent कहा जाता है यदि σσ = σ, और इसलिए प्रत्येक पद t के लिए tσσ = tσ। प्रतिस्थापन { x₁ ↦ t₁, …, x_k ↦ t_k } उदासीन है यदि और केवल यदि कोई भी चर x_i किसी भी t_i में नहीं होता है। प्रतिस्थापन संरचना क्रमविनिमेय नहीं है, अर्थात, στ, τσ से भिन्न हो सकता है, तथापि σ और τ उदासीन हों।

उदाहरण के लिए, { 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} है।

बीजगणित

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

$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.$

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

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

यह भी देखें

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

संदर्भ

• 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