संहतता प्रमेय

पिछले पाठों से क्या उपयोग में आता है

यह पाठ लगभग पूरी तरह अर्थविज्ञान में काम करता है, और उससे निम्नलिखित का उपयोग करता है। एक मान-नियतन एक फलन $v\colon V \to \{0, 1\}$ है, जो समुच्चय $V$ पर, अर्थात् चरों $v_1, v_2, v_3, \ldots$ के समुच्चय पर, परिभाषित है और सभी सूत्रों तक एक ही प्रकार से विस्तारित होता है; एक मान-नियतन सूत्रों के एक समुच्चय $\Gamma$ को संतुष्ट करता है, $v \models \Gamma$, यदि वह उनमें से प्रत्येक को मान $1$ देता है, और $\Gamma$ संतोषणीय है यदि कोई मान-नियतन उसे संतुष्ट करता है, अन्यथा असंतोषणीय। यह सब प्रस्तावात्मक तर्क के अर्थविज्ञान पर पाठ में है, साथ ही इस पाठ का केंद्रीय उपकरण, संपाती प्रमेयिका: यदि दो मान-नियतन $\varphi$ के चरों पर, जो एक परिमित समुच्चय $V(\varphi)$ बनाते हैं, मेल खाते हैं, तो वे $\varphi$ को एक ही मान देते हैं।

शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता पर पाठ से $\Gamma \models \varphi$ की परिभाषा (प्रत्येक मान-नियतन जो $\Gamma$ को संतुष्ट करता है, $\varphi$ को संतुष्ट करता है), उसके संरचनात्मक गुण, विशेषकर एकदिष्टता (यदि $\Gamma \subseteq \Delta$ और $\Gamma \models \varphi$, तो $\Delta \models \varphi$) और पाँचवाँ गुण (एक असंतोषणीय समुच्चय का परिणाम प्रत्येक सूत्र है), तथा परिणाम और असंतोषणीयता का प्रमेय उपयोग में आते हैं: $\Gamma \models \varphi$ यदि और केवल यदि $\Gamma \cup \{\neg\varphi\}$ असंतोषणीय है। डी मॉर्गन के और वितरण के व्यापकीकृत नियमों पर पाठ से मान प्रमेयिका उपयोग में आती है: $\bigwedge_{i=1}^{n} \varphi_i$ का मान $1$ है यदि और केवल यदि उसके सभी पदों का मान $1$ है, और $\bigvee_{i=1}^{n} \varphi_i$ का, यदि और केवल यदि किसी पद का मान $1$ है। अंत में, $\top := (v_1 \rightarrow v_1)$ एक पुनरुक्ति है और $\bot := \neg\top$ एक व्याघात।

निगमन की ओर से, औपचारिक निगमन प्रणालियों पर पाठ ने एकदिष्टता (Mon: यदि $\Gamma \subseteq \Delta$ और $\Gamma \vdash \varphi$, तो $\Delta \vdash \varphi$) और परिमितता (Fin: यदि $\Gamma \vdash \varphi$, तो कोई परिमित उपसमुच्चय $\Gamma_0$, जो $\Gamma$ का उपसमुच्चय है, ऐसा है कि $\Gamma_0 \vdash \varphi$) सिद्ध कीं, और निगमन की चार तकनीकों पर पाठ ने जाँचा कि दोनों पाठ्यक्रम की प्रणाली (अभिगृहीत-योजनाएँ A1, A2 और A3, मोडस पोनेन्स और दोहरे निषेध का प्रतिस्थापन, RDN) में लागू होती हैं, जिसकी ओर आगे से प्रतीक $\vdash$ संकेत करता है। अंत में, सुदृढ़ता और पूर्णता पर पाठ ने सुदृढ़ता प्रमेय ($\Gamma \vdash \varphi$, $\Gamma \models \varphi$ को निहित करता है, प्रत्येक $\Gamma$ के लिए) और आधार-वाक्यों के परिमित समुच्चयों के लिए पूर्णता सिद्ध की: यदि $\{\gamma_1, \ldots, \gamma_k\} \models \varphi$, तो $\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi$।