फलनात्मक पूर्णता

सारांश

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

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

$n$ संकार्यों वाले सत्यता फलनों की गिनती करना और सूत्रों द्वारा निरूपित फलनों से यह तय करना कि दो सूत्र कब तुल्य हैं।
किसी सत्यता फलन की सारणी से उसे निरूपित करने वाला सूत्र बनाना और, आवश्यकता होने पर, कोई छोटा तुल्य सूत्र खोजना।
यह समझाना कि पाठ्यक्रम की भाषा में अकेला संयुक्त निषेध क्यों पर्याप्त है, और केवल संयुक्त निषेध से किसी दिए गए फलन को निरूपित करने वाला सूत्र लिखना।
यह सिद्ध करना कि संयोजकों का कोई समुच्चय पर्याप्त है, उसके सूत्रों से संयुक्त निषेध को निरूपित करके।
यह सिद्ध करना कि संयोजकों का कोई समुच्चय पर्याप्त नहीं है, ऐसे गुण के द्वारा जिसे उसके सभी सूत्र संरक्षित करते हैं।

सत्यता फलन

प्रस्तावात्मक तर्क का अर्थविज्ञान पर पाठ ने प्रत्येक मान-नियतन में प्रत्येक सूत्र को एक सत्यता मान दिया और दिखाया कि वह मान केवल सूत्र में आने वाले चरों के मानों पर निर्भर करता है। इसलिए $n$ चरों वाले प्रत्येक सूत्र की $2^{n}$ पंक्तियों वाली सत्यता सारणी होती है। इस पाठ का प्रश्न विलोम है: कोई भी सारणी दी हो, अर्थात $2^{n}$ पंक्तियों के सामने मनमाने ढंग से लिखा 1 और 0 का कोई स्तंभ, तो क्या कोई ऐसा सूत्र है जिसकी वह सारणी हो? यदि हर सारणी के लिए ऐसा है, तो भाषा में अभिव्यक्ति की कोई कमी नहीं है: $n$ कथनों के सत्यता मानों के बारे में, उन मानों के अनुसार, जो कुछ भी कहा जा सकता है, वह एक सूत्र से कहा जा सकता है। और चूँकि इस पाठ्यक्रम में प्रत्येक संयुक्त सूत्र एक संयुक्त निषेध है, उत्तर यह भी बताता है कि क्या सब कुछ कहने के लिए एक अकेला संयोजक पर्याप्त है।

पिछले पाठों से क्या लिया जाता है

मान-नियतन एक फलन $v$ है, चरों के समुच्चय $\{v_1, v_2, \ldots\}$ से $\{0, 1\}$ में, जहाँ $1$ सत्य को और $0$ असत्य को दर्शाता है; सभी सूत्रों पर उसका विस्तार भी $v$ लिखा जाता है और पुनरावर्ती परिभाषा से निर्धारित होता है: $v((\varphi \downarrow \psi)) = 1$ यदि और केवल यदि $v(\varphi) = 0$ और $v(\psi) = 0$ । उसी पाठ ने, व्युत्पन्न संयोजकों के मान के प्रमेय में, आधिकारिक संक्षेपणों से प्रत्येक संयोजक का मान निकाला; योगों और गुणनफलों के रूप में लिखने पर, प्रत्येक मान-नियतन $v$ और सभी सूत्रों $\varphi$ , $\psi$ के लिए, वे ये हैं:

v(\neg\varphi) = 1 - v(\varphi), \qquad v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), \qquad v((\varphi \vee \psi)) = v(\varphi) + v(\psi) - v(\varphi)\,v(\psi)

v((\varphi \rightarrow \psi)) = 1 - v(\varphi) + v(\varphi)\,v(\psi), \qquad v((\varphi \downarrow \psi)) = (1 - v(\varphi))\,(1 - v(\psi))

इसके अतिरिक्त, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$ , जो $1$ के बराबर है यदि और केवल यदि $v(\varphi) = v(\psi)$ , और $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$ , जो $1$ के बराबर है यदि और केवल यदि $v(\varphi) \neq v(\psi)$ । चूँकि मान $0$ या $1$ होते हैं, किसी मान का वर्ग वही मान है ( $v(\varphi)\,v(\varphi) = v(\varphi)$ ), और मानों का गुणनफल $1$ के बराबर है यदि और केवल यदि प्रत्येक गुणनखंड $1$ के बराबर हो; इन दो प्रेक्षणों का प्रयोग बिना दोहराए किया जाएगा। संपाती प्रमेयिका का भी प्रयोग किया जाएगा: यदि दो मान-नियतन $\varphi$ के चरों पर, अर्थात $\varphi$ के उन उपसूत्रों पर जो चर हैं, सहमत हों, तो वे $\varphi$ को एक ही मान देते हैं। शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता पर पाठ से शब्दार्थीय तुल्यता ली जाती है: $\varphi \eqsem \psi$ का अर्थ है कि $v(\varphi) = v(\psi)$ , प्रत्येक मान-नियतन $v$ के लिए। अंत में, औपचारिकीकरण पर पाठ की अक्षरों वाली परिपाटी लागू रहती है: $p$ , $q$ और $r$ क्रमशः चर $v_1$ , $v_2$ और $v_3$ को दर्शाते हैं।

