अधिसिद्धांत: परिचय

सारांश

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

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

इकाई के तीन पाठों का क्रम बताना, यह समझाना कि हर पाठ पिछले पाठ के कौन-से परिणाम उपयोग करता है, और यह तर्कसंगत ठहराना कि संहतता को, एक शब्दार्थीय युक्ति से, प्रबल पूर्णता से पहले क्यों सिद्ध किया जाता है।
पाठ्यक्रम के दो पहलुओं में भेद करना, निगम्यता $\Gamma \vdash \varphi$ , जो अस्तित्वपरक और परिमित है, और शब्दार्थीय परिणाम $\Gamma \models \varphi$ , जो अनंत मान-नियतनों पर सार्विक है, तथा सुदृढ़ता और पूर्णता को उसकी तीन कोटियों में कथित करना।
यह समझाना कि दोनों संबंधों का मेल एक-एक उदाहरण से स्थापित क्यों नहीं किया जा सकता, बल्कि केवल अधिप्रमेयों से, और पहचानना कि हर उपपत्ति पिछली इकाइयों के कौन-से उपकरण (आगमन, स्थिति-भेद से उपपत्ति, दोनों निगमन प्रमेय, संपाती प्रमेयिका, संयोजक रूप) उपयोग करेगी।
इकाई के निगमनों पर निगमन और शब्दार्थीय युक्तियाँ पढ़ना, हर चरण में यह भेद करते हुए कि बात किस संबंध की है, और प्रवेश मूल्यांकन से आरंभ करके अध्ययन को व्यवस्थित करना।

प्रवेश मूल्यांकन

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

प्रवेश मूल्यांकन

इकाई शुरू करने से पहले अपना आरंभ बिंदु मापें। यह एक छोटा स्व-मूल्यांकन है: इस पर अंक नहीं दिए जाते और इसका परिणाम केवल आपके ब्राउज़र में रहता है।

