दो-अवयव बूलियन बीजगणित

गणित और अमूर्त बीजगणित में,दो-अवयव बूलियन बीजगणित,बूलियन बीजगणित है जिसकाअंतर्निहित समुच्चय (या सर्वनिष्ट या वाहक) B बूलियन डोमेन है।चलन के अनुसार बूलियन डोमेन के तत्व 1 और 0 हैं,जिसके वजह से B= {0, 1}।इस बीजगणित "2" के लिए पॉल हल्मोस के नाम का साहित्य में कुछ अनुसरण किया जाता है,और यहां इसे नियोजित किया जाएगा।

परिभाषा

B एक अंशतः क्रमित समुच्चय है और B के अवयव भी इससे परिबद्ध हैं।

एरिटी n की एक संक्रिया Bⁿ से B तक एक प्रतिचित्रण है।बूलियन बीजगणित में दो द्विआधारी संक्रियाएं और एकल पूरकता होती हैं।द्विआधारी संक्रियाओं को विभिन्न तरीकों से नामित और नोट किया गया है।यहां उन्हें 'योग' और 'उत्पाद' कहा जाता है,और मध्यप्रत्यय द्वारा क्रमशः'+' और '∙' नोट किया जाता है।योग और उत्पाद बदलना और जोड़ना,जैसा कि वास्तविक संख्याओं के सामान्य बीजगणित में होता है।संक्रियाओं के क्रम के लिए,यदि उपस्थित हो तो कोष्ठक निर्णायक होते हैं।अन्यथा '∙','+' से पहले आता है।इस तरह (A ∙ B) + C की A ∙ B + C के रूप में पद व्याख्या की गई और A ∙ (B + C) के रूप में नहीं।पूरकता को उसके स्वतंत्र चर पर एक ओवरबार लिखकर दर्शाया जाता है।X के पूरक का संख्यात्मक तुल्यरूप 1 − X है।व्यापक बीजगणित की भाषा में,एक बूलियन बीजगणित,$\langle 2,2,1,0,0\rangle$प्रकार की एक$\langle B,+,.,{\overline {..}},1,0\rangle$बीजगणित है।

या तो {0,1} और या तो {सही, गलत} के बीच एक-एक पत्राचार प्राचीन द्विसंयोजी तर्क से समीकरण विषयक रूप में बदलता है,पूरकता के साथ NOT के रूप में पढ़ें।यदि 1 को सत्य के रूप में पढ़ा जाता है,'+' को OR के रूप में पढ़ा जाता है,और '∙' को AND के रूप में पढ़ा जाता है,और इसके विपरीत क्रम से यदि 1 को गलत के रूप में पढ़ा जाए।ये दो संक्रियाएं एक क्रम विनिमय सेमीरिंग को परिभाषित करती हैं,जिसे बूलियन सेमीरिंग के रूप में जाना जाता है।

कुछ मूलभूत सर्वसमिकाएँ

2 को निम्नलिखित साधारण बूलियन अंकगणित के आधार पर देखा जा सकता है:

${\begin{aligned}&1+1=1+0=0+1=1\\&0+0=0\\&0\cdot 0=0\cdot 1=1\cdot 0=0\\&1\cdot 1=1\\&{\overline {1}}=0\\&{\overline {0}}=1\end{aligned}}$

नोट करें कि:

• '+' और '∙',1+1=1 के अलावा बिल्कुल संख्यात्मक अंकगणित की तरह काम करते हैं। '+' और '∙' संख्यात्मक अंकगणित से समतुल्यता द्वारा प्राप्त किए गए हैं;ऐसे ही किसी भी शून्येतर संख्या को 1 पर निर्धारित करें।
• 0 और 1,और '+' और '∙' की अदला-बदली सत्य को सुरक्षित रखती है;यह सभी बूलियन बीजगणित में व्याप्त द्वैतता का सार है।

यह बूलियन अंकगणित 2 के किसी भी समीकरण को,अभिगृहीत सहित,प्रत्येक चर के लिए 0 और 1 के प्रत्येक संभावित निर्धारण की जांच से सत्यापित करने के लिए पर्याप्त है(निर्णय प्रक्रिया देखें)।

निम्नलिखित समीकरण अब सत्यापित किए जा सकते हैं:

${\begin{aligned}&A+A=A\\&A\cdot A=A\\&A+0=A\\&A+1=1\\&A\cdot 0=0\\&{\overline {\overline {A}}}=A\end{aligned}}$

'+' और '∙' में से प्रत्येक का दूसरे पर वितरण:

• $\ A\cdot (B+C)=A\cdot B+A\cdot C;$
• $\ A+(B\cdot C)=(A+B)\cdot (A+C).$

वह '∙','+' पर वितरित होता है जो प्राथमिक बीजगणित से सहमत है,लेकिन '∙' पर '+' नहीं। इस और अन्य कारणों से,उत्पादों का योग (NAND संश्लेषण के लिए अग्रणी) साधारणतः योगों के उत्पाद (NOR संश्लेषण के लिए अग्रणी) की तुलना में अधिक नियोजित होता है।

'+' और '∙' में से प्रत्येक को दूसरे और पूरकता के संदर्भ में परिभाषित किया जा सकता है:

• $A\cdot B={\overline {{\overline {A}}+{\overline {B}}}}$
• $A+B={\overline {{\overline {A}}\cdot {\overline {B}}}}.$

