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

इस इकाई के पिछले पाठों ने, एक के ऊपर दूसरा, निगमन के उपकरण बनाए: अभिगृहीत प्रणाली और मोडस पोनेन्स, चार मूल तकनीकें और दोहरे निषेध का प्रतिस्थापन, संयोजकों की सममितियाँ और शास्त्रीय तर्क की तकनीकें। यह पाठ कोई नया नियम नहीं जोड़ता; यह उन्हें साथ मिलकर काम करवाता है। यदि ऐसा है, तो इसकी रुचि कथनों में उतनी नहीं है, जो शायद दूसरे पाठ्यक्रमों से ज्ञात हों, जितनी उन्हें प्राप्त करने की विधि में: प्रत्येक पंक्ति का औचित्य किसी अभिगृहीत, किसी आधार-वाक्य, किसी परिभाषा, दोनों मूल नियमों में से किसी एक या किसी पहले से सिद्ध परिणाम से देना होता है, और कोई भी पंक्ति उस पर नहीं टिक सकती जो “स्पष्ट प्रतीत होता है”।

क्या उपयोग होता है और वह कैसे जुड़ता है

औपचारिक निगमन प्रणालियों वाले पाठ से लुकासिएविच के अभिगृहीत A1, A2 और A3, मोडस पोनेन्स (MP), आधार-वाक्यों के साथ भी, स्वतुल्यता (Refl: यदि $\varphi \in \Gamma$, तो $\Gamma \vdash \varphi$), एकदिष्टता (Mon), कर्तन (Cut: यदि $\Gamma \vdash \varphi_i$, प्रत्येक $i$ के लिए, और $\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi$, तो $\Gamma \vdash \psi$), निगमन प्रमेय (DT) और निगमनतः तुल्यता ($\varphi \dashv\vdash \psi$ यदि $\{\varphi\} \vdash \psi$ और $\{\psi\} \vdash \varphi$) लिए जाते हैं, अपने गुणों सहित: यह स्वतुल्य, सममित और संक्रामक है, और, यदि $\varphi \dashv\vdash \psi$, तो $\Gamma \vdash \varphi$ यदि और केवल यदि $\Gamma \vdash \psi$। निगमन की चार तकनीकों वाले पाठ से दोहरा निषेध (DN: $\varphi \dashv\vdash \neg\neg\varphi$), प्रतिपरिवर्तन (CP), विशेष रूप से $(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi)$, और पाठ्यक्रम की प्रणाली का दूसरा मूल नियम, दोहरे निषेध का प्रतिस्थापन (RDN), लिए जाते हैं, जिसके साथ निगमन प्रमेय मान्य बना रहता है: यदि $\chi'$, $\chi$ से किसी उपसूत्र $\theta$ की एक उपस्थिति को $\neg\neg\theta$ से, या $\neg\neg\theta$ की एक उपस्थिति को $\theta$ से, प्रतिस्थापित करने पर प्राप्त होता है, तो $\chi$ से $\chi'$ का अनुमान होता है; इस प्रकार पंक्ति $i$ से प्राप्त पंक्ति का औचित्य RDN$(i)$ होता है। इसके तात्कालिक परिणामों में $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$, $(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$ और, सामान्यतः, $\chi \dashv\vdash \chi'$ हैं, जब $\chi'$, $\chi$ से RDN द्वारा प्राप्त होता है; इससे यह निकलता है कि RDN$(i)$, $\chi \dashv\vdash \varphi$ के रूप वाली पंक्ति पर भी लागू होता है, ताकि $\varphi$ में किसी दोहरे निषेध को बदला जा सके। संयोजकों की सममितियों वाले पाठ से तुल्यों का प्रतिस्थापन (Repl) और सममितियाँ (Sym) ली जाती हैं, जिनमें $(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi)$ और $(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi)$ हैं।

शास्त्रीय तर्क की तकनीकों वाले पाठ से निम्नलिखित नियम लिए जाते हैं, सभी आधार-वाक्यों के किसी समुच्चय $\Gamma$ के साथ। वियोजन का प्रवेश ($\vee$I): यदि $\Gamma \vdash \varphi$, तो $\Gamma \vdash (\varphi \vee \psi)$ और $\Gamma \vdash (\psi \vee \varphi)$। वियोजन का निरसन ($\vee$E, वियोजक न्यायवाक्य): यदि $\Gamma \vdash (\varphi \vee \psi)$ और $\Gamma \vdash \neg\varphi$, तो $\Gamma \vdash \psi$। संयोजन का प्रवेश ($\wedge$I): यदि $\Gamma \vdash \varphi$ और $\Gamma \vdash \psi$, तो $\Gamma \vdash (\varphi \wedge \psi)$। संयोजन का निरसन ($\wedge$E): यदि $\Gamma \vdash (\varphi \wedge \psi)$, तो $\Gamma \vdash \varphi$ और $\Gamma \vdash \psi$। मध्य-परिहार नियम (EM): $\vdash (\varphi \vee \neg\varphi)$। और स्थिति-भेद से उपपत्ति (स्थितियाँ) अपने दोनों रूपों में: यदि $\Gamma \cup \{\varphi\} \vdash \chi$ और $\Gamma \cup \{\neg\varphi\} \vdash \chi$, तो $\Gamma \vdash \chi$; और यदि $\Gamma \cup \{\varphi\} \vdash \chi$, $\Gamma \cup \{\psi\} \vdash \chi$ और $\Gamma \vdash (\varphi \vee \psi)$, तो $\Gamma \vdash \chi$। निगमनों में, पहला रूप दो पंक्तियों के साथ उद्धृत होता है, स्थितियाँ$(i, j)$, और दूसरा तीन के साथ, स्थितियाँ$(i, j, k)$, कथन के क्रम में: दोनों स्थितियाँ और, अंत में, वियोजन। वह पाठ यह भी याद दिलाता है कि हर पहले से सिद्ध नियम किसी संदर्भ $\Gamma$ के भीतर मान्य है, और यहाँ दोहरे निषेध और प्रतिपरिवर्तन का उपयोग इसी तरह होता है।

किसी शृंखला के नाम और तुल्य सूत्र

प्रस्तावात्मक तर्क की भाषा वाले पाठ से याद करें कि $\downarrow$ से भिन्न संयोजक एक आधिकारिक और अद्वितीय परिभाषा वाले संक्षेपण हैं: $\neg\varphi := (\varphi \downarrow \varphi)$, $(\varphi \vee \psi) := \neg(\varphi \downarrow \psi)$, $(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi)$, $(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi)$, $(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi))$ और $(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi)$। कोई परिभाषा सूत्रों के बारे में कुछ भी अभिकथित नहीं करती: वह पहले से विद्यमान एक शृंखला को दूसरा नाम देती है। इससे यह निकलता है कि यदि दो व्यंजक एक ही शृंखला को निर्दिष्ट करते हैं, तो एक को दूसरे के स्थान पर कहीं भी रखा जा सकता है, किसी बड़े सूत्र के भीतर भी, क्योंकि जो लिखा जाता है वह वृत्तों और चक्रिकाओं का वही अनुक्रम है। इस प्रकार, $\neg(\varphi \wedge \psi)$ और $\neg\neg(\neg\varphi \vee \neg\psi)$ एक ही शृंखला हैं: दूसरी, पहली के भीतर संयोजन का विस्तार लिखने से प्राप्त होती है। निगमनों में, नाम के इस परिवर्तन का औचित्य “Def” से दिया जाता है, जिसके बाद वह संयोजक लिखा जाता है जिसे खोला या संकुचित किया जाता है।

