अर्थविज्ञान: सारांश और चुनौतियाँ

सारांश

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

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

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

इकाई की उपलब्धियाँ

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

सूत्र का मान

प्रस्तावात्मक तर्क के अर्थविज्ञान पर पाठ ने मान-नियतन को चरों से $\{0, 1\}$ तक के फलन के रूप में परिभाषित किया और सूत्रों पर पुनरावर्तन द्वारा परिभाषा के प्रमेय से सिद्ध किया कि वह एक ही खंड के द्वारा अद्वितीय रूप से सभी सूत्रों तक विस्तृत होता है: $v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))$ । आधिकारिक संक्षेपणों से, और कुछ भी अभिधारित किए बिना, उसने प्रत्येक व्युत्पन्न संयोजक का मान घटकों के मानों के बहुपद के रूप में निकाला, और उसके साथ सोपाधिक की सारणी, जो यहाँ एक प्रमेय है। उसने जटिलता पर आगमन से संपाती प्रमेयिका सिद्ध की, जिससे यह निकलता है कि $2^{n}$ पंक्तियों की सत्यता सारणी में वह सब है जो अनंत मान-नियतन $n$ चरों वाले किसी सूत्र के बारे में कहते हैं; उसने संतुष्टि, वैधता, संतोषणीयता, व्याघात और आकस्मिकता को परिभाषित किया, स्पष्ट किया कि $\not\models \varphi$ कहता है कि $\varphi$ वैध नहीं है, न कि वह व्याघात है, $\top := (v_{1} \rightarrow v_{1})$ और $\bot := \neg\top$ को निर्धारित किया, और वैधता तथा संतोषणीयता की निर्णेयता घातीय क़ीमत पर प्राप्त की, जिसे खंडन करने वाले मान-नियतन की लक्षित खोज घटाती है, पर मिटाती नहीं।

परिणाम और तुल्यता

शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता पर पाठ ने आधार-वाक्यों के किसी समुच्चय से, परिमित हो या अनंत, परिणाम को परिभाषित किया और सिद्ध किया कि उसमें निगमन के संरचनात्मक गुण हैं (स्वतुल्यता, एकदिष्टता, कर्तन और संक्रामकता), ऐसी उपपत्तियों से जो पंक्तियों पर काम करने के बजाय मान-नियतनों को एक-एक करके देखती हैं। शब्दार्थीय निगमन प्रमेय, $\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)$ , सोपाधिक की एकमात्र असत्य पंक्ति पर आ टिका, और परिणाम असंतोषणीयता पर आ टिका: $\Gamma \models \varphi \Leftrightarrow \Gamma \cup \{\neg\varphi\}$ असंतोषणीय है। मानों की समानता के रूप में परिभाषित शब्दार्थीय तुल्यता पारस्परिक परिणाम के साथ और द्विसोपाधिक की वैधता के साथ मेल खाती पाई गई। उसके दो कार्य-प्रमेय जटिलता पर आगमन से सिद्ध हुए: किसी उपसूत्र की एक उपस्थिति का किसी तुल्य सूत्र से प्रतिस्थापन, पूर्ण उपस्थिति की उस स्थिति सहित जिसे छोड़ा नहीं जा सकता, और चरों के स्थान पर स्वेच्छ सूत्रों का समरूप स्थापन, जो वैधता, तुल्यता और परिणाम को संरक्षित करता है। इनके द्वारा, नियमों की सूची के नियम, जिन्हें बहुपदों की सर्वसमिकाओं के रूप में जाँचा गया, किसी भी सूत्र के किसी भी स्थान पर लागू होते हैं और शृंखलाबद्ध होते हैं।

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

