शिक्षण उद्देश्‍य:
इस कक्षा के अंत तक, छात्र सक्षम होंगे:

1. याद करना लिटरल और संयोजनात्मक और विच्छेदनात्मक सामान्य रूपों की परिभाषा।
2. पहचानना CNF और DNF में एक अभिव्यक्ति की संरचना।
3. उपयोग करना CNF या DNF का उपयोग करके प्रस्तावनात्मक तर्कशास्त्र अभिव्यक्तियों को सरल बनाना।

सूचकांक
लिटरल की परिभाषा
सामान्य रूप की परिभाषा
सामान्य रूप का प्रमेय

प्रस्तावनात्मक तर्कशास्त्र का एक रोचक और उपयोगी परिणाम सामान्य रूपों से संबंधित है। इन विषयों पर विस्तृत चर्चा करने के लिए हमें पहले कुछ अवधारणाओं की समीक्षा करनी होगी।

लिटरल की परिभाषा

लिटरल कोई भी परमाणु अभिव्यक्ति या परमाणु अभिव्यक्ति का नकारात्मक रूप होता है। इसके आधार पर, हम नकारात्मक या सकारात्मक लिटरल के बारे में बात करते हैं, यह इस पर निर्भर करता है कि परमाणु अभिव्यक्तियाँ नकारात्मकता के साथ होती हैं या नहीं। उदाहरण के लिए: A एक सकारात्मक लिटरल होगा और \neg A एक नकारात्मक लिटरल होगा।

सामान्य रूप की परिभाषा

एक अभिव्यक्ति F सामान्य रूप में होती है जब उसे लिटरल्स के विच्छेदन के संयोजन के रूप में लिखा जा सकता है, अर्थात:

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

और इसी प्रकार, यदि इसे लिटरल्स के संयोजन के विच्छेदन के रूप में लिखा जाए, तो यह विच्छेदनात्मक सामान्य रूप (DNF) होगी:

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

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

सभी प्रस्तावनात्मक तर्कशास्त्र अभिव्यक्तियाँ CNF और DNF अभिव्यक्तियों के बराबर होती हैं।

प्रमाण:

इसका प्रमाण सूत्रों F की जटिलता पर प्रेरण द्वारा किया जा सकता है।

• प्रारंभिक स्थिति: यदि F एक परमाणु अभिव्यक्ति है, तो इसे एक साथ CNF और DNF में लिखा जा सकता है, क्योंकि: F\equiv F_D \equiv F_C, जहाँ F_C:=((F\vee F)\wedge (F\vee F)) और F_D:=((F\wedge F)\vee (F\wedge F))
• प्रेरण कदम: मान लें G और H दो कोई भी अभिव्यक्तियाँ हैं जिनके लिए प्रमेय का परिणाम सत्य है; अर्थात्, ऐसे H_C और G_C CNF में होते हैं, और H_D और G_D DNF में होते हैं, जैसे कि:

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  इसलिए हम लिख सकते हैं:

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  बिना सामान्यता को खोए, यदि F:= \neg G, तो प्रतिस्थापन प्रमेय और डि मॉर्गन के सामान्यीकृत नियम के अनुसार हमारे पास होगा:

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  दूसरी ओर, यदि F:=G\wedge H, तो प्रतिस्थापन प्रमेय के अनुसार:

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  यह एक संयोजनात्मक सामान्य रूप है। और इसी प्रकार, यदि F:=H\vee G, तो:

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  यानी यह एक विच्छेदनात्मक सामान्य रूप है।

  इसलिए, प्रेरण पूर्ण है और सभी प्रस्तावनात्मक तर्कशास्त्र अभिव्यक्तियाँ FND और CNF में लिखी जा सकती हैं।

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