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

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

परिभाषा

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

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

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

जहाँ चर कोई भी चर होता है।

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

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

यद्यपि, निम्नलिखित सूत्र डीएनएफ में नहीं होता हैं:

• $\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 होता है।

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

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

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

कम्प्यूटेशनल सम्मिश्र

संयोजक सामान्य रूप सूत्रों पर बूलियन सेटिस्फाईएबिलिटी समस्या एनपी-हार्ड होती है; द्वैत सिद्धांत के अनुसार डीएनएफ सूत्रों पर मिथ्याकरणीयता की समस्या भी होती है। इसलिए, यह तय किया जाता है की को-एनपी-हार्ड और डीएनएफ फॉर्मूला एक टॉटोलॉजी है या नहीं।

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

प्रकार

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

यह भी देखें

• बीजगणितीय सामान्य रूप - 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]