डी मॉर्गन के और वितरण के व्यापकीकृत नियम पर पाठ ने पुनरावर्तन द्वारा, बाईं ओर साहचर्य के साथ, $n$ सूत्रों के संयोजन और वियोजन को परिभाषित किया और पदों की संख्या पर आगमन से मान प्रमेयिका सिद्ध की, जो कहती है कि संयोजन सत्य है यदि और केवल यदि उसके सभी पद सत्य हैं, और वियोजन यदि और केवल यदि कोई एक पद सत्य है। इसके और तुल्यता के साथ संयोजकों की अनुकूलता के द्वारा उसने व्यापकीकृत साहचर्यता प्राप्त की, जिसे तुल्यताओं की शृंखला से सिद्ध किया गया ताकि वह निगमनतः तुल्यता के लिए भी मान्य हो; क्रम और पुनरावृत्ति से स्वतंत्रता; डी मॉर्गन के व्यापकीकृत नियम; और व्यापकीकृत वितरण, जिसका दो सूचकांकों पर आगमन इस प्रकार रचा गया कि आगमन परिकल्पना दूसरी सूची की सभी लंबाइयों को समेटे; द्वैत नियम डी मॉर्गन के नियम से प्राप्त हुआ, दोहरे आगमन को दोहराए बिना।

सत्यता फलन

फलनात्मक पूर्णता पर पाठ ने उलटा मार्ग अपनाया, सारणी से सूत्र तक। उसने $n$ संकार्यों के सत्यता फलन गिने (वे $2^{2^{n}}$ हैं), दिखाया कि प्रत्येक सूत्र उनमें से ठीक एक को निरूपित करता है और दो सूत्र तुल्य हैं यदि और केवल यदि वे एक ही फलन को निरूपित करते हैं, और फलनात्मक पूर्णता का प्रमेय सिद्ध किया: किसी पंक्ति का संयोजन ठीक अपनी पंक्ति में सत्य है, और उन पंक्तियों के संयोजनों का वियोजन जिनमें फलन का मान $1$ है, उस फलन को निरूपित करता है। चूँकि यह सूत्र वृत्तों और चक्रिकाओं की एक प्रतीक-शृंखला है, अकेला संयुक्त निषेध पर्याप्त है; संयुक्त निषेध की कसौटी से $\{\neg, \wedge\}$ , $\{\neg, \vee\}$ , $\{\neg, \rightarrow\}$ और वैकल्पिक निषेध भी पर्याप्त हैं; और संवृति सिद्धांत से $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ के सभी सूत्र $1$ को संरक्षित करते हैं, अतः यह समुच्चय पर्याप्त नहीं है।

प्रसामान्य रूप

प्रसामान्य रूपों पर पाठ ने तुल्य सूत्रों के प्रत्येक वर्ग में निश्चित आकार के प्रतिनिधि चुने। उसने लिटरल, उपवाक्य और प्राथमिक संयोजन परिभाषित किए और सिद्ध किया कि किसी प्रसामान्य रूप का निषेध उसके द्वैत रूप के तुल्य है, जो प्रत्येक संयोजन को वियोजन में और प्रत्येक लिटरल को उसके विपरीत लिटरल में बदल देता है। उसने सारणी से विहित रूप बनाए, जो चर निश्चित होने पर अद्वितीय हैं, और दोनों प्रसामान्य रूपों का अस्तित्व दो प्रकार से सिद्ध किया: सारणी से, फलनात्मक पूर्णता के उपप्रमेय के रूप में, और जटिलता पर आगमन से, जिसमें एकमात्र स्थिति संयुक्त निषेध की है, जो अपने घटकों के निषेधों के संयोजन के तुल्य है, और आगमन परिकल्पना दोनों रूपों की एक साथ माँग करती है, क्योंकि निषेध उन्हें आपस में बदल देता है। अंत में, उसने दिखाया कि संयोजक रूप की वैधता और वियोजक रूप की संतोषणीयता उनके पूरक युग्मों से एक नज़र में पढ़ी जाती है।

कलन-विधि और परिपथ