परंतु निगमनतः तुल्यता सर्वसमिका नहीं है। $\varphi \dashv\vdash \neg\neg\varphi$ का अर्थ है कि प्रत्येक से दूसरा निगमित होता है, यह नहीं कि वे एक ही शृंखला हैं: $\neg\neg\varphi$, $\varphi$ से बहुत लंबा है। अतः यह जानना कि $\varphi \dashv\vdash \varphi'$, अपने आप में, किसी बड़े सूत्र के भीतर $\varphi'$ को $\varphi$ के स्थान पर लिखने की अनुमति नहीं देता। यह “दोनों पक्षों का निषेध करने” की अनुमति भी नहीं देता: यह कि $\varphi \dashv\vdash \varphi'$ से $\neg\varphi \dashv\vdash \neg\varphi'$ निकलता है, एक प्रमेय है, तुल्यों का प्रतिस्थापन, जिसकी उपपत्ति प्रतिपरिवर्तन का उपयोग करती है, कोई स्पष्ट संक्रिया नहीं। केवल एक ही स्थिति है जिसमें प्रणाली प्रतिस्थापन की सीधे अनुमति देती है, सूत्र में किसी भी स्थान पर: $\theta$ को $\neg\neg\theta$ से, या इसके विपरीत, प्रतिस्थापित करना, जो RDN नियम है; और निगमन प्रणालियों वाले पाठ ने अंकन के द्वारा दिखाया कि यह स्थिति भी अभिगृहीतों और मोडस पोनेन्स से निगमित नहीं होती, इसलिए इसे अभिधारणा के रूप में रखना पड़ा। यह सावधानी पांडित्य-प्रदर्शन नहीं है; यही उपपत्ति को प्रतीकों के ऐसे हेरफेर से अलग करती है जो, अन्य संयोजकों पर या अन्य प्रणालियों में लागू होने पर, असत्य निष्कर्षों तक ले जा सकता है।