सत्यता फलन और उनकी गिनती

मान लीजिए $n$ एक प्राकृत संख्या है। $n$ मानों की एक पंक्ति एक अनुक्रम $a = (a_1, \ldots, a_n)$ है, जिसमें प्रत्येक $a_i$ , $0$ या $1$ है; ऐसी सभी पंक्तियों के समुच्चय को $\{0, 1\}^{n}$ लिखा जाता है। $n$ संकार्यों वाला एक सत्यता फलन एक फलन

f\colon \{0, 1\}^{n} \to \{0, 1\}

है, जो प्रत्येक पंक्ति को एक सत्यता मान देता है। इसे सारणी के रूप में दिखाया जाता है: पंक्तियाँ सारणी के क्रम में लिखी जाती हैं, उस पंक्ति से आरंभ करके जिसके सभी मान $1$ हैं (दो संकार्यों के लिए $1\,1$ , $1\,0$ , $0\,1$ , $0\,0$ ), और प्रत्येक के सामने उसका मान लिखा जाता है। इस प्रकार सत्यता फलन बिना सूत्र की सत्यता सारणी है: सबसे दाहिना स्तंभ, जिसके शीर्ष पर कुछ नहीं लिखा है।

साध्य

2^{2^{n}}

सत्यता फलन हैं, जिनके

n

संकार्य हैं

प्रत्येक प्राकृत संख्या $n$ के लिए, ठीक $2^{n}$ पंक्तियाँ हैं, जिनमें $n$ मान हैं, और $2^{2^{n}}$ सत्यता फलन हैं, जिनके $n$ संकार्य हैं।

प्रमाण

$\dato{filas}{1\,0\,1 \;\; \longmapsto \;\; \sigI\sigO\sigI}$
पंक्ति $n$ प्रतीकों का एक अनुक्रम है, जिनमें से प्रत्येक $1$ या $0$ है। $1$ के स्थान पर एक चक्रिका और $0$ के स्थान पर एक वृत्त लिखने पर, पंक्तियाँ दो प्रतीकों की वर्णमाला पर लंबाई $n$ की शृंखलाओं से एक-एक संगत होती हैं, जिनकी संख्या $2^{n}$ है, आगमन पर पाठ के पहले हल प्रश्न के अनुसार, जहाँ इसे $n$ पर आगमन से सिद्ध किया गया।
$f \;\; \longmapsto \;\; f(1, \ldots, 1) \;\; \ldots \;\; f(0, \ldots, 0)$
सत्यता फलन पंक्तियों पर अपने मानों से निर्धारित होता है, और उन मानों का कोई भी चुनाव एक फलन देता है। मानों को सारणी के क्रम में लिखने पर, फलन $2^{n}$ प्रतीकों के उन अनुक्रमों से एक-एक संगत होते हैं, जिनमें प्रत्येक प्रतीक $1$ या $0$ है।
$2^{\resaltar{2^{n}}}$
वही गिनती, अब लंबाई $2^{n}$ के अनुक्रमों पर लागू करने पर, $2$ की घात $2^{n}$ फलन देती है।
$2^{2} = 4, \quad 2^{4} = 16, \quad 2^{8} = 256, \quad 2^{16} = 65\,536$
पहले कुछ मान दिखाते हैं कि यह संख्या कितनी तेज़ी से बढ़ती है: पाँच संकार्यों पर फलन पहले ही चार अरब से अधिक हैं।

उदाहरणएक संकार्य और दो संकार्यों वाले फलन

एक संकार्य वाले चार फलन ये हैं: अचर $1$ , तत्समक फलन, मानों को आपस में बदलने वाला फलन और अचर $0$ । सूत्र $\top$ , $p$ , $\neg p$ और $\bot$ की सारणियाँ क्रमशः यही हैं, जहाँ $\top := (p \rightarrow p)$ और $\bot := \neg\top$ अर्थविज्ञान के पाठ में निश्चित किए गए थे। दो संकार्यों वाले सोलह फलनों में पाठ्यक्रम के छह संयोजकों के फलन हैं: संयुक्त निषेध, वियोजन, संयोजन, सोपाधिक, द्विसोपाधिक और अनन्य वियोजन। शेष दस हैं, और उनमें दो अचर, वे फलन जो केवल एक संकार्य पर निर्भर करते हैं, और वैकल्पिक निषेध हैं, जिसका मान $0$ होता है केवल तब जब दोनों संकार्य $1$ हों। पहला हल प्रश्न इन सबका वर्गीकरण करता है।

फलन को निरूपित करने वाला सूत्र