प्रसामान्य रूपों की कलन-विधि और उसके अनुप्रयोग पर पाठ ने अस्तित्व की दूसरी उपपत्ति को लेखनों पर काम करने वाली एक प्रक्रिया में बदला: $\neg$ , $\wedge$ और $\vee$ के अतिरिक्त संयोजकों का निरसन, निषेधों को चरों तक ले जाना, और वितरण। उसने लेखनों में प्रतिस्थापन से उसकी शुद्धता सिद्ध की, जो प्रतिस्थापन प्रमेय को संक्षेपणों के अनुकूल बनाता है, और तीन मापों से उसका समापन, जो हर चरण में घटते हैं और जिनमें से अंतिम संयोजन को गुणनफल के रूप में पढ़ता है; उसने यह भी सिद्ध किया कि $\bigvee_{i=1}^{n} (p_i \wedge q_i)$ के संयोजक रूप में अनिवार्यतः $2^{n}$ उपवाक्य होते हैं, अतः वृद्धि कलन-विधि का दोष नहीं है। फिर उसने किसी ब्लैक बॉक्स के प्रसामान्य रूप उसकी सारणी से प्राप्त किए, उन्हें पड़ोसी पंक्तियों को मिलाकर सरल किया, और उन्हें स्विचों के परिपथों में बदला, जिनका चालन उनके सूत्र का मान है।

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

शृंखला के आधार

Aअद्वितीय पठनीयता और पुनरावर्तन. यदि $\sigI\varphi\psi = \sigI\varphi'\psi'$ , जहाँ चारों प्रतीक-शृंखलाएँ सूत्र हैं, तो $\varphi = \varphi'$ और $\psi = \psi'$ ; अतः कोई नियम जो $\sigI\varphi\psi$ का मान $\varphi$ से, $\psi$ से और उनके मानों से निकालता है, सूत्रों पर एक अद्वितीय फलन परिभाषित करता है। पहली इकाई में सिद्ध। इस इकाई में बिना प्रमाण के स्वीकार किया गया।
Bआगमन. प्राकृत संख्याओं पर सरल और प्रबल आगमन, और सूत्रों की जटिलता पर आगमन, जिसकी केवल स्थितियाँ चर और संयुक्त निषेध $(\varphi \downarrow \psi)$ हैं। पहली इकाई में सिद्ध। इस इकाई में बिना प्रमाण के स्वीकार किया गया।
Cआधिकारिक संक्षेपण. $\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)$ । पहली इकाई में निर्धारित। इस इकाई में बिना प्रमाण के स्वीकार किया गया।
Dसंयोजकों के मान. $a = v(\varphi)$ और $b = v(\psi)$ होने पर: $v(\neg\varphi) = 1 - a$ , $v((\varphi \vee \psi)) = a + b - ab$ , $v((\varphi \wedge \psi)) = ab$ , $v((\varphi \rightarrow \psi)) = 1 - a(1 - b)$ , $v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b)$ और $v((\varphi \veebar \psi)) = a + b - 2ab$ , जहाँ $a^{2} = a$ । स्थापित होता है: 1. मान-नियतन का विस्तार.
Eसंपाती प्रमेयिका. यदि दो मान-नियतन $\varphi$ के चरों पर मेल खाते हैं, तो वे $\varphi$ को एक ही मान देते हैं; इसलिए $2^{n}$ पंक्तियों की सारणी सब कुछ कहती है। स्थापित होता है: 2. संपाती प्रमेयिका और सारणियाँ.
Fशब्दार्थीय प्रतिस्थापन. यदि $\theta \eqsem \theta'$ और $\chi'$ , $\chi$ में $\theta$ की एक उपस्थिति को $\theta'$ से प्रतिस्थापित करके प्राप्त होता है, तो $\chi \eqsem \chi'$ । स्थापित होता है: 7. शब्दार्थीय प्रतिस्थापन प्रमेय.
Gतुल्यता के नियम. स्वेच्छ सूत्रों के लिए दोहरा निषेध, वर्गसमता, क्रमविनिमेयता, साहचर्यता, वितरण, डी मॉर्गन, अवशोषण, तत्समक नियम, प्रभाविता नियम, मध्य-परिहार नियम और अव्याघात नियम। स्थापित होता है: 9. तुल्यता के नियम.
Hमान प्रमेयिका. $v\left( \bigwedge_{i=1}^{n} \varphi_i \right) = 1$ यदि और केवल यदि $v(\varphi_i) = 1$ सभी $i$ के लिए; $v\left( \bigvee_{i=1}^{n} \varphi_i \right) = 1$ यदि और केवल यदि $v(\varphi_i) = 1$ किसी $i$ के लिए। स्थापित होता है: 10. मान प्रमेयिका और अनुकूलता.

