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

From Vigyanwiki

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

परिभाषा

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

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

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

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

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

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

  • , क्योंकि एक OR एक NOT के भीतर निहित होता है
  • , चूँकि AND एक NOT के भीतर निहित होता है
  • , चूँकि एक OR एक AND के भीतर निहित होता है

सूत्र डीएनएफ में होता है, परन्तु पूर्ण डीएनएफ में नहीं; एक समतुल्य पूर्ण-डीएनएफ संस्करण होता है।

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

वियोजक सामान्य रूप का कर्णघ मानचित्र A∧¬B∧¬D)ABC)(ABD)(A∧¬B∧¬C)
वियोजक सामान्य रूप का कर्णघ मानचित्र AC∧¬D)(BCD)(A∧¬CD)B∧¬C∧¬D). भिन्न-भिन्न समूहीकरण के पश्चात् भी, पिछले मानचित्र की भांति समान क्षेत्र में 1 होता है।

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

सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है।[1]: 152–153  यद्यपि, कुछ स्थितियों में डीएनएफ में रूपांतरण से सूत्र का शीघ्रता से विस्फोट हो सकता है। उदाहरण के लिए, सूत्र को डीएनएफ में परिवर्तित करने पर 2n पदों वाला एक सूत्र प्राप्त होता है।

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

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

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

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

प्रकार

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

यह भी देखें

टिप्पणियाँ

  1. Ignoring variations based on associativity and commutativity of AND and OR.

संदर्भ

  1. 1.0 1.1 B.A. Davey and H.A. Priestley (1990). लैटिस और ऑर्डर का परिचय. Cambridge Mathematical Textbooks. Cambridge University Press.
  2. Martin Zimmermann (2015-01-22). "लीनियर-टाइम टेम्पोरल लॉजिक के मॉडलों की गिनती की जटिलता" (PDF). Saarland University. Retrieved 2023-02-02.


बाहरी संबंध