दो-अवयव बूलियन बीजगणित: Difference between revisions
| Line 48: | Line 48: | ||
2 के लिए समीकरणों का सेट एक''आधारक'' है,जिसे [[स्वयंसिद्ध|अभिगृहीत]] कहा जाता है,जिससे उपरोक्त सभी समीकरण (और अधिक) प्राप्त किए जा सकते हैं।सभी बूलियन बीजगणित के लिए और इस कारण से 2 के लिए कई ज्ञात आधार हैं। केवल संयोजन और ओवरबार का उपयोग करके नोट किया गया एक सुंदर आधार है: | 2 के लिए समीकरणों का सेट एक''आधारक'' है,जिसे [[स्वयंसिद्ध|अभिगृहीत]] कहा जाता है,जिससे उपरोक्त सभी समीकरण (और अधिक) प्राप्त किए जा सकते हैं।सभी बूलियन बीजगणित के लिए और इस कारण से 2 के लिए कई ज्ञात आधार हैं। केवल संयोजन और ओवरबार का उपयोग करके नोट किया गया एक सुंदर आधार है: | ||
# <math>\ ABC = BCA</math> (संयोजन आवागमन, | # <math>\ ABC = BCA</math> (संयोजन आवागमन,संगुणित होना) | ||
# <math>\overline{A}A = 1</math> ('''2''' एक पूरित जाली है,1 के उपरिपरिबंध के साथ) | # <math>\overline{A}A = 1</math> ('''2''' एक पूरित जाली है,1 के उपरिपरिबंध के साथ) | ||
#<math>\ A0 = A</math> (0 निम्न परिबंध है)। | #<math>\ A0 = A</math> (0 निम्न परिबंध है)। | ||
| Line 57: | Line 57: | ||
यदि 0=1, (1)-(3) [[एबेलियन समूह]] के लिए अभिगृहीत हैं। | यदि 0=1, (1)-(3) [[एबेलियन समूह]] के लिए अभिगृहीत हैं। | ||
(1) केवल संयोजन आवागमन और | (1) केवल संयोजन आवागमन और संगुणित सिद्ध करने का काम करता है।पहले मान लें कि(1) बाएँ या दाएँ से संगुणित है,फिर क्रमविनिमेयता सिद्ध करें। फिर दूसरी दिशा से संबंध सिद्ध करें। संबद्धता केवल बाएँ और दाएँ संयुक्त रूप से जुड़ा होना है। | ||
इस आधार पर सिद्ध के लिए एक आसान तरीका बनाता है, जिसे ''फॉर्म के नियम'' में "गणना" कहा जाता है,जो कि अभिगृहीतों (2)-(4) का उपयोग करके और प्रारंभिक सर्वसमिकाओं के व्यंजकों को 0 या 1 पर सरल करके <math>AA=A, \overline{\overline{A}}=A, 1+A = 1</math>,और वितरण नियम को आगे बढ़ाता है। | |||
== | ==अधिसिद्धांत== | ||
डी मॉर्गन के प्रमेय | डी मॉर्गन के प्रमेय कहता है कि यदि कोई किसी [[बूलियन फ़ंक्शन]] के लिए दिए गए क्रम में निम्नलिखित करता है: | ||
* प्रत्येक चर को पूरक करें; | * प्रत्येक चर को पूरक करें; | ||
* '+' और '∙' | * '+' और '∙' संक्रियकोंं की अदला-बदली करें (संक्रियाओं का क्रम समान रहे को सुनिश्चित करने के लिए कोष्ठक जोड़ने का ध्यान रखें); | ||
*परिणाम को पूरक करें, | *परिणाम को पूरक करें, | ||
परिणाम | परिणाम इस [[तार्किक तुल्यता|तर्क की दृष्टि से तुल्य]] है जो आपने शुरू किया।एक फ़ंक्शन के कुछ हिस्सों में डी मॉर्गन प्रमेय के पुनरावर्ती अनुप्रयोग का उपयोग सभी पूरकों को अलग-अलग चर तक ले जाने के लिए किया जा सकता है। | ||
एक शक्तिशाली और | एक शक्तिशाली और असाधारण [[रूपक सिद्धांत|अधिसिद्धांत]] कहता है कि '''2''' की कोई भी सर्वसमिका सभी बूलियन बीजगणित के लिए मान्य है।<ref>{{Cite book |doi = 10.1007/978-0-387-68436-9|title = बूलियन बीजगणित का परिचय|series = Undergraduate Texts in Mathematics|year = 2009|last1 = Halmos|first1 = Paul|last2 = Givant|first2 = Steven|isbn = 978-0-387-40293-2}}</ref>इसके विपरीत,एक सर्वसमिका जो एक यादृच्छिक असाधारण बूलियन बीजगणित के लिए होती है,वह '''2''' में भी होती है।इसलिए बूलियन बीजगणित की सभी पहचान '''2''' द्वारा अधिकृत की जाती हैं।यह प्रमेय उपयोगी है क्योंकि '''2''' में किसी भी समीकरण को निर्णय प्रक्रिया द्वारा सत्यापित किया जा सकता है।तर्कशास्त्री इस तथ्य "'''2''' निर्धारणीय है" के रूप में संदर्भित करते हैं।सभी ज्ञात निर्णय प्रक्रियाओं के लिए कई चरणों की आवश्यकता होती है जो सत्यापित किए जाने वाले N चरों की संख्या के एक चरघातांकी फलन समीकरण में होती है।क्या कोई निर्णय प्रक्रिया मौजूद है जिसके चरण N के बहुपद फलन P = NP अनुमान के अंतर्गत आते है। | ||
यदि हम केवल परमाणु सकारात्मक समानताओं के बजाय अधिक सामान्य [[प्रथम-क्रम तर्क]] सूत्रों की वैधता पर विचार करते | उपरोक्त अधिसिद्धांत मान्य नहीं है यदि हम केवल परमाणु सकारात्मक समानताओं के बजाय अधिक सामान्य [[प्रथम-क्रम तर्क]] सूत्रों की वैधता पर विचार करते हैं।उदाहरण के तौर पर सूत्र {{math|1=(''x'' = 0) ∨ (''x'' = 1)}} पर विचार करें।यह सूत्र दो-अवयव बूलियन बीजगणित में हमेशा सत्य होता है।चार-अवयव बूलियन बीजगणित में जिसका डोमेन घात समुच्चय {{tmath|\{0,1\} }} है, यह सूत्र {{math|1=(''x'' = ∅) ∨ (''x'' = {{mset|0,1}})}} कथन से मेल खाता है और जब x {{tmath|\{1\} }}होता है पर असत्य होता है।[[बूलियन बीजगणित]] के कई वर्गों के [[प्रथम-क्रम सिद्धांत]] के लिए निर्णायकता को अभी भी परिमाणक उन्मूलन या छोटे मॉडल गुण धर्म(डोमेन आकार के साथ गणना सूत्र के एक फ़ंक्शन के रूप की जाती है और व्यापक रुप में 2 से बड़ा) का उपयोग करके दिखाया जा सकता है। | ||
<!--==Minterms and minimum two level forms== | <!--==Minterms and minimum two level forms== | ||
Any Boolean expression can be written as a series of [[minterm]]s added together--> | Any Boolean expression can be written as a series of [[minterm]]s added together--> | ||
Revision as of 07:22, 6 July 2023
गणित और गूढ़ बीजगणित में, दो-अवयव बूलियन बीजगणित बूलियन बीजगणित (संरचना) है जिसका अंतर्निहित सेट(या यूनिवर्स या वाहक)B बूलियन डोमेन है।चलन के अनुसार बूलियन डोमेन के तत्व 1 और 0 हैं,जिसके वजह से B= {0, 1}।इस बीजगणित "2" के लिए पॉल हल्मोस के नाम का साहित्य में कुछ अनुसरण किया जाता है,और इसे यहां नियोजित किया जाएगा।
परिभाषा
B एक अंशतः क्रमित सेट है और B के अवयव भी इसके परिबद्ध हैं।
एरिटी n की एक संक्रिया Bn से B तक एक प्रतिचित्रण है।बूलियन बीजगणित में दो द्विआधारी संक्रियाएं और एकल पूरण होते हैं।द्विआधारी संक्रियाओं को विभिन्न तरीकों से नामित और नोट किया गया है। यहां उन्हें 'योग' और 'उत्पाद' कहा जाता है,और मध्यप्रत्यय द्वारा क्रमशः'+' और '∙' नोट किया जाता है।योग और उत्पाद बदलना और जोड़ना,जैसा कि वास्तविक संख्याओं के सामान्य बीजगणित में होता है।संक्रियाओं के क्रम के लिए,यदि उपस्थित हो तो कोष्ठक निर्णायक होते हैं।अन्यथा '∙','+' से पहले आता है।इस तरह (A ∙ B) + C की A ∙ B + C के रूप में पद व्याख्या की गई और A ∙ (B + C) के रूप में नहीं।पूरकता को उसके स्वतंत्र चर पर एक ओवरबार लिखकर दर्शाया जाता है।X के पूरक का संख्यात्मक तुल्यरूप 1 − X है।व्यापक बीजगणित की भाषा में,एक बूलियन बीजगणित,प्रकार की एकबीजगणित है एरिटी की बीजगणितीय संरचना {0,1} और {सही, गलत} के बीच एक-से-एक पत्राचार समीकरणात्मक रूप में शास्त्रीय द्विसंयोजक तर्क उत्पन्न करता है, पूरकता को तार्किक नहीं के रूप में पढ़ा जाता है। यदि 1 को सत्य के रूप में पढ़ा जाता है, तो '+' को तार्किक OR के रूप में पढ़ा जाता है, और '∙' को तार्किक AND के रूप में पढ़ा जाता है, और इसके विपरीत यदि 1 को गलत के रूप में पढ़ा जाता है। ये दो ऑपरेशन एक क्रमविनिमेय मोटी हो जाओ को परिभाषित करते हैं, जिसे बूलियन सेमीरिंग के रूप में जाना जाता है।
कुछ मूलभूत सर्वसमिकाएँ
2 को निम्नलिखित साधारण बूलियन अंकगणित के आधार पर देखा जा सकता है:
नोट करें कि:
- '+' और '∙',1+1=1 के अलावा बिल्कुल संख्यात्मक अंकगणित की तरह काम करते हैं। '+' और '∙' संख्यात्मक अंकगणित से समतुल्यता द्वारा प्राप्त किए गए हैं;ऐसे हि किसी भी अशून्य संख्या को 1 पर निर्धारित करें।
- 0 और 1, और '+' और '∙' की अदला-बदली सत्य को सुरक्षित रखती है;यह सभी बूलियन बीजगणित में व्याप्त द्वैतता का सार है।
यह बूलियन अंकगणित 2 के किसी भी समीकरण को,स्वयंसिद्ध सहित,प्रत्येक चर के लिए 0s और 1s के प्रत्येक संभावित निर्धारण की जांच से सत्यापित करने के लिए पर्याप्त है(निर्णय प्रक्रिया देखें)।
निम्नलिखित समीकरण अब सत्यापित किए जा सकते हैं:
'+' और '∙' में से प्रत्येक का दूसरे पर वितरण:
वह '∙','+' पर वितरित होता है जो प्राथमिक बीजगणित से सहमत है,लेकिन '∙' पर '+' नहीं। इस और अन्य कारणों से,उत्पादों का योग (NAND संश्लेषण के लिए अग्रणी) साधारणतः योगों के उत्पाद (NOR संश्लेषण के लिए अग्रणी) की तुलना में अधिक नियोजित होता है।
'+' और '∙' में से प्रत्येक को दूसरे और पूरकता के संदर्भ में परिभाषित किया जा सकता है:
हमें केवल एक द्विआधारी संक्रिया की आवश्यकता है,और इसे दर्शाने के लिए संयोजन पर्याप्त है। इसलिए संयोजन और ओवरबार 2 को नोट करने के लिए पर्याप्त हैं। यह संकेतन क्विन के बूलियन शब्द स्कीमाटा का भी है।(X) को X के पूरक को निरूपित करने और ()" को 0 या 1 को निरूपित करने से जी.स्पेंसर-ब्राउन के फॉर्म के नियम के प्राथमिक बीजगणित का वाक्य-विन्यास प्राप्त होता है।
2 के लिए समीकरणों का सेट एकआधारक है,जिसे अभिगृहीत कहा जाता है,जिससे उपरोक्त सभी समीकरण (और अधिक) प्राप्त किए जा सकते हैं।सभी बूलियन बीजगणित के लिए और इस कारण से 2 के लिए कई ज्ञात आधार हैं। केवल संयोजन और ओवरबार का उपयोग करके नोट किया गया एक सुंदर आधार है:
- (संयोजन आवागमन,संगुणित होना)
- (2 एक पूरित जाली है,1 के उपरिपरिबंध के साथ)
- (0 निम्न परिबंध है)।
- (2 एक वितरणात्मक जाली है)
जहां संयोजन = OR,1 = सत्य,और 0 = असत्य,या संयोजन=AND,1 = असत्य,और 0 = सत्य। (ओवरबार दोनों ही मामलों में निषेध है।)
यदि 0=1, (1)-(3) एबेलियन समूह के लिए अभिगृहीत हैं।
(1) केवल संयोजन आवागमन और संगुणित सिद्ध करने का काम करता है।पहले मान लें कि(1) बाएँ या दाएँ से संगुणित है,फिर क्रमविनिमेयता सिद्ध करें। फिर दूसरी दिशा से संबंध सिद्ध करें। संबद्धता केवल बाएँ और दाएँ संयुक्त रूप से जुड़ा होना है।
इस आधार पर सिद्ध के लिए एक आसान तरीका बनाता है, जिसे फॉर्म के नियम में "गणना" कहा जाता है,जो कि अभिगृहीतों (2)-(4) का उपयोग करके और प्रारंभिक सर्वसमिकाओं के व्यंजकों को 0 या 1 पर सरल करके ,और वितरण नियम को आगे बढ़ाता है।
अधिसिद्धांत
डी मॉर्गन के प्रमेय कहता है कि यदि कोई किसी बूलियन फ़ंक्शन के लिए दिए गए क्रम में निम्नलिखित करता है:
- प्रत्येक चर को पूरक करें;
- '+' और '∙' संक्रियकोंं की अदला-बदली करें (संक्रियाओं का क्रम समान रहे को सुनिश्चित करने के लिए कोष्ठक जोड़ने का ध्यान रखें);
- परिणाम को पूरक करें,
परिणाम इस तर्क की दृष्टि से तुल्य है जो आपने शुरू किया।एक फ़ंक्शन के कुछ हिस्सों में डी मॉर्गन प्रमेय के पुनरावर्ती अनुप्रयोग का उपयोग सभी पूरकों को अलग-अलग चर तक ले जाने के लिए किया जा सकता है।
एक शक्तिशाली और असाधारण अधिसिद्धांत कहता है कि 2 की कोई भी सर्वसमिका सभी बूलियन बीजगणित के लिए मान्य है।[1]इसके विपरीत,एक सर्वसमिका जो एक यादृच्छिक असाधारण बूलियन बीजगणित के लिए होती है,वह 2 में भी होती है।इसलिए बूलियन बीजगणित की सभी पहचान 2 द्वारा अधिकृत की जाती हैं।यह प्रमेय उपयोगी है क्योंकि 2 में किसी भी समीकरण को निर्णय प्रक्रिया द्वारा सत्यापित किया जा सकता है।तर्कशास्त्री इस तथ्य "2 निर्धारणीय है" के रूप में संदर्भित करते हैं।सभी ज्ञात निर्णय प्रक्रियाओं के लिए कई चरणों की आवश्यकता होती है जो सत्यापित किए जाने वाले N चरों की संख्या के एक चरघातांकी फलन समीकरण में होती है।क्या कोई निर्णय प्रक्रिया मौजूद है जिसके चरण N के बहुपद फलन P = NP अनुमान के अंतर्गत आते है।
उपरोक्त अधिसिद्धांत मान्य नहीं है यदि हम केवल परमाणु सकारात्मक समानताओं के बजाय अधिक सामान्य प्रथम-क्रम तर्क सूत्रों की वैधता पर विचार करते हैं।उदाहरण के तौर पर सूत्र (x = 0) ∨ (x = 1) पर विचार करें।यह सूत्र दो-अवयव बूलियन बीजगणित में हमेशा सत्य होता है।चार-अवयव बूलियन बीजगणित में जिसका डोमेन घात समुच्चय है, यह सूत्र (x = ∅) ∨ (x = {0,1}) कथन से मेल खाता है और जब x होता है पर असत्य होता है।बूलियन बीजगणित के कई वर्गों के प्रथम-क्रम सिद्धांत के लिए निर्णायकता को अभी भी परिमाणक उन्मूलन या छोटे मॉडल गुण धर्म(डोमेन आकार के साथ गणना सूत्र के एक फ़ंक्शन के रूप की जाती है और व्यापक रुप में 2 से बड़ा) का उपयोग करके दिखाया जा सकता है।
यह भी देखें
- बूलियन बीजगणित
- बाउंडेड सेट
- जाली (आदेश)
- आदेश सिद्धांत
संदर्भ
- ↑ Halmos, Paul; Givant, Steven (2009). बूलियन बीजगणित का परिचय. Undergraduate Texts in Mathematics. doi:10.1007/978-0-387-68436-9. ISBN 978-0-387-40293-2.
अग्रिम पठन
Many elementary texts on Boolean algebra were published in the early years of the computer era. Perhaps the best of the lot, and one still in print, is:
- Mendelson, Elliot, 1970. Schaum's Outline of Boolean Algebra. McGraw–Hill.
The following items reveal how the two-element Boolean algebra is mathematically nontrivial.
- Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra," by J. Donald Monk.
- Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