खंड 1 सूत्र का मान
- संयुक्त निषेध के खंड से किसी सूत्र का मान निकालना और संक्षेपणों से प्रत्येक व्युत्पन्न संयोजक का मान प्राप्त करना।
- संपाती प्रमेयिका सिद्ध करना और उससे यह उचित ठहराना कि $2^{n}$ पंक्तियों की सारणी पर्याप्त है।
- $\not\models \varphi$ को व्याघात से भ्रमित किए बिना सूत्रों और समुच्चयों का वर्गीकरण करना, और खंडन करने वाला मान-नियतन खोजकर वैधता का निर्णय करना।
1. मान-नियतन का विस्तार. प्रत्येक मान-नियतन $v$ , खंड $v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))$ के द्वारा सभी सूत्रों तक अद्वितीय रूप से विस्तृत होता है; संक्षेपणों को खोलकर $\neg$ , $\vee$ , $\wedge$ , $\rightarrow$ , $\leftrightarrow$ और $\veebar$ का मान निकाला जाता है।
  आधार: A (अद्वितीय पठनीयता और पुनरावर्तन), C (आधिकारिक संक्षेपण). सिद्ध किया गया: प्रस्तावात्मक तर्क का अर्थविज्ञान.
2. संपाती प्रमेयिका और सारणियाँ. यदि $v$ और $v'$ , $V(\varphi)$ पर मेल खाते हैं, तो $v(\varphi) = v'(\varphi)$ , जटिलता पर आगमन से; अतः सभी मान-नियतनों में $\varphi$ के मान ठीक वही हैं जो उसकी सारणी की $2^{n}$ पंक्तियों में हैं।
  उपयोग करती है: 1. मान-नियतन का विस्तार. आधार: B (आगमन). सिद्ध किया गया: प्रस्तावात्मक तर्क का अर्थविज्ञान.
3. वर्गीकरण और निर्णय. प्रत्येक सूत्र ठीक एक है: वैध, आकस्मिक या व्याघात; $\varphi$ वैध है यदि और केवल यदि $\neg\varphi$ व्याघात है, और व्याघात है यदि और केवल यदि $\models \neg\varphi$ । $\top$ और मध्य-परिहार नियम वैध हैं, $\bot$ व्याघात है, और वैधता तथा संतोषणीयता का निर्णय पंक्तियों को एक-एक करके देखकर होता है।
  आधार: D (संयोजकों के मान), E (संपाती प्रमेयिका). सिद्ध किया गया: प्रस्तावात्मक तर्क का अर्थविज्ञान.
खंड 2 परिणाम और तुल्यता
- परिमित या अनंत समुच्चयों से परिणाम का निर्णय करना, कोई प्रति-मॉडल प्रस्तुत करके या यह सिद्ध करके कि वह नहीं है।
- शब्दार्थीय निगमन प्रमेय और परिणाम को असंतोषणीयता पर ले आने की विधि लागू करना।
- एक उपस्थिति के प्रतिस्थापन को समरूप स्थापन से अलग करना और दोनों को जटिलता पर आगमन से सिद्ध करना।
- प्रत्येक नियम का सही नाम लेते हुए शृंखलाओं से तुल्यताएँ स्थापित करना।
1. परिणाम और उसके गुण. $\Gamma \models \varphi$ जब $\Gamma$ को संतुष्ट करने वाला प्रत्येक मान-नियतन $\varphi$ को संतुष्ट करता है; $\emptyset \models \varphi$ यदि और केवल यदि $\models \varphi$ ; स्वतुल्यता, एकदिष्टता, कर्तन और संक्रामकता मान्य हैं, और असंतोषणीय समुच्चय का परिणाम हर सूत्र है।
  उपयोग करती है: 3. वर्गीकरण और निर्णय. सिद्ध किया गया: शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता.
2. शब्दार्थीय निगमन और असंतोषणीयता. $\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)$ सोपाधिक की एकमात्र असत्य पंक्ति से; $\{\varphi_1, \ldots, \varphi_n\} \models \psi \Leftrightarrow\; \models (\varphi_1 \rightarrow (\varphi_2 \rightarrow \cdots (\varphi_n \rightarrow \psi) \cdots))$ ; और $\Gamma \models \varphi$ यदि और केवल यदि $\Gamma \cup \{\neg\varphi\}$ असंतोषणीय है।
  उपयोग करती है: 4. परिणाम और उसके गुण. आधार: D (संयोजकों के मान). सिद्ध किया गया: शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता.