हमें केवल एक द्विआधारी संक्रिया की आवश्यकता है,और इसे दर्शाने के लिए संयोजन पर्याप्त है।इसलिए 2 को नोट करने के लिए संयोजन और ओवरबार पर्याप्त हैं।यह संकेतन क्विन के बूलियन शब्द स्कीमेता का भी है।माना कि (X), X के पूरक को निरूपित करे और "()" को 0 या 1 को निरूपित करे तो जी.स्पेंसर-ब्राउन के फॉर्म के नियम के प्राथमिक बीजगणित का वाक्य-विन्यास परिवर्तित होता है।

2 के लिए समीकरणों का सेट एकआधार है,जिसे अभिगृहीत कहा जाता है,जिससे उपरोक्त सभी समीकरण (और अधिक) प्राप्त किए जा सकते हैं।सभी बूलियन बीजगणित के लिए और इस कारण से 2 के लिए कई ज्ञात आधार हैं।केवल संयोजन और ओवरबार का उपयोग करके नोट किया गया एक सुंदर आधार है:

1. $\ ABC=BCA$ (संयोजन आवागमन,संगुणित होना)
2. ${\overline {A}}A=1$ (2 एक पूरित जाली है,1 के उपरिपरिबंध के साथ)
3. $\ A0=A$ (0 निम्न-परिबंध है)।
4. $A{\overline {AB}}=A{\overline {B}}$ (2 एक वितरणात्मक जाली है)

जहां संयोजन = OR,1 = सत्य,और 0 = असत्य,या संयोजन=AND,1 = असत्य,और 0 = सत्य। (ओवरबार दोनों ही मामलों में निषेध है।)

यदि 0=1,(1)-(3) एबेलियन समूह के लिए अभिगृहीत हैं।

(1) केवल संयोजन आवागमन और संगुणित सिद्ध करने का काम करता है।पहले मान लें कि(1) बाएँ या दाएँ से संगुणित है,फिर क्रमविनिमेयता सिद्ध करें। फिर दूसरी दिशा से संबंध सिद्ध करें। संबद्धता केवल बाएँ और दाएँ संयुक्त रूप में जुड़ा होना है।

इस आधार पर यह परिमाण के लिए एक आसान तरीका बनाता है,जिसे फॉर्म के नियम में "गणना" कहा जाता है,जो कि (2)-(4) अभिगृहीतों का उपयोग करके और प्रारंभिक सर्वसमिकाओं के व्यंजकों को 0 या 1 पर सरल करके $AA=A,{\overline {\overline {A}}}=A,1+A=1$,और वितरण नियम को आगे बढ़ाता है।

अधिसिद्धांत

डी मॉर्गन का सिद्धांत कहता है कि यदि कोई दिए गए क्रम में किसी बूलियन फ़ंक्शन के लिए निम्नलिखित करता है:

• प्रत्येक चर को पूरक करें;
• '+' और '∙' संक्रियकोंं की अदला-बदली करें (संक्रियाओं का क्रम समान रहे ऐसा सुनिश्चित करने के लिए कोष्ठक जोड़ने का ध्यान रखें);
• परिणाम को पूरक करें,

परिणाम इस तर्क की दृष्टि से तुल्य है जो आपने शुरू किया।एक फ़ंक्शन के कुछ हिस्सों में डी मॉर्गन प्रमेय के पुनरावर्ती अनुप्रयोग का उपयोग सभी पूरकों को अलग-अलग चर तक ले जाने के लिए किया जा सकता है।

एक शक्तिशाली और असाधारण अधिसिद्धांत कहता है कि 2 की कोई भी सर्वसमिका सभी बूलियन बीजगणित के लिए मान्य है।इसके विपरीत,एक सर्वसमिका जो एक यादृच्छिक असाधारण बूलियन बीजगणित के लिए होती है,वह 2 में भी होती है।इसलिए बूलियन बीजगणित की सभी पहचान 2 द्वारा अधिकृत की जाती हैं।यह प्रमेय उपयोगी है क्योंकि 2 में किसी भी समीकरण को निर्णय प्रक्रिया द्वारा सत्यापित किया जा सकता है।तर्कशास्त्री इस तथ्य "2 निर्धारणीय है" के रूप में संदर्भित करते हैं।सभी ज्ञात निर्णय प्रक्रियाओं के लिए कई चरणों की आवश्यकता होती है जो सत्यापित किए जाने वाले N चरों की संख्या के एक चरघातांकी फलन समीकरण में होती है।क्या कोई निर्णय प्रक्रिया मौजूद है जिसके चरण N के बहुपद फलन,P = NP अनुमान के अंतर्गत आते है?

उपरोक्त अधिसिद्धांत मान्य नहीं है यदि हम केवल परमाण्वीय सकारात्मक समानताओं के अलावा अधिक सामान्य प्रथम-क्रम तर्क सूत्रों की वैधता पर विचार करते हैं।उदाहरण के तौर पर सूत्र (x = 0) ∨ (x = 1) पर विचार करें।यह सूत्र दो-अवयव बूलियन बीजगणित में हमेशा सत्य होता है।चार-अवयव बूलियन बीजगणित में जिसका डोमेन घात समुच्चय $\{0,1\}$ है,यह सूत्र (x = ∅) ∨ (x = {0,1}) कथन से मेल खाता है और जब x,$\{1\}$होता है पर कथन असत्य होता है।बूलियन बीजगणित के कई वर्गों के प्रथम-क्रम सिद्धांत के लिए निर्णायकता को अभी भी परिमाणक उन्मूलन या छोटे मॉडल गुण धर्म(डोमेन आकार के साथ गणना सूत्र के एक फ़ंक्शन के रूप की जाती है और व्यापक रुप में 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.