सामग्री पर जाएँ
Topos Uranos
हिन्दी

डी मॉर्गन के और वितरण के व्यापकीकृत नियम

सारांश

डी मॉर्गन के नियम और वितरण नियम अब तक दो पदों के लिए कहे गए थे; इसके विपरीत, प्रसामान्य रूप किसी भी संख्या के पदों वाले संयोजनों और वियोजनों को एकत्र करते हैं, और उन्हें ये नियम उनकी पूरी व्यापकता में चाहिए। यह पाठ सूत्रों की किसी सूची (φ1,…,φn)(\varphi_1, \ldots, \varphi_n) के संयोजन और वियोजन को पुनरावर्तन द्वारा परिभाषित करता है, जिन्हें क्रमशः ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i और ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i लिखा जाता है और जो बाईं ओर से समूहित होते हैं; और पदों की संख्या पर आगमन से सिद्ध करता है: मान प्रमेयिका (एक संयोजन सत्य है यदि और केवल यदि उसके सभी पद सत्य हों, और एक वियोजन सत्य है यदि और केवल यदि उसका कोई पद सत्य हो), पुनः समूहन की अनुमति देने वाली व्यापकीकृत साहचर्यता, क्रम और पुनरावृत्तियों से स्वतंत्रता, डी मॉर्गन के व्यापकीकृत नियम, और वितरण का व्यापकीकृत नियम उसी रूप में जिसमें प्रसामान्य रूपों का पाठ उसका उपयोग करता है: दो वियोजनों का संयोजन, जिनके पदों की संख्या nn और mm है, उन nmnm संयोजनों के वियोजन के तुल्य है जो प्रत्येक वियोजन से एक-एक पद लेकर बनते हैं, और द्वैत रूप से भी यही सत्य है। प्रश्नों में मान-नियतन गिने जाते हैं, उस उपपत्ति की भूल पकड़ी जाती है जो एक पुनः समूहन को परिभाषा बताकर प्रस्तुत करती है, वितरण से होने वाली वृद्धि मापी जाती है, और उससे 2n2^n पदों वाली एक पुनरुक्ति प्राप्त की जाती है।

अधिगम उद्देश्य

  1. nn पदों वाले संयोजनों और वियोजनों को ⋀\bigwedge और ⋁\bigvee संकेतन से लिखना, उन्हें बाईं ओर से समूहित प्रतीक-शृंखलाओं के रूप में खोलना और मान प्रमेयिका से उनका सत्यता मान निकालना।
  2. पदों की संख्या पर आगमन से व्यापकीकृत साहचर्यता, क्रम और पुनरावृत्तियों से स्वतंत्रता और डी मॉर्गन के व्यापकीकृत नियम सिद्ध करना, और प्रत्येक चरण में प्रतीक-शृंखलाओं की सर्वसमिका को शब्दार्थीय तुल्यता से अलग पहचानना।
  3. दो सूचकांकों पर आगमन को व्यवस्थित करके वितरण का व्यापकीकृत नियम और उसका द्वैत सिद्ध करना, और किसी वितरण से उत्पन्न पदों को गिनना।
  4. आगमन द्वारा उस उपपत्ति की भूल ढूँढ़ना जिसकी आधार स्थिति गलत लिखी गई हो या जिसका चरण एक पुनः समूहन को छिपाता हो, और उसे सुधारना।

किसी भी संख्या के पदों के लिए नियम

शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता के पाठ ने दो पदों के लिए तुल्यता के नियम स्थापित किए: उनमें ∧\wedge और ∨\vee की क्रमविनिमेयता और साहचर्यता, डी मॉर्गन के नियम और वितरण के दो नियम हैं। परंतु वियोजक प्रसामान्य रूप का कोई सूत्र संयोजनों का वियोजन होता है, और प्रत्येक संयोजन में उतने पद होते हैं जितने आवश्यक हों; किसी सूत्र को इस रूप में लाने के लिए किसी भी लंबाई के संयोजनों और वियोजनों का निषेध करना, उन्हें पुनः समूहित करना और उनका वितरण करना पड़ता है। यदि ऐसा है, तो दो पदों के नियम अपने आप में पर्याप्त नहीं हैं: उन्हें nn पदों तक बढ़ाना होगा, और वह भी एक साथ सभी nn के लिए।

प्रत्येक निश्चित nn के लिए, nn पदों वाला डी मॉर्गन का नियम 2n2^n पंक्तियों की एक सत्यता सारणी से जाँचा जा सकता है, जो nn चरों से लिखी जाती है, और पिछले पाठ का समरूप स्थापन, दोनों पक्षों के बीच के द्विसोपाधिक पर लागू होकर, उसे किसी भी सूत्र तक ले जाता है। परंतु nn के मान अनंत हैं, और कितनी भी सारणियाँ उन्हें समाप्त नहीं करतीं। इससे यह निकलता है कि “सभी nn के लिए” वाला दावा दो सूत्रों के बीच की तुल्यता नहीं है, बल्कि अनंत तुल्यताओं के बारे में एक कथन है, जो अधिभाषा में व्यक्त किया गया है; उसकी उपपत्ति बाहरी है, प्राकृत संख्याओं और सूत्रों पर आगमन के पाठ की उपपत्तियों की तरह, और उसका साधन पदों की संख्या पर आगमन है। संकेतन ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i भी अधिभाषा का है: यह भाषा का कोई नया प्रतीक नहीं, बल्कि वृत्तों और चक्रिकाओं की एक प्रतीक-शृंखला का नाम है, ठीक वैसे ही जैसे (φ∧ψ)(\varphi \wedge \psi)।