3. शब्दार्थीय तुल्यता. $\varphi \eqsem \psi$ यदि और केवल यदि $\varphi \models \psi$ और $\psi \models \varphi$ , और यदि और केवल यदि $\models (\varphi \leftrightarrow \psi)$ ; तुल्यता स्वतुल्य, सममित और संक्रामक है, और दो तुल्य सूत्र आधार-वाक्यों और निष्कर्षों के रूप में परस्पर बदले जा सकते हैं।
  उपयोग करती है: 4. परिणाम और उसके गुण. आधार: D (संयोजकों के मान). सिद्ध किया गया: शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता.
4. शब्दार्थीय प्रतिस्थापन प्रमेय. यदि $\theta \eqsem \theta'$ , तो $\chi$ में $\theta$ की एक उपस्थिति को, पूर्ण उपस्थिति सहित, $\theta'$ से प्रतिस्थापित करने पर $\chi$ के तुल्य सूत्र मिलता है; और सभी उपस्थितियों में एक साथ प्रतिस्थापन से भी।
  उपयोग करती है: 1. मान-नियतन का विस्तार, 6. शब्दार्थीय तुल्यता. आधार: A (अद्वितीय पठनीयता और पुनरावर्तन), B (आगमन). सिद्ध किया गया: शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता.
5. समरूप स्थापन. यदि $w(v_n) = v(\sigma(v_n))$ , तो $v(\sigma(\chi)) = w(\chi)$ ; अतः यदि $\models \chi$ , तो $\models \sigma(\chi)$ भी, और स्थापन तुल्यता और परिणाम को संरक्षित करता है, पर संतोषणीयता को नहीं, न आकस्मिकता को।
  उपयोग करती है: 1. मान-नियतन का विस्तार, 4. परिणाम और उसके गुण, 6. शब्दार्थीय तुल्यता. आधार: A (अद्वितीय पठनीयता और पुनरावर्तन), B (आगमन). सिद्ध किया गया: शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता.
6. तुल्यता के नियम. सूची के नियम $a^{2} = a$ के साथ बहुपदों की सर्वसमिकाओं के रूप में जाँचे जाते हैं; प्रतिस्थापन और संक्रामकता से वे उपसूत्रों पर लागू होते हैं और शृंखलाबद्ध होते हैं।
  उपयोग करती है: 3. वर्गीकरण और निर्णय, 6. शब्दार्थीय तुल्यता. आधार: D (संयोजकों के मान), F (शब्दार्थीय प्रतिस्थापन). सिद्ध किया गया: शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता.
खंड 3 किसी भी संख्या के पदों के नियम
- $n$ पदों के संयोजनों और वियोजनों को बाईं ओर साहचर्य वाली प्रतीक-शृंखलाओं के रूप में खोलना और उनका मान निकालना।
- पदों की संख्या पर आगमन से व्यापकीकृत साहचर्यता, क्रम से स्वतंत्रता और डी मॉर्गन के व्यापकीकृत नियम सिद्ध करना।
- दो सूचकांकों पर आगमन से व्यापकीकृत वितरण सिद्ध करना और उससे उत्पन्न पदों को गिनना।
1. मान प्रमेयिका और अनुकूलता. यदि $\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')$ ; $n$ पदों का संयोजन $1$ है यदि और केवल यदि सभी पद $1$ हैं, वियोजन यदि और केवल यदि कोई एक पद $1$ है, और तुल्य पद तुल्य संयोजन और वियोजन देते हैं।
  उपयोग करती है: 6. शब्दार्थीय तुल्यता. आधार: D (संयोजकों के मान), B (आगमन). सिद्ध किया गया: डी मॉर्गन के और वितरण के व्यापकीकृत नियम.
