विच्छेदनात्मक सामान्य रूप: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Standard form of Boolean function}} | {{Short description|Standard form of Boolean function}} | ||
[[बूलियन तर्क]] में, एक | [[बूलियन तर्क]] में, एक '''वियोजक सामान्य रूप (डीएनएफ)''' एक तार्किक सूत्र का एक [[विहित सामान्य रूप]] होता है जिसमें संयोजनों का वियोजन सम्मिलित होता है; इसे '''ANDs''' के '''OR''', [[उत्पादों का योग]], या ([[दार्शनिक तर्क]] में) एक ''क्लस्टर अवधारणा'' के रूप में भी वर्णित किया जा सकता है। [[सामान्य रूप (सार पुनर्लेखन)|सामान्य रूप]] में, यह स्वचालित प्रमेय सिद्ध करने में उपयोगी होती है। | ||
==परिभाषा== | ==परिभाषा== | ||
एक तार्किक सूत्र को डीएनएफ में माना जाता है यदि यह एक या अधिक [[शाब्दिक (गणितीय तर्क)]] के एक या अधिक [[तार्किक संयोजन]] का [[तार्किक विच्छेदन]] है।<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}} एक डीएनएफ सूत्र पूर्ण | एक तार्किक सूत्र को डीएनएफ में माना जाता है यदि यह एक या अधिक [[शाब्दिक (गणितीय तर्क)|शाब्दिक]] के एक या अधिक [[तार्किक संयोजन]] का [[तार्किक विच्छेदन|तार्किक वियोजन]] होता है।<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>) होता हैं। नॉट ऑपरेटर का उपयोग मात्र शाब्दिक भाग के रूप में किया जा सकता है, जिसका अर्थ है कि यह मात्र एक [[प्रस्तावात्मक चर]] से पहले हो सकता है। | ||
निम्नलिखित | निम्नलिखित डीएनएफ के लिए एक [[संदर्भ-मुक्त व्याकरण]] निम्न प्रकार है : | ||
# डीएनएफ → (संयोजन) <math>\vee</math> डीएनएफ | # डीएनएफ → (संयोजन) <math>\vee</math> डीएनएफ | ||
# डीएनएफ → (संयोजन) | # डीएनएफ → (संयोजन) | ||
| Line 12: | Line 12: | ||
# शाब्दिक → <math>\neg</math>चर | # शाब्दिक → <math>\neg</math>चर | ||
# शाब्दिक → परिवर्तनशील | # शाब्दिक → परिवर्तनशील | ||
जहाँ चर कोई भी चर होता है। | |||
उदाहरण के लिए, निम्नलिखित सभी सूत्र | उदाहरण के लिए, निम्नलिखित सभी सूत्र डीएनएफ में निम्न प्रकार है: | ||
*<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 20: | Line 20: | ||
*<math>(A \land B)</math> | *<math>(A \land B)</math> | ||
*<math>(A)</math> | *<math>(A)</math> | ||
यद्यपि, निम्नलिखित सूत्र डीएनएफ में नहीं होता हैं: | |||
*<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 \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| | [[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| | [[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}} | सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है।<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="नोट">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> | ||
== | == प्रकार == | ||
कलन विधि के विश्लेषण के अध्ययन में उपयोग किया जाने वाला एक महत्वपूर्ण भिन्नता के-डीएनएफ होता है। यदि कोई सूत्र डीएनएफ में होता है तो वह के-डीएनएफ में होता है और प्रत्येक संयोजन में अधिकतम के अक्षर होते हैं। | |||
== यह भी देखें == | == यह भी देखें == | ||
* [[बीजगणितीय सामान्य रूप]] - AND | * [[बीजगणितीय सामान्य रूप]] - 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}} | ||
Revision as of 22:16, 13 August 2023
बूलियन तर्क में, एक वियोजक सामान्य रूप (डीएनएफ) एक तार्किक सूत्र का एक विहित सामान्य रूप होता है जिसमें संयोजनों का वियोजन सम्मिलित होता है; इसे ANDs के OR, उत्पादों का योग, या (दार्शनिक तर्क में) एक क्लस्टर अवधारणा के रूप में भी वर्णित किया जा सकता है। सामान्य रूप में, यह स्वचालित प्रमेय सिद्ध करने में उपयोगी होती है।
परिभाषा
एक तार्किक सूत्र को डीएनएफ में माना जाता है यदि यह एक या अधिक शाब्दिक के एक या अधिक तार्किक संयोजन का तार्किक वियोजन होता है।[1]: 153 एक डीएनएफ सूत्र पूर्ण विघटनकारी सामान्य रूप में होता है यदि इसका प्रत्येक चर प्रत्येक संयोजन में मात्र एक बार दिखाई देता हो तो। संयोजक सामान्य रूप (सीएनएफ) की तरह, डीएनएफ में एकमात्र प्रस्तावक संचालक तार्किक संयोजन AND (), OR (), और NOT () होता हैं। नॉट ऑपरेटर का उपयोग मात्र शाब्दिक भाग के रूप में किया जा सकता है, जिसका अर्थ है कि यह मात्र एक प्रस्तावात्मक चर से पहले हो सकता है।
निम्नलिखित डीएनएफ के लिए एक संदर्भ-मुक्त व्याकरण निम्न प्रकार है :
- डीएनएफ → (संयोजन) डीएनएफ
- डीएनएफ → (संयोजन)
- संयोजन → शाब्दिक संयोजक
- संयोजन → शाब्दिक
- शाब्दिक → चर
- शाब्दिक → परिवर्तनशील
जहाँ चर कोई भी चर होता है।
उदाहरण के लिए, निम्नलिखित सभी सूत्र डीएनएफ में निम्न प्रकार है:
यद्यपि, निम्नलिखित सूत्र डीएनएफ में नहीं होता हैं:
- , क्योंकि एक OR एक NOT के भीतर निहित होता है
- , चूँकि AND एक NOT के भीतर निहित होता है
- , चूँकि एक OR एक AND के भीतर निहित होता है
सूत्र डीएनएफ में होता है, परन्तु पूर्ण डीएनएफ में नहीं; एक समतुल्य पूर्ण-डीएनएफ संस्करण होता है।
डीएनएफ में रूपांतरण
किसी सूत्र को डीएनएफ में परिवर्तित करने में तार्किक समकक्षों का उपयोग करना सम्मिलित होता है, जैसे कि दोहरा निषेध उन्मूलन, डी मॉर्गन के नियम और वितरणात्मक नियम।
सभी तार्किक सूत्रों को समतुल्य वियोजक सामान्य रूप में परिवर्तित किया जा सकता है।[1]: 152–153 यद्यपि, कुछ स्थितियों में डीएनएफ में रूपांतरण से सूत्र का शीघ्रता से विस्फोट हो सकता है। उदाहरण के लिए, सूत्र को डीएनएफ में परिवर्तित करने पर 2n पदों वाला एक सूत्र प्राप्त होता है।
प्रत्येक विशेष बूलियन फलन को मात्र और मात्र एक[नोट 1] पूर्ण विघटनकारी सामान्य रूप, विहित रूप में से एक द्वारा प्रदर्शित किया जा सकता है। इसके विपरीत, दो भिन्न-भिन्न सधारण वियोजक सामान्य रूप एक ही बूलियन फलन को प्रदर्शित कर सकते हैं; चित्र देखें।
कम्प्यूटेशनल सम्मिश्र
संयोजक सामान्य रूप सूत्रों पर बूलियन संतुष्टि समस्या एनपी-हार्ड होती है; द्वैत सिद्धांत के अनुसार डीएनएफ सूत्रों पर मिथ्याकरणीयता की समस्या भी होती है। इसलिए, यह तय किया जाता है की को-एनपी-हार्ड और डीएनएफ फॉर्मूला एक टॉटोलॉजी है या नहीं।
इसके विपरीत, एक डीएनएफ फॉर्मूला तभी संतोषजनक होता है, जब और मात्र तभी, इसका कोई एक संयोजन संतोषजनक हो; इसका निर्णय P (सम्मिश्र) में किया जा सकता है।[2]
प्रकार
कलन विधि के विश्लेषण के अध्ययन में उपयोग किया जाने वाला एक महत्वपूर्ण भिन्नता के-डीएनएफ होता है। यदि कोई सूत्र डीएनएफ में होता है तो वह के-डीएनएफ में होता है और प्रत्येक संयोजन में अधिकतम के अक्षर होते हैं।
यह भी देखें
- बीजगणितीय सामान्य रूप - AND उपवाक्यों का एक XOR
- ब्लेक विहित रूप - सभी प्रमुख निहितार्थों सहित डीएनएफ
- क्विन-मैक्लुस्की कलन विधि - प्राइम इम्प्लेंट्स की गणना के लिए कलन विधि
- मक तर्क
- सत्य सारणी
टिप्पणियाँ
संदर्भ
- ↑ 1.0 1.1 B.A. Davey and H.A. Priestley (1990). लैटिस और ऑर्डर का परिचय. Cambridge Mathematical Textbooks. Cambridge University Press.
- ↑ Martin Zimmermann (2015-01-22). "लीनियर-टाइम टेम्पोरल लॉजिक के मॉडलों की गिनती की जटिलता" (PDF). Saarland University. Retrieved 2023-02-02.
- 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]
Cite error: <ref> tags exist for a group named "नोट", but no corresponding <references group="नोट"/> tag was found