अभी से उन तीन संबंधों को निश्चित कर लेना उचित है जिन्हें भ्रमित नहीं करना चाहिए। समता α=β\alpha = \beta कहती है कि α\alpha और β\beta एक ही प्रतीक-शृंखला हैं; परिभाषाएँ, जो :=:= से लिखी जाती हैं, प्रतीक-शृंखलाओं के लिए नाम प्रस्तुत करती हैं, और जो किसी परिभाषा को खोलने से मिलता है वह समान है, केवल तुल्य नहीं। शब्दार्थीय तुल्यता α≡β\alpha \eqsem \beta कहती है कि v(α)=v(β)v(\alpha) = v(\beta), प्रत्येक मान-नियतन vv के लिए। निगमन की इकाई की सिद्ध तुल्यता, α⊣⊢β\alpha \dashv\vdash \beta, कहती है कि दोनों सूत्रों में से प्रत्येक दूसरे से निगमित होता है। यह पाठ पहले दो संबंधों से काम लेता है; तीसरा केवल एक टिप्पणी में आता है।

क्या प्रयुक्त होता है

प्रस्तावात्मक तर्क के अर्थविज्ञान के पाठ से ये लिए जाते हैं: मान-नियतन, अर्थात् चरों v1,v2,…v_1, v_2, \ldots से {0,1}\{0, 1\} में फलन, और सभी सूत्रों तक उनका विस्तार (जिसे उसी अक्षर vv से लिखा जाता है); आधिकारिक संक्षेपणों से निकाले गए व्युत्पन्न संयोजकों के मान, v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi) और v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi) (इसलिए एक संयोजन का मान 11 है यदि और केवल यदि उसके दोनों घटकों का मान 11 हो, और v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 यदि और केवल यदि v(φ)=1v(\varphi) = 1 या v(ψ)=1v(\psi) = 1); संपाती प्रमेयिका (दो मान-नियतन जो किसी सूत्र के चरों पर मेल खाते हैं, उस सूत्र पर भी मेल खाते हैं); और सूत्र ⊤\top और ⊥\bot, एक निश्चित पुनरुक्ति और एक निश्चित व्याघात। शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता के पाठ से ये लिए जाते हैं: यह कि ≡\eqsem स्वतुल्य, सममित और संक्रामक है; शब्दार्थीय प्रतिस्थापन प्रमेय; और नामित नियमों की सूची: क्रमविनिमेयता (φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) और (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi), (φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) और ∨\vee के लिए वैसा ही नियम, डी मॉर्गन के नियम ¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) और ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi), वितरण (φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) और (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi)), दोहरा निषेध ¬¬φ≡φ\neg\neg\varphi \eqsem \varphi, वर्गसमता (φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi, तत्समक नियम (φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi और अपवर्जित मध्य ⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi)। ये नियम किन्हीं भी सूत्रों φ\varphi, ψ\psi और χ\chi के लिए मान्य हैं, जो अधिचर हैं।

आगे की उपपत्तियों के प्रत्येक चरण में किसी सूत्र के एक भाग को उसके तुल्य दूसरे भाग से बदला जाता है। शब्दार्थीय प्रतिस्थापन प्रमेय इसकी अनुमति एक बार में एक उपस्थिति के लिए देता है; अगली प्रमेयिका, जो उसकी एक विशेष स्थिति है, इसे निषेध, संयोजन या वियोजन के भागों के लिए एक ही बार में देती है। ध्यान देना चाहिए कि यह कोई वाक्यविन्यासीय तुच्छता नहीं है: ¬α\neg\alpha प्रतीक-शृंखला (α↓α)(\alpha \downarrow \alpha) है, जिसमें α\alpha दो बार आता है, और इसलिए (α∧β)(\alpha \wedge \beta) में α\alpha की आठ उपस्थितियाँ और β\beta की आठ उपस्थितियाँ हैं।

उपप्रमेयसंयोजकों की तुल्यता के साथ अनुकूलता

यदि α≡α′\alpha \eqsem \alpha' और β≡β′\beta \eqsem \beta', तो ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta') और (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta')।

प्रमाण

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    मान लीजिए vv कोई भी मान-नियतन है। परिकल्पना से, α\alpha और α′\alpha' का मान एक ही है, और β\beta और β′\beta' का भी।

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    किसी निषेध का मान और किसी संयोजन का मान केवल उनके घटकों के मानों पर निर्भर करता है।

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    वियोजन के साथ भी यही होता है: उसका मान 11 है यदि और केवल यदि किसी घटक का मान 11 हो, और घटकों के मान दोनों पक्षों में समान हैं।

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    चूँकि vv कोई भी था, तीनों तुल्यताएँ मान्य हैं।