2. साहचर्यता और क्रम. दो सूचियों के संयोजनों का संयोजन उनके संयोजित रूप के संयोजन के तुल्य है, और हर समूहन बाईं ओर साहचर्य वाले के तुल्य है; एक ही पदों वाली दो सूचियाँ तुल्य संयोजन और वियोजन देती हैं, क्रम और पुनरावृत्ति जो भी हों।
  आधार: H (मान प्रमेयिका), G (तुल्यता के नियम), B (आगमन). सिद्ध किया गया: डी मॉर्गन के और वितरण के व्यापकीकृत नियम.
3. डी मॉर्गन के व्यापकीकृत नियम. $\neg \bigwedge_{i=1}^{n} \varphi_i \eqsem \bigvee_{i=1}^{n} \neg\varphi_i$ और $\neg \bigvee_{i=1}^{n} \varphi_i \eqsem \bigwedge_{i=1}^{n} \neg\varphi_i$ : दो पदों का नियम अंतिम जोड़ पर लागू होता है और आगमन परिकल्पना भीतर बचे भाग पर।
  आधार: H (मान प्रमेयिका), G (तुल्यता के नियम), B (आगमन). सिद्ध किया गया: डी मॉर्गन के और वितरण के व्यापकीकृत नियम.
4. व्यापकीकृत वितरण. $\left( \bigvee_{i=1}^{n} \varphi_i \right) \wedge \left( \bigvee_{j=1}^{m} \psi_j \right) \eqsem \bigvee_{i,j} (\varphi_i \wedge \psi_j)$ , $nm$ पदों के साथ, शब्दकोशीय क्रम में; और द्वैत नियम, जो दो संयोजनों के वियोजन का वितरण करता है, डी मॉर्गन के नियम से।
  उपयोग करती है: 11. साहचर्यता और क्रम, 12. डी मॉर्गन के व्यापकीकृत नियम. आधार: H (मान प्रमेयिका), G (तुल्यता के नियम), B (आगमन). सिद्ध किया गया: डी मॉर्गन के और वितरण के व्यापकीकृत नियम.
खंड 4 सत्यता फलन
- सत्यता फलन गिनना और दो सूत्रों द्वारा निरूपित फलनों की तुलना करके तुल्यता का निर्णय करना।
- किसी सारणी का सूत्र बनाना और किसी भी फलन को केवल संयुक्त निषेध से लिखना।
- संयुक्त निषेध की कसौटी से संयोजकों के किसी समुच्चय की पर्याप्तता, या उसके सूत्रों द्वारा संरक्षित किसी गुण से उसकी अपर्याप्तता सिद्ध करना।
1. सत्यता फलन. $2^{2^{n}}$ सत्यता फलन हैं, प्रत्येक $n$ संकार्यों का; जिस सूत्र के चर $v_1, \ldots, v_n$ में से हैं, वह उनमें से ठीक एक को, $f_\varphi$ को, निरूपित करता है, और $\varphi \eqsem \psi \Leftrightarrow f_\varphi = f_\psi$ ।
  उपयोग करती है: 6. शब्दार्थीय तुल्यता. आधार: E (संपाती प्रमेयिका). सिद्ध किया गया: फलनात्मक पूर्णता.
2. फलनात्मक पूर्णता. किसी पंक्ति का संयोजन ठीक अपनी पंक्ति में $1$ है; उन पंक्तियों के संयोजनों का वियोजन जिनमें $f$ का मान $1$ है, या $(v_{1} \wedge \neg v_{1})$ यदि कोई ऐसी पंक्ति न हो, $f$ को निरूपित करता है; और प्रत्येक सूत्र अपनी सारणी के सूत्र के तुल्य है।
  उपयोग करती है: 14. सत्यता फलन. आधार: H (मान प्रमेयिका), D (संयोजकों के मान). सिद्ध किया गया: फलनात्मक पूर्णता.
3. पर्याप्त और अपर्याप्त समुच्चय. संयुक्त निषेध पर्याप्त है, क्योंकि संक्षेपण खोले जाते हैं; यदि $K$ के सूत्र $(1 - a)(1 - b)$ के मान को व्यक्त करते हैं, तो समुच्चय $K$ पर्याप्त है, जैसे $\{\neg, \wedge\}$ , $\{\neg, \vee\}$ , $\{\neg, \rightarrow\}$ और $\{\uparrow\}$ ; $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ के सूत्रों का मान $1$ होता है जब सभी चरों का मान $1$ हो, और यह समुच्चय पर्याप्त नहीं है।
  उपयोग करती है: 15. फलनात्मक पूर्णता. आधार: C (आधिकारिक संक्षेपण), B (आगमन), D (संयोजकों के मान). सिद्ध किया गया: फलनात्मक पूर्णता.
