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

{{Short description|Standard form of Boolean function}}
{{multiple|
{{refimprove|date=November 2010}}
{{No footnotes|date=November 2010}}
}}
[[बूलियन तर्क]] में, एक विच्छेदनात्मक सामान्य रूप (DNF) एक तार्किक सूत्र का एक [[विहित सामान्य रूप]] है जिसमें संयोजनों का विच्छेदन शामिल होता है; इसे ANDs के OR, [[उत्पादों का योग]], या ([[दार्शनिक तर्क]] में) एक ''क्लस्टर अवधारणा'' के रूप में भी वर्णित किया जा सकता है।{{cn|date=December 2019}} [[सामान्य रूप (सार पुनर्लेखन)]] के रूप में, यह स्वचालित प्रमेय सिद्ध करने में उपयोगी है।

==परिभाषा==
एक तार्किक सूत्र को डीएनएफ में माना जाता है यदि यह एक या अधिक [[शाब्दिक (गणितीय तर्क)]] के एक या अधिक [[तार्किक संयोजन]] का [[तार्किक विच्छेदन]] है।<ref name="Davey.Priestley.1990">{{cite book | author=B.A. Davey and H.A. Priestley | title=लैटिस और ऑर्डर का परिचय|title-link= लैटिस और ऑर्डर का परिचय| publisher=Cambridge University Press | series=Cambridge Mathematical Textbooks | year=1990 }}</ref>{{rp|153}} एक डीएनएफ सूत्र पूर्ण विच्छेदात्मक सामान्य रूप में होता है यदि इसका प्रत्येक चर प्रत्येक संयोजन में बिल्कुल एक बार दिखाई देता है। [[संयोजक सामान्य रूप]] (सीएनएफ) की तरह, डीएनएफ में एकमात्र प्रस्तावक संचालक तार्किक संयोजन हैं (<math>\wedge</math>), तार्किक विच्छेदन (<math>\vee</math>), और निषेध (<math>\neg</math>). नॉट ऑपरेटर का उपयोग केवल शाब्दिक भाग के रूप में किया जा सकता है, जिसका अर्थ है कि यह केवल एक [[प्रस्तावात्मक चर]] से पहले हो सकता है।

निम्नलिखित DNF के लिए एक [[संदर्भ-मुक्त व्याकरण]] है:
# डीएनएफ → (संयोजन) <math>\vee</math> डीएनएफ
# डीएनएफ → (संयोजन)
# संयोजन → शाब्दिक <math>\wedge</math> संयोजक
# संयोजन → शाब्दिक
# शाब्दिक → <math>\neg</math>चर
# शाब्दिक → परिवर्तनशील
जहां वेरिएबल कोई भी वेरिएबल है।

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

*<math>(A \land \neg B \land \neg C) \lor (\neg D \land E \land F)</math>
*<math>(A \land B) \lor (C)</math>
*<math>(A \land B)</math>
*<math>(A)</math>
हालाँकि, निम्नलिखित सूत्र DNF में नहीं हैं:
*<math>\neg(A \lor B)</math>, क्योंकि एक OR एक NOT के भीतर निहित है
*<math>\neg(A \land B) \lor C</math>, चूँकि AND एक NOT के भीतर निहित है
*<math>A \lor (B \land (C \lor D))</math>, चूँकि एक OR एक AND के भीतर निहित है

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

