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

गणितऔरअमूर्त बीजगणित में,द्वि-तत्वीय बूलियन बीजगणित वह बूलियन बीजगणित है जिसकाअंतर्निहित समुच्चय (या यूनिवर्स या वाहक)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 को दर्शाने के लिए इस्तेमाल करना,G.स्पेंसर-ब्राउन के "फॉर्म के नियम" की प्राथमिक बीजी बीजगणित की सिन्टैक्स देता है।

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) बाएं या दाएं से संघटित होता है, फिर सम्मुखता साबित करें।फिर दूसरे दिशा से सम्मुखता साबित करें। सम्मुखता सामरिकता केवल बाएं और दाएं से संघटित होने का संयोजन है।

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

अधिसिद्धांत

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

• प्रत्येक चर का पूरक लें;
• '+' और '∙' आपरेशन को बदलें (संचालन के क्रम को सुनिश्चित करने के लिए ब्रैकेट जोड़ें);
• परिणाम का पूरक लें,

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

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

उपरोक्त मेटाथियोरेम उस स्थिति में सही नहीं है,जब हम केवल परमाणुक धनात्मक समानताओं के स्वीकृति की अलावाऔरअधिक सामान्य प्रथम-क्रम तर्क सूत्रों की मान्यता को विचार करते हैं।एक उदाहरण के रूप में मान लें सूत्र(x = 0) ∨ (x = 1)।सूत्र का द्वी-तत्वीय बूलियन बीजी बहुपद में हमेशा सत्य होता है।जबकि 4-तत्वीय बूलियन बीजी बहुपद में, जिसका डोमेन $\{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.