खंड 5 प्रसामान्य रूप
- लिटरल, उपवाक्य और प्रसामान्य रूप पहचानना, प्रतीक-शृंखला के आकार को उसके मान से अलग करते हुए।
- सारणी से विहित रूप बनाना और उनकी अद्वितीयता सिद्ध करना।
- दोनों की माँग करने वाली आगमन परिकल्पना के साथ आगमन से प्रसामान्य रूपों का अस्तित्व सिद्ध करना।
- संयोजक रूप की वैधता और वियोजक रूप की संतोषणीयता का एक नज़र में निर्णय करना।
1. लिटरल और द्वैतता. $\neg\ell \eqsem \ell^{*}$ ; प्राथमिक संयोजन संतोषणीय है यदि और केवल यदि उसमें कोई पूरक युग्म न हो, और उपवाक्य वैध है यदि और केवल यदि उसमें कोई पूरक युग्म हो; किसी प्रसामान्य रूप का निषेध उसके द्वैत रूप के तुल्य है, अतः $\varphi$ का संयोजक रूप $\neg\varphi$ के वियोजक रूप का द्वैत रूप है।
  उपयोग करती है: 12. डी मॉर्गन के व्यापकीकृत नियम. आधार: G (तुल्यता के नियम), F (शब्दार्थीय प्रतिस्थापन), H (मान प्रमेयिका). सिद्ध किया गया: प्रसामान्य रूप.
2. विहित रूप. यदि $\varphi$ संतोषणीय है, तो वह अपने विहित वियोजक रूप के तुल्य है, और यदि वैध नहीं है, तो अपने विहित संयोजक रूप के; चर $v_1, \ldots, v_n$ निश्चित होने पर, दो विहित रूप तुल्य हैं यदि और केवल यदि वे एक ही प्रतीक-शृंखला हैं, और दो संतोषणीय सूत्र तुल्य हैं यदि और केवल यदि उनका विहित वियोजक रूप एक ही है।
  उपयोग करती है: 15. फलनात्मक पूर्णता, 17. लिटरल और द्वैतता. आधार: H (मान प्रमेयिका), E (संपाती प्रमेयिका). सिद्ध किया गया: प्रसामान्य रूप.
3. आगमन से अस्तित्व. $(\varphi \downarrow \psi) \eqsem (\neg\varphi \wedge \neg\psi)$ ; प्रसामान्य रूप संयोजन और वियोजन के अंतर्गत संवृत हैं, संयोजन का वियोजक रूप और वियोजन का संयोजक रूप व्यापकीकृत वितरण से; आगमन से, दोनों रूपों पर आगमन परिकल्पना के साथ, प्रत्येक सूत्र का एक वियोजक रूप और एक संयोजक रूप होता है।
  उपयोग करती है: 17. लिटरल और द्वैतता, 11. साहचर्यता और क्रम, 13. व्यापकीकृत वितरण. आधार: B (आगमन), F (शब्दार्थीय प्रतिस्थापन). सिद्ध किया गया: प्रसामान्य रूप.
4. जो एक नज़र में दिखता है. कोई संयोजक रूप वैध है यदि और केवल यदि उसके प्रत्येक उपवाक्य में कोई पूरक युग्म हो; कोई वियोजक रूप संतोषणीय है यदि और केवल यदि किसी प्राथमिक संयोजन में कोई भी पूरक युग्म न हो।
  उपयोग करती है: 17. लिटरल और द्वैतता. आधार: H (मान प्रमेयिका). सिद्ध किया गया: प्रसामान्य रूप.
