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

गणितऔरअमूर्त बीजगणित में,द्वि-तत्वीय बूलियन बीजगणित वह बूलियन बीजगणित है जिसकाअंतर्निहित समुच्चय (या यूनिवर्स या वाहक)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.