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

From Vigyanwiki
(Created page with "{{Short description|Standard form of Boolean function}} {{multiple| {{refimprove|date=November 2010}} {{No footnotes|date=November 2010}} }} [[बूलियन तर्क]...")
 
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Standard form of Boolean function}}
{{Short description|Standard form of Boolean function}}
{{multiple|
[[बूलियन तर्क]] में, एक '''वियोजक सामान्य रूप (डीएनएफ)''' एक तार्किक सूत्र का एक [[विहित सामान्य रूप]] होता है जिसमें संयोजनों का वियोजन सम्मिलित होता है; इसे '''ANDs''' के '''OR''', [[उत्पादों का योग]], या ([[दार्शनिक तर्क]] में) एक ''क्लस्टर अवधारणा'' के रूप में भी वर्णित किया जा सकता है। [[सामान्य रूप (सार पुनर्लेखन)|सामान्य रूप]] में, यह स्वचालित प्रमेय सिद्ध करने में उपयोगी होती है।
{{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>). नॉट ऑपरेटर का उपयोग केवल शाब्दिक भाग के रूप में किया जा सकता है, जिसका अर्थ है कि यह केवल एक [[प्रस्तावात्मक चर]] से पहले हो सकता है।
एक तार्किक सूत्र को डीएनएफ में माना जाता है यदि यह एक या अधिक [[शाब्दिक (गणितीय तर्क)|शाब्दिक]] के एक या अधिक [[तार्किक संयोजन]] का [[तार्किक विच्छेदन|तार्किक वियोजन]] होता है।<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}} एक डीएनएफ सूत्र '''पूर्ण विघटनकारी सामान्य रूप''' में होता है यदि इसका प्रत्येक चर प्रत्येक संयोजन में मात्र एक बार दिखाई देता हो तो। [[संयोजक सामान्य रूप]] (सीएनएफ) की तरह, डीएनएफ में एकमात्र प्रस्तावक संचालक तार्किक संयोजन AND (<math>\wedge</math>), OR (<math>\vee</math>), और NOT (<math>\neg</math>) होता हैं। नॉट ऑपरेटर का उपयोग मात्र शाब्दिक भाग के रूप में किया जा सकता है, जिसका अर्थ है कि यह मात्र एक [[प्रस्तावात्मक चर]] से पहले हो सकता है।


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


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


*<math>(A \land \neg B \land \neg C) \lor (\neg D \land E \land F)</math>
*<math>(A \land \neg B \land \neg C) \lor (\neg D \land E \land F)</math>
Line 24: Line 20:
*<math>(A \land B)</math>
*<math>(A \land B)</math>
*<math>(A)</math>
*<math>(A)</math>
हालाँकि, निम्नलिखित सूत्र DNF में नहीं हैं:
यद्यपि, निम्नलिखित सूत्र डीएनएफ में नहीं होता हैं:
*<math>\neg(A \lor B)</math>, क्योंकि एक OR एक NOT के भीतर निहित है
*<math>\neg(A \lor B)</math>, क्योंकि एक OR एक NOT के भीतर निहित होता है
*<math>\neg(A \land B) \lor C</math>, चूँकि AND एक 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 \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>.
सूत्र <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 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 में परिवर्तित करने में तार्किक समकक्षों का उपयोग करना शामिल है, जैसे कि [[दोहरा निषेध उन्मूलन]], डी मॉर्गन के नियम और वितरण_प्रॉपर्टी#प्रोपोज़िशनल_लॉजिक।
[[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 होता है।]]किसी सूत्र को डीएनएफ में परिवर्तित करने में तार्किक समकक्षों का उपयोग करना सम्मिलित होता है, जैसे कि [[दोहरा निषेध उन्मूलन]], डी मॉर्गन के नियम और वितरणात्मक नियम।


सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है।<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 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> को डीएनएफ में परिवर्तित करने पर 2<sup>''n''</sup> पदों वाला एक सूत्र प्राप्त होता है।


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


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


 
== संदर्भ ==
==संदर्भ==
{{reflist}}
{{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|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}}
Line 69: Line 63:
==बाहरी संबंध==
==बाहरी संबंध==
* {{springer|title=Disjunctive normal form|id=p/d033300}}
* {{springer|title=Disjunctive normal form|id=p/d033300}}
[[Category: सामान्य रूप (तर्क)]]


[[Category: Machine Translated Page]]
[[Category:Created On 08/08/2023]]
[[Category:Created On 08/08/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages that use a deprecated format of the math tags]]
[[Category:Pages with reference errors]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]

Latest revision as of 10:56, 22 August 2023

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

परिभाषा

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

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

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

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

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

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

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

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

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

वियोजक सामान्य रूप का कर्णघ मानचित्र (¬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 होता है।

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

सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है।[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.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=विच्छेदनात्मक_सामान्य_रूप&oldid=252191’