==डीएनएफ में रूपांतरण==
[[File:Karnaugh map KV 4mal4 18.svg|thumb|डिसजंक्टिव सामान्य रूप का [[कर्णघ मानचित्र]] {{color|#800000|(¬''A''∧¬''B''∧¬''D'')}} ∨ {{color|#000080|(¬''A''∧''B''∧''C'')}} ∨ {{color|#008000|(''A''∧''B''∧''D'')}} ∨ {{color|#800080|(''A''∧¬''B''∧¬''C'')}}]]
[[File:Karnaugh map KV 4mal4 19.svg|thumb|डिसजंक्टिव सामान्य रूप का कर्णघ मानचित्र {{color|#800080|(¬''A''∧''C''∧¬''D'')}} ∨ {{color|#008000|(''B''∧''C''∧''D'')}} ∨ {{color|#000080|(''A''∧¬''C''∧''D'')}} ∨ {{color|#800000|(¬''B''∧¬''C''∧¬''D'')}}. अलग-अलग समूहीकरण के बावजूद, पिछले मानचित्र की तरह समान फ़ील्ड में 1 होता है।]]किसी सूत्र को DNF में परिवर्तित करने में तार्किक समकक्षों का उपयोग करना शामिल है, जैसे कि [[दोहरा निषेध उन्मूलन]], डी मॉर्गन के नियम और वितरण_प्रॉपर्टी#प्रोपोज़िशनल_लॉजिक।

सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है।<ref name="Davey.Priestley.1990"/>{{rp|152-153}} हालाँकि, कुछ मामलों में डीएनएफ में रूपांतरण से सूत्र का तेजी से विस्फोट हो सकता है। उदाहरण के लिए, सूत्र को परिवर्तित करना <math>(X_1 \lor Y_1) \land (X_2 \lor Y_2) \land \dots \land (X_n \lor Y_n)</math> DNF से 2 के साथ एक सूत्र प्राप्त होता है<sup>n</sup>शर्तें.

प्रत्येक विशेष [[बूलियन फ़ंक्शन]] को केवल और केवल एक द्वारा दर्शाया जा सकता है<ref group=note>Ignoring variations based on associativity and commutativity of AND and OR.</ref> पूर्ण विघटनकारी सामान्य रूप, [[विहित रूप (बूलियन बीजगणित)]] में से एक। इसके विपरीत, दो अलग-अलग सादे विच्छेदनात्मक सामान्य रूप एक ही बूलियन फ़ंक्शन को दर्शा सकते हैं; चित्र देखें.

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

इसके विपरीत, एक डीएनएफ फॉर्मूला तभी संतोषजनक होता है, जब और केवल तभी, इसका कोई एक संयोजन संतोषजनक हो; इसका निर्णय P (जटिलता) में किया जा सकता है।<ref>{{cite web|url=https://www.react.uni-saarland.de/people/zimmermann/slides/AlgoSyn_2015.pdf|title=लीनियर-टाइम टेम्पोरल लॉजिक के मॉडलों की गिनती की जटिलता|author=Martin Zimmermann|publisher=[[Saarland University]]|date=2015-01-22|access-date=2023-02-02}}</ref>


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

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

==टिप्पणियाँ==
{{reflist|group=note}}


==संदर्भ==
{{reflist}}
*{{cite book|author1=David Hilbert|author2=Wilhelm Ackermann|title=Principles of Mathematical Logic|url=https://books.google.com/books?id=45ZGMjV9vfcC&q=%22disjunctive+normal+form%22|year=1999|publisher=American Mathematical Soc.|isbn=978-0-8218-2024-7}}
*{{cite book|author=J. Eldon Whitesitt|title=Boolean Algebra and Its Applications|url=https://books.google.com/books?id=20Un1T78GlMC&q=%22disjunctive+normal+form%22|date=24 May 2012|publisher=Courier Corporation|isbn=978-0-486-15816-7}}
*{{cite book|author=Colin Howson|title=Logic with Trees: An Introduction to Symbolic Logic|url=https://books.google.com/books?id=Y4WGAgAAQBAJ&q=%22disjunctive+normal+form%22|date=11 October 2005|publisher=Routledge|isbn=978-1-134-78550-6}}
*{{cite book|author1=David Gries|author2=Fred B. Schneider|title=A Logical Approach to Discrete Math|url=https://books.google.com/books?id=ZWTDQ6H6gsUC&q=%22disjunctive+normal+form%22&pg=PA67|date=22 October 1993|publisher=Springer Science & Business Media|isbn=978-0-387-94115-8|pages=67–}}


==बाहरी संबंध==
* {{springer|title=Disjunctive normal form|id=p/d033300}}
[[Category: सामान्य रूप (तर्क)]] 



[[Category: Machine Translated Page]]
[[Category:Created On 08/08/2023]]