प्रश्न 1पिछली इकाइयों से $\Gamma \models \varphi$ का अर्थ क्या है?
यह कि $\Gamma$ के सभी सूत्रों को संतुष्ट करने वाला हर मान-नियतन $\varphi$ को संतुष्ट करता है।
यह कि $\varphi$ का $\Gamma$ से एक निगमन अस्तित्व में है।
यह कि कोई मान-नियतन $\Gamma$ और $\varphi$ को एक साथ संतुष्ट करता है।
यह कि $\varphi$ , $\Gamma$ के किसी एक सूत्र का, अकेले लिए जाने पर, परिणाम है।
प्रश्न 2पिछली इकाइयों सेनिम्नलिखित में से कौन-सा कथन $\Gamma \models \varphi$ के तुल्य है?
यह कि $\Gamma \cup \{\neg\varphi\}$ असंतोषणीय है।
यह कि $\Gamma \cup \{\varphi\}$ संतोषणीय है।
यह कि $\Gamma \cup \{\neg\varphi\}$ संतोषणीय है।
यह कि $\neg\varphi$ असंतोषणीय है।
प्रश्न 3पिछली इकाइयों सेयदि कोई मान-नियतन $v$ , $\alpha$ को मान $1$ देता है, तो वह $(\alpha \downarrow \beta)$ को कौन-सा मान देता है?
$0$ , $\beta$ का मान चाहे जो हो।
यह $\beta$ पर निर्भर है: इसका मान $1$ है यदि $\beta$ का मान $0$ है।
$1 - v(\beta)$ ।
$1$ , क्योंकि घटकों में से एक सत्य है।
प्रश्न 4पिछली इकाइयों से $\varphi$ के चर $v_{2}$ और $v_{7}$ हैं। दो मान-नियतन $v$ और $w$ , $v_{2}$ और $v_{7}$ को समान मान देते हैं, और शेष सभी चरों को विपरीत मान। यदि $v(\varphi) = 1$ , तो $w(\varphi)$ के बारे में क्या कहा जा सकता है?
यह कि $w(\varphi) = 1$ ।
कुछ नहीं, क्योंकि $v$ और $w$ अनंत चरों में भिन्न हैं।
यह कि $w(\varphi) = 0$ , क्योंकि $w$ , $v$ के लगभग सभी मानों को उलट देता है।
यह कि $w(\varphi) = 1$ केवल तब, जब $v$ और $w$ , $v_{1}, \ldots, v_{6}$ पर भी मेल खाते हों।
प्रश्न 5पिछली इकाइयों सेमान लीजिए $\Gamma$ सूत्रों का एक अनंत समुच्चय है जिसके लिए $\Gamma \vdash \varphi$ । क्या कहा जा सकता है?
यह कि $\Gamma$ का कोई परिमित उपसमुच्चय $\varphi$ को निगमित करता है।
यह कि $\varphi$ एक प्रमेय है।
यह कि निगमन $\Gamma$ के सभी सूत्रों का उपयोग करता है।
संहतता प्रमेय के बिना कुछ नहीं, क्योंकि $\Gamma$ अनंत है।
प्रश्न 6पिछली इकाइयों सेज्ञात है कि $\Gamma \cup \{p\} \vdash \chi$ और कि $\Gamma \cup \{\neg p\} \vdash \chi$ । स्थिति-भेद से उपपत्ति क्या निष्कर्ष निकालने देती है?
यह कि $\Gamma \vdash \chi$ ।
कुछ नहीं, जब तक यह ज्ञात न हो कि $\Gamma$ , $p$ को निगमित करता है या $\neg p$ को।
यह कि $\Gamma \vdash (p \leftrightarrow \chi)$ ।
केवल यह कि $\Gamma \cup \{p, \neg p\} \vdash \chi$ ।
प्रश्न 7पाठ्यक्रम की प्रणाली सुदृढ़ है। यह गुण क्या कहता है?
यह कि हर समुच्चय $\Gamma$ के लिए, यदि $\Gamma \vdash \varphi$ , तो $\Gamma \models \varphi$ ।
यह कि यदि $\Gamma \models \varphi$ , तो $\Gamma \vdash \varphi$ ।
यह कि कोई ऐसा सूत्र $\varphi$ नहीं है जिसके लिए $\vdash \varphi$ और $\vdash \neg\varphi$ ।
यह कि हर सत्य सूत्र एक प्रमेय है।
प्रश्न 8मान लीजिए $v$ वह मान-नियतन है जो $1$ को $p$ पर और $0$ को $q$ पर रखता है। काल्मार प्रमेयिका, चरों $p$ और $q$ के साथ, सूत्र $(p \leftrightarrow q)$ के लिए क्या कहती है?
यह कि $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$ ।
यह कि $\{p, \neg q\} \vdash (p \leftrightarrow q)$ ।
यह कि $\{p, q\} \vdash \neg(p \leftrightarrow q)$ ।
यह कि $\vdash \neg(p \leftrightarrow q)$ ।
प्रश्न 9क्या कोई निगमन प्रणाली पूर्ण हुए बिना सुदृढ़ हो सकती है?
हाँ: लुकासिएविच प्रणाली, RDN नियम के बिना, सुदृढ़ है और पुनरुक्ति $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ को निगमित नहीं करती।
नहीं: सुदृढ़ता और पूर्णता एक-दूसरे से निगमित होती हैं।
नहीं: जिस प्रणाली के अभिगृहीत पुनरुक्तियाँ हैं, वह सभी पुनरुक्तियाँ निगमित करती है।
हाँ, पर केवल यदि प्रणाली असंगत हो।
प्रश्न 10संहतता प्रमेय क्या कहता है?
यह कि सूत्रों का एक समुच्चय संतोषणीय है यदि और केवल यदि उसका हर परिमित उपसमुच्चय संतोषणीय है।
यह कि सूत्रों का एक समुच्चय संतोषणीय है यदि और केवल यदि उसका हर सूत्र संतोषणीय है।
यह कि सूत्रों का हर अनंत समुच्चय संतोषणीय है।
यह कि एक समुच्चय संतोषणीय है यदि उसका कोई परिमित उपसमुच्चय संतोषणीय है।
प्रश्न 11मान लीजिए $\Gamma$ सूत्रों का एक अनंत समुच्चय है जिसके लिए $\Gamma \models \varphi$ । संहतता क्या सुनिश्चित करती है?
यह कि $\Gamma_{0} \models \varphi$ , जहाँ $\Gamma_{0}$ , $\Gamma$ का कोई परिमित उपसमुच्चय है।
यह कि $\varphi$ , $\Gamma$ के किसी एक सूत्र का, अकेले लिए जाने पर, परिणाम है।
यह कि $\varphi$ , $\Gamma$ के हर परिमित उपसमुच्चय का परिणाम है।
यह कि $\varphi$ वैध है।
प्रश्न 12पहला पाठ आधार-वाक्यों के परिमित समुच्चयों के लिए पूर्णता सिद्ध करता है। उसे किसी अनंत समुच्चय $\Gamma$ तक बढ़ाने के लिए निगमन की परिमितता पर्याप्त क्यों नहीं है?
क्योंकि परिमितता $\Gamma \vdash \varphi$ के बारे में बोलती है, और हमारे पास $\Gamma \models \varphi$ है: आवश्यक यह है कि परिणाम, न कि निगमन, किसी परिमित भाग तक घटे, और यही संहतता है।
पर्याप्त है: यदि $\Gamma \models \varphi$ , तो परिमितता एक परिमित $\Gamma_{0}$ देती है जिसके लिए $\Gamma_{0} \models \varphi$ ।
क्योंकि काल्मार प्रमेयिका अनंत चरों वाले सूत्रों के लिए सत्य नहीं है।
क्योंकि आधार-वाक्यों के अनंत समुच्चयों के लिए पूर्णता असत्य है।
प्रश्न 13उपवाक्यों $\{p, \neg q, r\}$ और $\{q, s\}$ का विभेदक क्या है?
$\{p, r, s\}$ ।
$\{p, \neg q, r, q, s\}$ ।
$\{p, r\}$ ।
उनका कोई विभेदक नहीं, क्योंकि उनमें कोई लिटरल साझा नहीं है।
प्रश्न 14विभेदन से यह निर्णय करने के लिए कि क्या $\{(p \vee q), \neg p\} \models q$ , किस उपवाक्य समुच्चय का खंडन करने का प्रयास किया जाता है?
$\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$ ।
$\{\{p, q\}, \{\neg p\}, \{q\}\}$ ।
$\{\{p, q\}, \{\neg p\}\}$ ।
$\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$ ।
प्रश्न 15क्या रिक्त उपवाक्य $\Box$ की, समुच्चय $\{\{p, q\}, \{\neg p, \neg q\}\}$ से, विभेदन द्वारा व्युत्पत्ति हो सकती है?
नहीं: समुच्चय संतोषणीय है, और विभेदन सुदृढ़ है।
हाँ, एक ही चरण में, दोनों पूरक युग्मों को एक साथ हटाकर।
हाँ, दो चरणों में: पहले $p$ पर और फिर $q$ पर।
नहीं, क्योंकि दोनों उपवाक्यों में से कोई एकल नहीं है।

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

इकाई की विषय-वस्तु
पाठ्यक्रम में इकाई का स्थान
एक ही संबंध के दो पहलू
संहतता प्रबल पूर्णता से पहले क्यों आती है
एक तीसरा मार्ग
क्या ज्ञात माना जाता है
इकाई जो समस्या हल करती है
इकाई का अध्ययन कैसे करें
यह कहाँ ले जाती है

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

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

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

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

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

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