खंड 6 कलन-विधि और परिपथ
- पुनर्लेखन की कलन-विधि लागू करना और द्विसोपाधिक के निरसन का उपयुक्त तरीका चुनना।
- उसकी शुद्धता और समापन सिद्ध करना और समझाना कि संयोजक रूप घातीय रूप से क्यों बढ़ सकता है।
- किसी ब्लैक बॉक्स के प्रसामान्य रूप प्राप्त करना और सरल करना, और उनसे स्विचों के परिपथ बनाना।
1. कलन-विधि की शुद्धता और समापन. किसी उपलेखन को तुल्य उपलेखन से प्रतिस्थापित करने पर तुल्य लेखन मिलता है; प्रत्येक नियम एक तुल्यता है, और अलघुकरणीय लेखन किसी समूहन के साथ प्रसामान्य रूप है; माप $M_1$ , $M_2$ , $M_2(\neg\varphi) = 2^{M_2(\varphi)}$ के साथ, और $M_3$ , $M_3(\varphi \wedge \psi) = M_3(\varphi)\,M_3(\psi)$ के साथ, हर चरण में घटते हैं।
  उपयोग करती है: 19. आगमन से अस्तित्व, 11. साहचर्यता और क्रम. आधार: G (तुल्यता के नियम), D (संयोजकों के मान), B (आगमन). सिद्ध किया गया: प्रसामान्य रूपों की कलन-विधि और उसके अनुप्रयोग.
2. घातीय वृद्धि. $\bigvee_{i=1}^{n} (p_i \wedge q_i)$ एक ऐसे संयोजक रूप के तुल्य है जिसमें $2^{n}$ उपवाक्य हैं, और उसके तुल्य प्रत्येक संयोजक रूप में कम से कम $2^{n}$ अवैध उपवाक्य होते हैं।
  उपयोग करती है: 19. आगमन से अस्तित्व, 17. लिटरल और द्वैतता. आधार: H (मान प्रमेयिका). सिद्ध किया गया: प्रसामान्य रूपों की कलन-विधि और उसके अनुप्रयोग.
3. पड़ोसी पंक्तियाँ और परिपथ. $(\kappa \wedge \ell) \vee (\kappa \wedge \ell^{*}) \eqsem \kappa$ और द्वैत तुल्यता; श्रेणी-समांतर परिपथ अवस्था $v$ में चालन करता है यदि और केवल यदि $v(\varphi_C) = 1$ , और प्रत्येक सत्यता फलन को कोई परिपथ साकार करता है।
  उपयोग करती है: 15. फलनात्मक पूर्णता, 18. विहित रूप, 17. लिटरल और द्वैतता, 11. साहचर्यता और क्रम. आधार: G (तुल्यता के नियम), F (शब्दार्थीय प्रतिस्थापन), D (संयोजकों के मान), B (आगमन). सिद्ध किया गया: प्रसामान्य रूपों की कलन-विधि और उसके अनुप्रयोग.

अधिसिद्धांत की ओर. शृंखला वहाँ रुकती है जहाँ अर्थविज्ञान के पास सूत्रों के बारे में हर प्रश्न के लिए एक प्रक्रिया है। जानना बाकी है कि जो प्रत्येक मान-नियतन में सत्य है, क्या वह ठीक वही है जो प्रणाली में निगमित होता है: अगली इकाई दोनों अवधारणाओं की तुलना करेगी।

इस पाठ के शेष भाग में

पाठ्यक्रम के भीतर इकाई
समापन मूल्यांकन
चुनौतियाँ
अपने सभी संकार्यों का ध्यान रखने वाले फलन
सीढ़ी की बत्ती
निषेध और द्विसोपाधिक से क्या व्यक्त होता है
द्वैतता का सिद्धांत
वृद्धि के विरुद्ध नए चर
अंतर्वेशन प्रमेय

निःशुल्क खाते के साथ पढ़ना जारी रखें

यह पूरा पाठ और हर पाठ्यक्रम के पहले पाठ पढ़ने तथा अपनी प्रगति सहेजने के लिए अपना निःशुल्क खाता बनाएँ।

खाता बनाएँ साइन इन करें

पूरा पाठ्यक्रम पाएँ

इस पाठ का शेष भाग सदस्यता में शामिल है। सदस्यता के साथ आपको हर पाठ्यक्रम के सभी पाठ, उनके प्रश्नों और प्रमाणों के साथ, मिलते हैं।

खाता बनाएँ साइन इन करें