विच्छेदनात्मक सामान्य रूप

बूलियन तर्क में, एक विच्छेदनात्मक सामान्य रूप (DNF) एक तार्किक सूत्र का एक विहित सामान्य रूप है जिसमें संयोजनों का विच्छेदन शामिल होता है; इसे ANDs के OR, उत्पादों का योग, या (दार्शनिक तर्क में) एक क्लस्टर अवधारणा के रूप में भी वर्णित किया जा सकता है। सामान्य रूप (सार पुनर्लेखन) के रूप में, यह स्वचालित प्रमेय सिद्ध करने में उपयोगी है।

परिभाषा

एक तार्किक सूत्र को डीएनएफ में माना जाता है यदि यह एक या अधिक शाब्दिक (गणितीय तर्क) के एक या अधिक तार्किक संयोजन का तार्किक विच्छेदन है। एक डीएनएफ सूत्र पूर्ण विच्छेदात्मक सामान्य रूप में होता है यदि इसका प्रत्येक चर प्रत्येक संयोजन में बिल्कुल एक बार दिखाई देता है। संयोजक सामान्य रूप (सीएनएफ) की तरह, डीएनएफ में एकमात्र प्रस्तावक संचालक तार्किक संयोजन हैं ($\wedge$), तार्किक विच्छेदन ($\vee$), और निषेध ($\neg$). नॉट ऑपरेटर का उपयोग केवल शाब्दिक भाग के रूप में किया जा सकता है, जिसका अर्थ है कि यह केवल एक प्रस्तावात्मक चर से पहले हो सकता है।

निम्नलिखित DNF के लिए एक संदर्भ-मुक्त व्याकरण है:

1. डीएनएफ → (संयोजन) $\vee$ डीएनएफ
2. डीएनएफ → (संयोजन)
3. संयोजन → शाब्दिक $\wedge$ संयोजक
4. संयोजन → शाब्दिक
5. शाब्दिक → $\neg$चर
6. शाब्दिक → परिवर्तनशील

जहां वेरिएबल कोई भी वेरिएबल है।

उदाहरण के लिए, निम्नलिखित सभी सूत्र DNF में हैं:

• $(A\land \neg B\land \neg C)\lor (\neg D\land E\land F)$
• $(A\land B)\lor (C)$
• $(A\land B)$
• $(A)$

हालाँकि, निम्नलिखित सूत्र DNF में नहीं हैं:

• $\neg (A\lor B)$, क्योंकि एक OR एक NOT के भीतर निहित है
• $\neg (A\land B)\lor C$, चूँकि AND एक NOT के भीतर निहित है
• $A\lor (B\land (C\lor D))$, चूँकि एक OR एक AND के भीतर निहित है

सूत्र $A\lor B$ डीएनएफ में है, लेकिन पूर्ण डीएनएफ में नहीं; एक समतुल्य पूर्ण-डीएनएफ संस्करण है $(A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)$.

डीएनएफ में रूपांतरण

डिसजंक्टिव सामान्य रूप का कर्णघ मानचित्र (¬A∧¬B∧¬D) ∨ (¬A∧B∧C) ∨ (A∧B∧D) ∨ (A∧¬B∧¬C)

डिसजंक्टिव सामान्य रूप का कर्णघ मानचित्र (¬A∧C∧¬D) ∨ (B∧C∧D) ∨ (A∧¬C∧D) ∨ (¬B∧¬C∧¬D). अलग-अलग समूहीकरण के बावजूद, पिछले मानचित्र की तरह समान फ़ील्ड में 1 होता है।

किसी सूत्र को DNF में परिवर्तित करने में तार्किक समकक्षों का उपयोग करना शामिल है, जैसे कि दोहरा निषेध उन्मूलन, डी मॉर्गन के नियम और वितरण_प्रॉपर्टी#प्रोपोज़िशनल_लॉजिक।

सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है। हालाँकि, कुछ मामलों में डीएनएफ में रूपांतरण से सूत्र का तेजी से विस्फोट हो सकता है। उदाहरण के लिए, सूत्र को परिवर्तित करना $(X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})$ DNF से 2 के साथ एक सूत्र प्राप्त होता हैⁿशर्तें.

प्रत्येक विशेष बूलियन फ़ंक्शन को केवल और केवल एक द्वारा दर्शाया जा सकता है पूर्ण विघटनकारी सामान्य रूप, विहित रूप (बूलियन बीजगणित) में से एक। इसके विपरीत, दो अलग-अलग सादे विच्छेदनात्मक सामान्य रूप एक ही बूलियन फ़ंक्शन को दर्शा सकते हैं; चित्र देखें.

कम्प्यूटेशनल जटिलता

संयोजक सामान्य रूप सूत्रों पर बूलियन संतुष्टि समस्या एनपी-कठोरता है|एनपी-हार्ड; द्वैत सिद्धांत (बूलियन बीजगणित) द्वारा, डीएनएफ सूत्रों पर मिथ्याकरणीयता की समस्या भी है। इसलिए, यह तय करना सह-एनपी-कठिन है कि डीएनएफ फॉर्मूला एक टॉटोलॉजी (तर्क) है या नहीं।

इसके विपरीत, एक डीएनएफ फॉर्मूला तभी संतोषजनक होता है, जब और केवल तभी, इसका कोई एक संयोजन संतोषजनक हो; इसका निर्णय P (जटिलता) में किया जा सकता है।

वेरिएंट

एल्गोरिदम के विश्लेषण के अध्ययन में उपयोग किया जाने वाला एक महत्वपूर्ण बदलाव k-DNF है। यदि कोई सूत्र डीएनएफ में है तो वह के-डीएनएफ में है और प्रत्येक संयोजन में अधिकतम के अक्षर होते हैं।

यह भी देखें

• बीजगणितीय सामान्य रूप - AND खंडों का एक XOR
• ब्लेक विहित रूप - सभी प्रमुख निहितार्थों सहित डीएनएफ
  • क्विन-मैक्लुस्की एल्गोरिदम - प्राइम इम्प्लेंट्स की गणना के लिए एल्गोरिदम
• मक तर्क
• ट्रुथ टेबल

संदर्भ

• David Hilbert; Wilhelm Ackermann (1999). Principles of Mathematical Logic. American Mathematical Soc. ISBN 978-0-8218-2024-7.
• J. Eldon Whitesitt (24 May 2012). Boolean Algebra and Its Applications. Courier Corporation. ISBN 978-0-486-15816-7.
• Colin Howson (11 October 2005). Logic with Trees: An Introduction to Symbolic Logic. Routledge. ISBN 978-1-134-78550-6.
• David Gries; Fred B. Schneider (22 October 1993). A Logical Approach to Discrete Math. Springer Science & Business Media. pp. 67–. ISBN 978-0-387-94115-8.

बाहरी संबंध

• "Disjunctive normal form", Encyclopedia of Mathematics, EMS Press, 2001 [1994]