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

सारांश

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

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

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

इस इकाई के पिछले पाठों में सूत्रों को अर्थ दिया गया: प्रस्तावात्मक तर्क का अर्थविज्ञान पर पाठ ने हर मान-नियतन का सभी सूत्रों पर विस्तार किया; शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता पर पाठ ने तुल्यता $\varphi \eqsem \psi$ को परिभाषित किया और शब्दार्थीय प्रतिस्थापन सिद्ध किया; डी मॉर्गन के और वितरण के व्यापकीकृत नियम पर पाठ ने उन नियमों को $n$ सूत्रों के संयोजनों और वियोजनों तक बढ़ाया; और फलनात्मक पूर्णता पर पाठ ने दिखाया कि हर सत्यता फलन किसी सूत्र से निरूपित होता है। किंतु एक सत्यता फलन अनंत सूत्रों से निरूपित होता है, जो आपस में बहुत भिन्न हो सकते हैं: $(v_1 \rightarrow v_2)$ , $\neg(v_1 \wedge \neg v_2)$ और $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ एक ही वस्तु के तीन नाम हैं। यदि ऐसा है, तो हर तुल्यता वर्ग में एक निश्चित रूप वाला प्रतिनिधि चुनना उचित है, जो बिना परिश्रम के पढ़ा जाए और जिससे कुछ प्रश्नों के उत्तर देखकर ही मिल जाएँ। यही प्रसामान्य रूप हैं।

लिटरल, उपवाक्य और प्रसामान्य रूप

व्यापकीकृत नियमों के पाठ से $n$ सूत्रों के संयोजन और वियोजन का संकेतन याद करें, जो पुनरावर्तन से और बाईं ओर से समूहित करके परिभाषित है; एक ही सूत्र का संयोजन और वियोजन वह सूत्र स्वयं है।

\bigwedge_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigwedge_{i=1}^{n + 1} \varphi_i = \left( \bigwedge_{i=1}^{n} \varphi_i \wedge \varphi_{n + 1} \right)

\bigvee_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigvee_{i=1}^{n + 1} \varphi_i = \left( \bigvee_{i=1}^{n} \varphi_i \vee \varphi_{n + 1} \right)

उसी पाठ में सिद्ध हुआ कि पदों का क्रम और समूहन, तुल्यता को छोड़कर, सूत्र को नहीं बदलते (व्यापकीकृत साहचर्यता तथा क्रम और पुनरावृत्तियों से स्वतंत्रता); इसलिए हम $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ भी बिना कोष्ठकों के लिखेंगे, बाईं ओर से समूहन समझते हुए।

लिटरल एक चर $v_n$ है, जिसे धनात्मक लिटरल कहते हैं, या किसी चर का निषेध $\neg v_n$ , जिसे ऋणात्मक लिटरल कहते हैं। किसी लिटरल $\ell$ का विपरीत लिटरल, जिसे हम $\ell^{*}$ लिखते हैं, उसी चर का दूसरे चिह्न वाला लिटरल है:

\ell = v_n \;\Rightarrow\; \ell^{*} = \neg v_n, \qquad \ell = \neg v_n \;\Rightarrow\; \ell^{*} = v_n

परिभाषा से निकलता है कि $(\ell^{*})^{*} = \ell$ । दो लिटरल एक पूरक युग्म बनाते हैं यदि एक दूसरे का विपरीत हो, जैसे $v_3$ और $\neg v_3$ ।

उपवाक्य लिटरलों का वियोजन $\bigvee_{j=1}^{k} \ell_j$ है, और प्राथमिक संयोजन लिटरलों का संयोजन $\bigwedge_{j=1}^{k} \ell_j$ है, दोनों स्थितियों में $k \geq 1$ के साथ; अतः एक अकेला लिटरल एक साथ उपवाक्य भी है और प्राथमिक संयोजन भी। कहा जाता है कि कोई लिटरल किसी उपवाक्य या प्राथमिक संयोजन में आता है यदि वह उसके $\ell_j$ में से एक हो।

कोई सूत्र वियोजक प्रसामान्य रूप में है यदि वह प्राथमिक संयोजनों का वियोजन हो, और संयोजक प्रसामान्य रूप में है यदि वह उपवाक्यों का संयोजन हो; अर्थात यदि वह क्रमशः निम्नलिखित दो रूपों में से किसी एक का हो, जहाँ $m$ और $k_1, \ldots, k_m$ प्राकृत संख्याएँ हैं और प्रत्येक $\ell_{i,j}$ एक लिटरल है:

\bigvee_{i=1}^{m} \bigwedge_{j=1}^{k_i} \ell_{i,j}, \qquad \bigwedge_{i=1}^{m} \bigvee_{j=1}^{k_i} \ell_{i,j}

हम कहेंगे कि $\Phi$ , $\varphi$ का एक वियोजक प्रसामान्य रूप है यदि वह वियोजक प्रसामान्य रूप में हो और $\varphi \eqsem \Phi$ , और संयोजक के लिए भी ऐसा ही। लंबाइयाँ $k_i$ एक संयोजन (या उपवाक्य) से दूसरे तक बदल सकती हैं: सब में लिटरलों की एक ही संख्या माँगने से पुनरावृत्तियों से भरना पड़ता और कुछ भी नहीं जुड़ता।

उदाहरणक्या प्रसामान्य रूप में है और क्या नहीं

सूत्र $(v_1 \wedge \neg v_2) \vee \neg v_3$ वियोजक प्रसामान्य रूप में है, जहाँ $m = 2$ , $k_1 = 2$ और $k_2 = 1$ ; वह संयोजक रूप में नहीं है, क्योंकि वह संयोजन नहीं है (उसके दोनों घटक भिन्न हैं, और संयोजन एक दोहरा निषेध है), और न ही वह उपवाक्य है: वियोजन के रूप में पढ़ने पर उसका एक पद $(v_1 \wedge \neg v_2)$ है, जो न लिटरल है न लिटरलों का वियोजन। सूत्र $v_1 \wedge \neg v_2 \wedge v_3$ दोनों रूपों में है: एक ही प्राथमिक संयोजन ( $m = 1$ ) के वियोजन के रूप में, और तीन उपवाक्यों के संयोजन के रूप में जिनमें प्रत्येक में एक लिटरल है। इसी प्रकार $(\neg v_1 \vee v_2)$ एक साथ उपवाक्य है, अर्थात $m = 1$ वाला संयोजक रूप, और एक-एक लिटरल वाले दो संयोजनों का वियोजक रूप भी।

(v_1 \wedge \neg v_2) \vee \neg v_3, \qquad v_1 \wedge \neg v_2 \wedge v_3, \qquad \neg v_1 \vee v_2

इसके विपरीत, $(v_1 \downarrow v_2)$ और $\neg(v_1 \rightarrow v_2)$ दोनों में से किसी भी रूप में नहीं हैं, यद्यपि पहला $(\neg v_1 \wedge \neg v_2)$ के और दूसरा $(v_1 \wedge \neg v_2)$ के तुल्य है, और ये उन रूपों में हैं।

(v_1 \downarrow v_2) \eqsem \neg v_1 \wedge \neg v_2, \qquad \neg(v_1 \rightarrow v_2) \eqsem v_1 \wedge \neg v_2

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

(\varphi \vee \varphi) = \neg(\varphi \downarrow \varphi) = \neg\neg\varphi

संयोजनों और वियोजनों का मान

अर्थविज्ञान के पाठ से व्युत्पन्न संयोजकों के मान लिए जाते हैं: $v(\neg\varphi) = 1 - v(\varphi)$ ; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$ , जिसका मान $1$ है यदि और केवल यदि दोनों का मान $1$ हो; और $v(\varphi \vee \psi) = 0$ यदि और केवल यदि दोनों का मान $0$ हो। डी मॉर्गन के और वितरण के व्यापकीकृत नियम पर पाठ ने इन्हें पदों की संख्या पर आगमन से $n$ सूत्रों तक बढ़ाया, मान प्रमेयिका में: प्रत्येक मान-नियतन $v$ के लिए, संयोजन $\bigwedge_{i=1}^{n} \varphi_i$ का मान $1$ होता है $v$ में यदि और केवल यदि प्रत्येक $\varphi_i$ का मान $1$ हो $v$ में, और वियोजन $\bigvee_{i=1}^{n} \varphi_i$ का मान $1$ होता है $v$ में यदि और केवल यदि किसी $\varphi_i$ का मान $1$ हो $v$ में। यह प्रमेयिका, जिसे यहाँ उसकी उपपत्ति दोहराए बिना उद्धृत किया जाता है, वह उपकरण है जिससे किसी भी प्रसामान्य रूप का मान निकाला जाता है।

उपप्रमेयलिटरल का निषेध

प्रत्येक लिटरल $\ell$ के लिए, $\ell$ का निषेध उसके विपरीत लिटरल $\neg\ell \eqsem \ell^{*}$ के तुल्य है; विशेष रूप से, $v(\ell^{*}) = 1 - v(\ell)$ , प्रत्येक मान-नियतन $v$ के लिए।

प्रमाण