सूत्रों और सत्यता फलनों का संबंध इस प्रकार है। यदि $\varphi$ एक सूत्र है जिसके चर $v_1, \ldots, v_n$ में से हैं, तो कहा जाता है कि $\varphi$ , $f$ सत्यता फलन को, जिसके $n$ संकार्य हैं, निरूपित करता है यदि प्रत्येक मान-नियतन $v$ के लिए

v(\varphi) = f(v(v_1), \ldots, v(v_n))

अर्थात, $\varphi$ चरों से लिखी गई $v_1, \ldots, v_n$ की सारणी $f$ की सारणी है। चरों वाली शर्त नगण्य नहीं है: सूत्र $(p \wedge q)$ एक संकार्य वाले किसी फलन को निरूपित नहीं करता, क्योंकि उसका मान केवल $p$ के मान पर निर्भर नहीं करता।

साध्यसूत्र का फलन

मान लीजिए $\varphi$ एक सूत्र है जिसके चर $v_1, \ldots, v_n$ में से हैं। तब $\varphi$ ठीक एक सत्यता फलन को, जिसके $n$ संकार्य हैं, निरूपित करता है, जिसे $f_\varphi$ लिखा जाता है। यदि $\psi$ एक अन्य सूत्र है जिसके चर $v_1, \ldots, v_n$ में से हैं, तो $\varphi \eqsem \psi$ यदि और केवल यदि $f_\varphi = f_\psi$ ।

प्रमाण

$\dato{va}{v_a(v_i) = a_i \quad (i \leq n), \qquad v_a(v_k) = 0 \quad (k > n)}$
प्रत्येक पंक्ति $a$ के लिए एक मान-नियतन है जो प्रत्येक $v_i$ को मान $a_i$ देता है: शेष चरों को मान $0$ देना पर्याप्त है।
$v(v_i) = v'(v_i) = a_i \quad (i \leq n) \;\; \Rightarrow \;\; v(\varphi) = v'(\varphi) = \resaltar{f_\varphi(a)}$
यदि दो मान-नियतन $v_1, \ldots, v_n$ को पंक्ति $a$ के मान देते हैं, तो वे $\varphi$ के चरों पर सहमत होते हैं, और संपाती प्रमेयिका से वे $\varphi$ को एक ही मान देते हैं। इस साझा मान को $f_\varphi(a)$ कहिए। रचना से, $\varphi$ , $f_\varphi$ को निरूपित करता है।
$g(a) = v_a(\varphi) = f_\varphi(a)$
यदि $\varphi$ फलन $g$ को भी निरूपित करता, तो प्रत्येक पंक्ति $a$ में $g(a) = v_a(\varphi) = f_\varphi(a)$ होता: निरूपित फलन अद्वितीय है।
$v(\varphi) = f_\varphi(v(v_1), \ldots, v(v_n)) = f_\psi(v(v_1), \ldots, v(v_n)) = v(\psi)$
यदि $f_\varphi = f_\psi$ , तो प्रत्येक मान-नियतन $v$ के लिए $\varphi$ और $\psi$ के मान एक ही फलन के एक ही पंक्ति में मान हैं। अतः $\varphi \eqsem \psi$ ।
$f_\varphi(a) = v_a(\varphi) = v_a(\psi) = f_\psi(a)$
विलोमतः, यदि $\varphi \eqsem \psi$ , तो प्रत्येक पंक्ति $a$ में मान-नियतन $v_a$ दोनों सूत्रों को एक ही मान देता है, और अतः $f_\varphi(a) = f_\psi(a)$ ।

$v_1, \ldots, v_n$ में से चरों वाले सूत्र अनंत हैं और फलन केवल $2^{2^{n}}$ : इसलिए बहुत-से सूत्र एक ही फलन को निरूपित करते हैं, और साध्य कहता है कि वे ठीक परस्पर तुल्य सूत्र हैं। अभी यह ज्ञात नहीं है कि क्या प्रत्येक फलन किसी सूत्र द्वारा निरूपित होता है, या कोई ऐसी सारणी बचती है जिसे किसी सूत्र की सारणी के रूप में प्राप्त नहीं किया जा सकता।

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

फलनात्मक पूर्णता का प्रमेय
अकेला संयुक्त निषेध पर्याप्त है
एक अनुप्रयोग: गेटों के परिपथ
संयोजकों के पर्याप्त समुच्चय
पर्याप्तता की कसौटी
अपर्याप्त समुच्चय
हल प्रश्न
वे फलन जो अपने दोनों संकार्यों पर निर्भर करते हैं
तीन का बहुमत
सोपाधिक और अनन्य वियोजन
निषेध के बिना क्या कहा जा सकता है
वे एकमात्र संयोजक जो अकेले पर्याप्त हैं
अभ्यास प्रश्न
सममित फलन
द्विसोपाधिक के लिए चार गेट
दोनों में से कोई नहीं, पर तीनों पर्याप्त
दूसरी उपपत्ति, संकार्य-दर-संकार्य
निषेध और द्विसोपाधिक पर्याप्त नहीं हैं

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

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

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

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

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

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