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

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

परिभाषा

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

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

{0,1} और {सही, गलत} के बीच एक-से-एक पत्राचार समीकरणात्मक रूप में शास्त्रीय द्विसंयोजक तर्क उत्पन्न करता है, पूरकता को तार्किक नहीं के रूप में पढ़ा जाता है। यदि 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, और '+' और '∙' की अदला-बदली सत्य को सुरक्षित रखती है; यह सभी बूलियन बीजगणित में व्याप्त द्वैत (आदेश सिद्धांत) का सार है।

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

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

${\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).$

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

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

• $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 = असत्य, या संयोजन = और, 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 निर्णायकता (तर्क) कहते हैं। सभी ज्ञात निर्णय प्रक्रियाओं के लिए कई चरणों की आवश्यकता होती है जो सत्यापित किए जाने वाले समीकरण में दिखाई देने वाले चर एन की संख्या का एक घातीय कार्य है। क्या कोई निर्णय प्रक्रिया मौजूद है जिसके चरण एन का बहुपद फलन हैं, पी = एनपी अनुमान के अंतर्गत आता है।

यदि हम केवल परमाणु सकारात्मक समानताओं के बजाय अधिक सामान्य प्रथम-क्रम तर्क सूत्रों की वैधता पर विचार करते हैं तो उपरोक्त मेटाथ्योरम मान्य नहीं है। उदाहरण के तौर पर सूत्र पर विचार करें (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.