दो परिणाम सटीकता से निर्धारित करते हैं कि क्या अनुमत है। पहला औपचारिक निगमन प्रणालियों वाले पाठ का निगमनतः तुल्यता के गुणों संबंधी साध्य है: यदि $\Gamma \vdash \varphi$ और $\varphi \dashv\vdash \varphi'$, तो $\Gamma \vdash \varphi'$, जिससे किसी निगमनतः तुल्यता को किसी पंक्ति के पूरे सूत्र पर लागू किया जा सकता है; और निगमनतः तुल्यता स्वतुल्य, सममित और संक्रामक है, जिससे तुल्यताएँ शृंखलाबद्ध होती हैं (यदि $\chi \dashv\vdash \varphi$ और $\varphi \dashv\vdash \varphi'$, तो $\chi \dashv\vdash \varphi'$) और एक ही शृंखला को निर्दिष्ट करने वाले दो व्यंजक, स्वतुल्यता से, निगमनतः तुल्य हैं। दूसरा परिणाम आगे की प्रमेयिका है, जो सुविधा से उद्धृत करने के लिए तुल्यों के प्रतिस्थापन का वियोजन और संयोजन तक विस्तार एकत्र करती है; सममितियों वाला पाठ इस प्रतिस्थापन को निषेध, सोपाधिक और संयुक्त निषेध के लिए सिद्ध करता है और अपने हल प्रश्नों में से एक में इसे इन दो संयोजकों तक विस्तारित करता है।

आगे से, “Repl” तुल्यों के प्रतिस्थापन को उसके किसी भी रूप में निर्दिष्ट करता है, इस प्रमेयिका के रूपों को भी, और इसे परत-दर-परत कई बार लगातार लागू किया जा सकता है, ताकि किसी भी गहराई पर स्थित उपसूत्र तक पहुँचा जा सके। जब कोई पंक्ति पंक्ति $i$ से किसी पहले से सिद्ध तुल्यता को लागू करके प्राप्त होती है, चाहे पूरे सूत्र पर या, Repl के साथ, उसके किसी भाग पर, तो उसका औचित्य उस तुल्यता के नाम और पंक्ति की संख्या से दिया जाता है: DN$(i)$, “Repl, DM$(i)$”। नाम का परिवर्तन कोई तुल्यता लागू नहीं करता, बल्कि उसी शृंखला को फिर से लिखता है; उसका औचित्य भी उसी प्रकार “Def” से दिया जाता है, जिसके बाद वह संयोजक लिखा जाता है जिसे खोला या संकुचित किया जाता है: Def $\wedge$ $(i)$। औपचारिक निगमन प्रणालियों वाले पाठ का साध्य गारंटी देता है कि ऐसी पंक्तियाँ औचित्यपूर्ण हैं, चाहे पंक्ति $i$, $\Gamma \vdash \varphi$ अभिकथित करे या कोई तुल्यता $\chi \dashv\vdash \varphi$ जो क्रमशः आगे बढ़ाई जाती है।