$\ell = v_n \;\Rightarrow\; \neg\ell = \neg v_n = \ell^{*}$
यदि $\ell$ एक चर $v_n$ है, तो उसका विपरीत $\neg v_n$ है, जो ठीक-ठीक शृंखला $\neg\ell$ है: सिद्ध करने को कुछ नहीं है।
$\ell = \neg v_n \;\Rightarrow\; \neg\ell = \resaltar{\neg\neg v_n} \eqsem v_n = \ell^{*}$
यदि $\ell$ , $\neg v_n$ है, तो उसका निषेध $\neg\neg v_n$ है, जो लिटरल नहीं है; दोहरे निषेध के नियम से (शब्दार्थीय परिणाम और शब्दार्थीय तुल्यता का पाठ), वह $v_n$ के तुल्य है, जो $\ell$ का विपरीत है।
$v(\ell^{*}) = v(\neg\ell) = 1 - v(\ell)$
दोनों स्थितियों में $\ell^{*}$ और $\neg\ell$ का प्रत्येक मान-नियतन में एक ही मान है, और $\neg\ell$ का मान निषेध का मान देता है।

दूसरी स्थिति आसानी से छूट जाती है: किसी प्रसामान्य रूप का निषेध करते समय लिटरल की जगह $\neg\ell_{i,j}$ लिखने की प्रवृत्ति होती है, और $\neg\neg v_n$ लिटरल नहीं है। दोहरा निषेध ही परिणाम को साँचे में लौटाता है।

उपप्रमेयप्राथमिक संयोजन और उपवाक्य

कोई प्राथमिक संयोजन संतोषणीय है यदि और केवल यदि उसमें कोई पूरक युग्म न हो। कोई उपवाक्य वैध है यदि और केवल यदि उसमें कोई पूरक युग्म हो।

प्रमाण

$v(\ell)\,v(\ell^{*}) = v(\ell)\,(1 - v(\ell)) = 0$
यदि किसी प्राथमिक संयोजन में $\ell$ और $\ell^{*}$ हों, तो पिछली प्रमेयिका से प्रत्येक मान-नियतन में दोनों में से एक का मान $0$ है; मान प्रमेयिका से संयोजन का मान प्रत्येक मान-नियतन में $0$ है।
$\dato{val}{v_n = \ell_j \;\Rightarrow\; v(v_n) = 1, \qquad \neg v_n = \ell_j \;\Rightarrow\; v(v_n) = 0}$
यदि उसमें कोई पूरक युग्म नहीं है, तो एक मान-नियतन परिभाषित किया जाता है जो उसमें धनात्मक लिटरल के रूप में आने वाले हर चर को $1$ और उसमें ऋणात्मक लिटरल के रूप में आने वाले हर चर को $0$ देता है (शेष को $0$ )। परिभाषा व्याघाती नहीं है, क्योंकि कोई चर दोनों तरह से नहीं आता।
$v\left( \bigwedge_{j=1}^{k} \ell_j \right) = 1$
उस मान-नियतन में उसके सभी लिटरलों का मान $1$ है, और मान प्रमेयिका से संयोजन का मान $1$ है: वह संतोषणीय है।
$v(\ell) + v(\ell^{*}) = 1$
यदि किसी उपवाक्य में $\ell$ और $\ell^{*}$ हों, तो प्रत्येक मान-नियतन में दोनों में से एक का मान $1$ है, और उपवाक्य का मान $1$ है: वह वैध है।
$v\left( \bigvee_{j=1}^{k} \ell_j \right) = 0$
यदि उसमें कोई पूरक युग्म नहीं है, तो वह मान-नियतन जो उसके धनात्मक चरों को $0$ और निषेधित चरों को $1$ देता है, उसके सभी लिटरलों का मान $0$ कर देता है; मान प्रमेयिका से उसमें उपवाक्य का मान $0$ है, और वह वैध नहीं है।

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

दोनों रूपों के बीच द्वैतता
सारणी से विहित रूप
जटिलता पर आगमन से अस्तित्व
जो एक नज़र में दिखता है
हल प्रश्न
एक चर जो अन्य दो में से किसी एक के साथ चलता है
दोहरे संयुक्त निषेध के प्रसामान्य रूप
प्रसामान्य रूपों से प्राकल्पिक न्यायवाक्य
सम-विषमता छोटे रूप स्वीकार नहीं करती
एकदिष्ट सूत्र
अभ्यास प्रश्न
एक चर जोड़ने पर विहित रूप
एक नज़र में एक परिणाम
एक वैध वियोजक रूप
संयोजक रूप में सम-विषमता
वे चर जिन पर कोई सूत्र निर्भर नहीं करता

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

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

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

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

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

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