बूलियन बीजगणित (संरचना)

For an introduction to the subject, see Boolean algebra. For an alternative presentation, see Boolean algebras canonically defined.

सार बीजगणित में, एक बूलियन बीजगणित या बूलियन जाली एक पूरक जाली वितरण जाली है। इस प्रकार की बीजगणितीय संरचना सेट (गणित) संचालन और तर्क संचालन दोनों के आवश्यक गुणों को पकड़ती है। एक बूलियन बीजगणित को सत्ता स्थापित बीजगणित या सेट के क्षेत्र के सामान्यीकरण के रूप में देखा जा सकता है, या इसके तत्वों को सामान्यीकृत सत्य मूल्यों के रूप में देखा जा सकता है। यह डी मॉर्गन बीजगणित और क्लेन बीजगणित (इनवोल्यूशन के साथ) का एक विशेष मामला भी है।

प्रत्येक बूलियन बीजगणित #बूलियन एक बूलियन रिंग में बजता है, और इसके विपरीत, रिंग (गणित) गुणन के साथ तार्किक संयोजन या मीट (गणित) ∧ के अनुरूप होता है, और विशेष या सममित अंतर (तार्किक संयोजन ∨ नहीं) के लिए रिंग जोड़। हालांकि, बूलियन रिंग्स के सिद्धांत में दो संचालकों के बीच एक अंतर्निहित विषमता है, जबकि बूलियन बीजगणित के स्वयंसिद्ध और प्रमेय द्वैत सिद्धांत (बूलियन बीजगणित) द्वारा वर्णित सिद्धांत की समरूपता को व्यक्त करते हैं।

सबसेट की बूलियन जाली

इतिहास

बूलियन बीजगणित शब्द जॉर्ज बूले (1815-1864), एक स्व-शिक्षित अंग्रेजी गणितज्ञ का सम्मान करता है। उन्होंने ऑगस्टस डी मॉर्गन और सर विलियम हैमिल्टन, 9वें बैरोनेट के बीच चल रहे एक सार्वजनिक विवाद के जवाब में 1847 में प्रकाशित एक छोटे से पैम्फलेट, द मैथमेटिकल एनालिसिस ऑफ लॉजिक में बीजगणितीय प्रणाली की शुरुआत की, और बाद में एक अधिक महत्वपूर्ण पुस्तक द लॉज़ ऑफ लॉजिक के रूप में। विचार, 1854 में प्रकाशित। बूल का सूत्रीकरण कुछ महत्वपूर्ण मामलों में ऊपर वर्णित से भिन्न है। उदाहरण के लिए, बूल में संयुग्मन और वियोग संचालन की एक दोहरी जोड़ी नहीं थी। 1860 के दशक में विलियम जेवन्स और चार्ल्स सैंडर्स पियर्स द्वारा लिखे गए पत्रों में बूलियन बीजगणित उभरा। बूलियन बीजगणित और वितरणात्मक जाली की पहली व्यवस्थित प्रस्तुति अर्न्स्ट श्रोडर (गणितज्ञ) के 1890 वोरलेसुंगेन |अर्न्स्ट श्रोडर के लिए बकाया है। अंग्रेजी में बूलियन बीजगणित का पहला व्यापक उपचार ए. एन. व्हाइटहेड का 1898 यूनिवर्सल बीजगणित है। आधुनिक स्वयंसिद्ध अर्थ में एक स्वयंसिद्ध बीजगणितीय संरचना के रूप में बूलियन बीजगणित एडवर्ड वी. हंटिंगटन द्वारा 1904 के पेपर से शुरू होता है। 1930 के दशक में मार्शल स्टोन के काम और गैरेट बिरखॉफ के 1940 के लैटिस थ्योरी के साथ बूलियन बीजगणित गंभीर गणित के रूप में सामने आया। 1960 के दशक में, पॉल कोहेन (गणितज्ञ), दाना स्कॉट, और अन्य लोगों ने गणितीय तर्क और स्वयंसिद्ध सेट सिद्धांत में बूलियन बीजगणित की शाखाओं का उपयोग करते हुए गहन नए परिणाम प्राप्त किए, अर्थात् बल (गणित) और बूलियन-मूल्यवान मॉडल।

परिभाषा

एक बूलियन बीजगणित एक छह-टपल है जिसमें एक सेट (गणित) ए होता है, जो दो बाइनरी ऑपरेशन से लैस होता है ∧ (जिसे मीट या कहा जाता है), ∨ (जॉइन या या कहा जाता है), एक एकात्मक ऑपरेशन ¬ (कहा जाता है पूरक या not ) और A में दो तत्व 0 और 1 (नीचे और ऊपर , या कम से कम और सबसे बड़ा तत्व कहा जाता है, जिन्हें क्रमशः ⊥ और ⊤ प्रतीकों द्वारा भी निरूपित किया जाता है), जैसे कि सभी तत्वों के लिए a, ' 'ए' का 'बी' और 'सी', निम्नलिखित स्वयंसिद्ध हैं:

a ∨ (b ∨ c) = (a ∨ b) ∨ c	a ∧ (b ∧ c) = (a ∧ b) ∧ c	associativity
a ∨ b = b ∨ a	a ∧ b = b ∧ a	commutativity
a ∨ (a ∧ b) = a	a ∧ (a ∨ b) = a	absorption
a ∨ 0 = a	a ∧ 1 = a	identity
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)	a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)	distributivity
a ∨ ¬a = 1	a ∧ ¬a = 0	complements

ध्यान दें, हालांकि, अवशोषण कानून और यहां तक ​​​​कि सहयोगीता कानून को सिद्धांतों के सेट से बाहर रखा जा सकता है क्योंकि उन्हें अन्य सिद्धांतों से प्राप्त किया जा सकता है (#Axiomatics देखें)।

एक बूलियन बीजगणित केवल एक तत्व के साथ एक तुच्छ बूलियन बीजगणित या पतित बूलियन बीजगणित कहा जाता है। (पुराने कार्यों में, कुछ लेखकों को इस मामले को बाहर करने के लिए 0 और 1 को 'अलग' तत्व होने की आवश्यकता थी।) यह ऊपर दिए गए स्वयंसिद्धों के अंतिम तीन जोड़े (पहचान, वितरण और पूरक) से आता है, या अवशोषण स्वयंसिद्ध से, कि

a = b ∧ a     अगर और केवल अगर     a ∨ b = b।

संबंध ≤ a ≤ b द्वारा परिभाषित यदि ये समतुल्य स्थितियां धारण करती हैं, तो कम से कम तत्व 0 और सबसे बड़ा तत्व 1 के साथ एक आंशिक क्रम है। a ∧ b मिलते हैं और दो तत्वों के a ∨ b में शामिल होते हैं, क्रमशः उनके न्यूनतम और उच्चतम के साथ मेल खाते हैं, ≤ के संबंध में।

स्वयंसिद्धों के पहले चार जोड़े एक परिबद्ध जाली की परिभाषा का निर्माण करते हैं।

यह स्वयंसिद्धों के पहले पाँच युग्मों से अनुसरण करता है कि कोई भी पूरक अद्वितीय है।

स्वयंसिद्धों का समुच्चय द्वैत (आदेश सिद्धांत)|स्व-द्वैत इस अर्थ में है कि यदि कोई ∨ को ∧ और 0 को 1 के साथ एक अभिगृहीत में बदलता है, तो परिणाम फिर से एक अभिगृहीत होता है। इसलिए, इस संक्रिया को एक बूलियन बीजगणित (या बूलियन जाली) पर लागू करके, समान तत्वों के साथ एक और बूलियन बीजगणित प्राप्त करता है; इसे इसका 'द्वैत' कहा जाता है।

उदाहरण

• सबसे सरल गैर-तुच्छ बूलियन बीजगणित, दो-तत्व बूलियन बीजगणित में केवल दो तत्व हैं, 0 और 1, और नियमों द्वारा परिभाषित किया गया है:

∧ 0 1 0 0 0 1 0 1

∨ 0 1 0 0 1 1 1 1

a 0 1 ¬a 1 0

• इसके तर्क में अनुप्रयोग हैं, 0 को असत्य के रूप में, 1 को सत्य के रूप में, ∧ को और, ∨ को या, और ¬ को नहीं के रूप में व्याख्या करते हुए। वेरिएबल्स और बूलियन ऑपरेशंस से जुड़े एक्सप्रेशंस स्टेटमेंट फॉर्म का प्रतिनिधित्व करते हैं, और ऐसे दो एक्सप्रेशंस को उपरोक्त एक्सिओम्स का उपयोग करके बराबर दिखाया जा सकता है अगर और केवल अगर संबंधित स्टेटमेंट फॉर्म तार्किक तुल्यता हैं।

• विद्युत अभियन्त्रण में सर्किट डिजाइन के लिए दो-तत्व बूलियन बीजगणित का भी उपयोग किया जाता है; यहां 0 और 1 डिजिटल सर्किट में एक अंश के दो अलग-अलग राज्यों का प्रतिनिधित्व करते हैं, आमतौर पर उच्च और निम्न वोल्टेज। सर्किट को वेरिएबल्स वाले एक्सप्रेशन द्वारा वर्णित किया जाता है, और ऐसे दो एक्सप्रेशंस वेरिएबल्स के सभी मानों के लिए समान होते हैं यदि और केवल तभी संबंधित सर्किट में समान इनपुट-आउटपुट व्यवहार होता है। इसके अलावा, हर संभव इनपुट-आउटपुट व्यवहार को एक उपयुक्त बूलियन अभिव्यक्ति द्वारा प्रतिरूपित किया जा सकता है।

* बूलियन बीजगणित के सामान्य सिद्धांत में दो-तत्व बूलियन बीजगणित भी महत्वपूर्ण है, क्योंकि कई चर वाले समीकरण आम तौर पर सभी बूलियन बीजगणित में सत्य होते हैं यदि और केवल यदि यह दो-तत्व बूलियन बीजगणित में सत्य है (जो हो सकता है) चर की छोटी संख्या के लिए एक तुच्छ क्रूर बल खोज एल्गोरिथ्म द्वारा जाँच की गई)। उदाहरण के लिए इसका उपयोग यह दिखाने के लिए किया जा सकता है कि निम्नलिखित कानून (सर्वसम्मति प्रमेय) आम तौर पर सभी बूलियन बीजगणित में मान्य हैं:

• • (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)

** (ए ∧ बी) ∨ (¬ए ∧ सी) ∨ (बी ∧ सी) ≡ (ए ∧ बी) ∨ (¬ए ∧ सी)

• किसी दिए गए गैर-खाली सेट S का पावर सेट (सभी उपसमुच्चयों का सेट) एक बूलियन बीजगणित बनाता है, सेट का बीजगणित, दो संचालनों के साथ ∨ := ∪ (यूनियन) और ∧ := ∩ (चौराहा)। सबसे छोटा अवयव 0 रिक्त समुच्चय है और सबसे बड़ा अवयव 1 समुच्चय S ही है।

* दो-तत्व बूलियन बीजगणित के बाद, सबसे सरल बूलियन बीजगणित वह है जो दो परमाणुओं के शक्ति सेट द्वारा परिभाषित किया गया है:

∧ 0 a b 1 0 0 0 0 0 a 0 a 0 a b 0 0 b b 1 0 a b 1

∨ 0 a b 1 0 0 a b 1 a a a 1 1 b b 1 b 1 1 1 1 1 1

x 0 a b 1 ¬x 1 b a 0

• सेट $A$ के सभी उपसमूहों में से $S$ जो या तो परिमित या सहमित हैं एक बूलियन बीजगणित है और समुच्चयों का एक बीजगणित है जिसे परिमित-सीमित बीजगणित कहा जाता है। अगर $S$ अनंत है तो के सभी सहपरिमित उपसमुच्चय का समुच्चय $S,$ जिसे फ्रेचेट फिल्टर कहा जाता है, एक फ्री ultrafilter ऑन है $A.$ हालाँकि, Fréchet फ़िल्टर के पावर सेट पर एक अल्ट्राफ़िल्टर नहीं है $S.$ * κ वाक्य प्रतीकों के साथ प्रस्तावपरक कलन के साथ शुरू करते हुए, लिंडेनबाउम-टार्स्की बीजगणित (अर्थात, प्रस्तावक कलन मॉड्यूलो तार्किक तुल्यता में वाक्यों का सेट) का निर्माण करें। यह निर्माण एक बूलियन बीजगणित उत्पन्न करता है। यह वास्तव में κ जनरेटर पर मुक्त बूलियन बीजगणित है। प्रस्तावपरक कलन में एक सत्य असाइनमेंट तब इस बीजगणित से दो-तत्व बूलियन बीजगणित तक एक बूलियन बीजगणित समरूपता है।
• कम से कम तत्व के साथ किसी भी रैखिक रूप से आदेशित सेट L को देखते हुए, अंतराल बीजगणित L के सबसे छोटे बीजगणित का सबसे छोटा बीजगणित होता है जिसमें सभी आधे-खुले अंतराल होते हैं [a, b) जैसे कि a L में है और b या तो L में है या बराबर है से ∞। अंतराल बीजगणित लिंडेनबाउम-टार्स्की बीजगणित के अध्ययन में उपयोगी होते हैं; प्रत्येक गणनीय बूलियन बीजगणित एक अंतराल बीजगणित के लिए समरूप है।

30 के भाजक के बूलियन बीजगणित का x150px।

* किसी भी प्राकृतिक संख्या n के लिए, परिभाषित करने वाले n के सभी धनात्मक विभाजकों का समुच्चय $a\leq b$ यदि a, b को विभाजित करता है, तो एक वितरणात्मक जाली बनाता है। यह जाली एक बूलियन बीजगणित है अगर और केवल अगर n वर्ग मुक्त पूर्णांक | वर्ग मुक्त है। इस बूलियन बीजगणित का निचला और शीर्ष तत्व क्रमशः प्राकृतिक संख्या 1 और n है। a का पूरक n/a द्वारा दिया गया है। a और b का मिलना और जुड़ना क्रमशः a और b के सबसे बड़े सामान्य भाजक (gcd) और सबसे कम सामान्य गुणक (lcm) द्वारा दिया जाता है। रिंग जोड़ a+b lcm(a,b)/gcd(a,b) द्वारा दिया जाता है। चित्र n = 30 के लिए एक उदाहरण दिखाता है। एक प्रति-उदाहरण के रूप में, गैर-वर्ग-मुक्त n = 60 पर विचार करते हुए, 30 का सबसे बड़ा सामान्य विभाजक और इसका पूरक 2 2 होगा, जबकि यह निचला तत्व 1 होना चाहिए।

• बूलियन बीजगणित के अन्य उदाहरण टोपोलॉजी से उत्पन्न होते हैं: यदि X एक टोपोलॉजिकल स्पेस है, तो X के सभी उपसमुच्चयों का संग्रह, जो क्लोपेन सेट हैं, संचालन के साथ एक बूलियन बीजगणित बनाता है ∨ := ∪ (यूनियन) और ∧ := ∩ (चौराहा) ).
• अगर $R$ एक मनमाना वलय है तो इसका केंद्रीय आदर्शों का समुच्चय, जो समुच्चय है
  $$A=\left\{e\in R:e^{2}=e{\text{ and }}ex=xe\;{\text{ for all }}\;x\in R\right\},$$
  एक बूलियन बीजगणित बन जाता है जब इसके संचालन द्वारा परिभाषित किया जाता है $e\vee f:=e+f-ef$ और $e\wedge f:=ef.$

समरूपता और समरूपता

दो बूलियन बीजगणित A और B के बीच एक समाकारिता एक फलन (गणित) है f : A → B ऐसा कि A में सभी a, b के लिए:

f(a ∨ b) = f(a) ∨ f(b),

f(a ∧ b) = f(a) ∧ f(b),

एफ (0) = 0,

एफ (1) = 1।

इसके बाद यह अनुसरण करता है कि f(¬a) = ¬f(a) सभी a में A के लिए। सभी बूलियन बीजगणित का वर्ग (सेट सिद्धांत), आकृतिवाद की इस धारणा के साथ, जाली के श्रेणी सिद्धांत की एक पूर्ण उपश्रेणी बनाता है। दो बूलियन बीजगणित ए और बी के बीच एक समरूपता एक समाकारिता है f: A → B एक व्युत्क्रम समाकारिता के साथ, अर्थात्, एक समाकारिता g: B → A ऐसा है कि फ़ंक्शन रचना g ∘ f: A → A, A पर पहचान कार्य है , और रचना f ∘ g: B → B, B पर पहचान फलन है। बूलियन बीजगणित का एक समरूपता एक समरूपता है यदि और केवल यदि यह आक्षेप है।

बूलियन रिंग

Main article: Boolean ring

प्रत्येक बूलियन बीजगणित (A, ∧, ∨) a + b को परिभाषित करके एक वलय (बीजगणित) (A, +, ·) को जन्म देता है:= (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b ) ∧ ¬(a ∧ b) (इस संक्रिया को समुच्चयों के मामले में सममित अंतर कहा जाता है और सत्य तालिका # तर्क के मामले में अनन्य संयोजन) और a · b := a ∧ b। इस अंगूठी का शून्य तत्व बूलियन बीजगणित के 0 के साथ मेल खाता है; रिंग का गुणात्मक पहचान तत्व बूलियन बीजगणित का 1 है। इस वलय में यह गुण है कि a · a = a for all a in A; इस गुण वाले छल्ले को बूलियन रिंग कहा जाता है।

इसके विपरीत, यदि एक बूलियन वलय A दिया गया है, तो हम x ∨ y := x + y + (x · y) और x ∧ y:= x · y को परिभाषित करके इसे एक बूलियन बीजगणित में बदल सकते हैं। चूंकि ये दो निर्माण एक दूसरे के व्युत्क्रम हैं, इसलिए हम कह सकते हैं कि प्रत्येक बूलियन वलय एक बूलियन बीजगणित से उत्पन्न होता है, और इसके विपरीत। इसके अलावा, एक नक्शा f : A → B बूलियन बीजगणित का एक समरूपता है यदि और केवल अगर यह बूलियन छल्ले का एक समरूपता है। बूलियन रिंग्स और बूलियन बीजगणित का श्रेणी सिद्धांत समतुल्य है। हिसियांग (1985) ने शब्द समस्या (गणित) के लिए सार पुनर्लेखन प्रणाली | नियम-आधारित एल्गोरिथ्म दिया कि क्या दो मनमाने भाव प्रत्येक बूलियन रिंग में समान मान को दर्शाते हैं। अधिक आम तौर पर, बॉडेट, जीन-पियरे जौनौड, और श्मिट-शाउस (1989) ने एकीकरण (कंप्यूटर विज्ञान) के लिए एक एल्गोरिद्म दिया #विशेष पृष्ठभूमि ज्ञान स्वैच्छिक बूलियन-रिंग अभिव्यक्तियों के बीच ई सेट करता है। बूलियन रिंग और बूलियन बीजगणित की समानता को नियोजित करते हुए, दोनों एल्गोरिदम में स्वचालित प्रमेय साबित करने में अनुप्रयोग हैं।

आदर्श और फ़िल्टर

Main articles: Ideal (order theory) and Filter (mathematics)

बूलियन बीजगणित ए का आदर्श एक उपसमुच्चय है जैसे कि I में सभी x, y के लिए हमारे पास I में x ∨ y है और A में सभी के लिए हमारे पास I में एक ∧ x है। आदर्श की यह धारणा इस धारणा के साथ मेल खाती है बूलियन वलय A में वलय आदर्श। A का आदर्श I अभाज्य कहलाता है यदि I ≠ A और यदि I में a ∧ b हमेशा I में a या b I में निहित होता है। इसके अलावा, प्रत्येक a ∈ A के लिए हमारे पास वह a ∧ - a = 0 ∈ I और फिर a ∈ I या -a ∈ I प्रत्येक a ∈ A के लिए, यदि I अभाज्य है। A का एक आदर्श I अधिकतम कहा जाता है यदि I ≠ A और यदि एकमात्र आदर्श ठीक से I को समाहित करता है तो A ही है। एक आदर्श I के लिए, यदि a ∉ I और -a ∉ I, तो I ∪ {a} या I ∪ {-a} अन्य आदर्श J में उचित रूप से समाहित है। इसलिए, कि एक I अधिकतम नहीं है और इसलिए अभाज्य की धारणा बूलियन बीजगणित में आदर्श और अधिकतम आदर्श समान हैं। इसके अलावा, ये धारणाएं बूलियन रिंग ए में प्रमुख आदर्श और अधिकतम आदर्श के रिंग थ्योरिटिक के साथ मेल खाती हैं।

एक आदर्श का दोहरा एक फिल्टर है। बूलियन बीजगणित A का एक फ़िल्टर एक उपसमुच्चय p है जैसे कि p में सभी x, y के लिए हमारे पास p में x ∧ y है और A में सभी a के लिए हमारे पास p में एक ∨ x है। बूलियन बीजगणित में एक अधिकतम (या प्रधान) आदर्श का दोहरा अल्ट्राफिल्टर है। अल्ट्राफिल्टर को वैकल्पिक रूप से ए से दो-तत्व बूलियन बीजगणित के 2-मूल्यवान आकारिकी के रूप में वर्णित किया जा सकता है। बूलियन बीजगणित में प्रत्येक फ़िल्टर को एक अल्ट्राफ़िल्टर तक बढ़ाया जा सकता है, इसे बूलियन प्रधान आदर्श प्रमेय # अल्ट्राफ़िल्टर लेम्मा कहा जाता है और ज़र्मेलो-फ्रेंकेल सेट सिद्धांत में सिद्ध नहीं किया जा सकता है, यदि ज़र्मेलो-फ्रेंकेल सेट सिद्धांत संगत है। जेडएफ के भीतर, यह पसंद के स्वयंसिद्ध से सख्ती से कमजोर है। अल्ट्राफिल्टर प्रमेय के कई समतुल्य योग हैं: प्रत्येक बूलियन बीजगणित में एक अल्ट्राफिल्टर होता है, बूलियन बीजगणित में प्रत्येक आदर्श को एक प्रमुख आदर्श तक बढ़ाया जा सकता है, आदि।

प्रतिनिधित्व

यह दिखाया जा सकता है कि प्रत्येक परिमित बूलियन बीजगणित एक परिमित सेट के सभी उपसमुच्चयों के बूलियन बीजगणित के लिए समरूप है। इसलिए, प्रत्येक परिमित बूलियन बीजगणित के तत्वों की संख्या दो की शक्ति है।

मार्शल एच. स्टोन | बूलियन बीजगणित के लिए स्टोन का प्रसिद्ध प्रतिनिधित्व प्रमेय कहता है कि प्रत्येक बूलियन बीजगणित A कुछ (कॉम्पैक्ट जगह पूरी तरह से डिस्कनेक्ट हॉसडॉर्फ स्पेस) टोपोलॉजिकल स्पेस में सभी क्लोपेन सेट सेटों के बूलियन बीजगणित के लिए आइसोमॉर्फिक है।

स्वयंसिद्ध

Proven properties
UId1 If x ∨ o = x for all x, then o = 0 Proof: If x ∨ o = x, then 0 = 0 ∨ o by assumption = o ∨ 0 by Cmm1 = o by Idn1	यूआईडी2[दोहरी]   अगर x ∧ i = x सभी x के लिए, तो i = 1
Idm1 x ∨ x = x Proof: x ∨ x = (x ∨ x) ∧ 1 by Idn2 = (x ∨ x) ∧ (x ∨ ¬x) by Cpl1 = x ∨ (x ∧ ¬x) by Dst1 = x ∨ 0 by Cpl2 = x by Idn1	आईडीएम2[दोहरी]   x ∧ x = x
Bnd1 x ∨ 1 = 1 Proof: x ∨ 1 = (x ∨ 1) ∧ 1 by Idn2 = 1 ∧ (x ∨ 1) by Cmm2 = (x ∨ ¬x) ∧ (x ∨ 1) by Cpl1 = x ∨ (¬x ∧ 1) by Dst1 = x ∨ ¬x by Idn2 = 1 by Cpl1	Bnd2[दोहरी]  x ∧ 0 = 0
Abs1 x ∨ (x ∧ y) = x Proof: x ∨ (x ∧ y) = (x ∧ 1) ∨ (x ∧ y) by Idn2 = x ∧ (1 ∨ y) by Dst2 = x ∧ (y ∨ 1) by Cmm1 = x ∧ 1 by Bnd1 = x by Idn2	पेट2[दोहरी]  x ∧ (x ∨ y) = x
UNg If x ∨ xn = 1 and x ∧ xn = 0, then xn = ¬x Proof: If x ∨ xn = 1 and x ∧ xn = 0, then xn = xn ∧ 1 by Idn2 = xn ∧ (x ∨ ¬x) by Cpl1 = (xn ∧ x) ∨ (xn ∧ ¬x) by Dst2 = (x ∧ xn) ∨ (¬x ∧ xn) by Cmm2 = 0 ∨ (¬x ∧ xn) by assumption = (x ∧ ¬x) ∨ (¬x ∧ xn) by Cpl2 = (¬x ∧ x) ∨ (¬x ∧ xn) by Cmm2 = ¬x ∧ (x ∨ xn) by Dst2 = ¬x ∧ 1 by assumption = ¬x by Idn2
DNg ¬¬x = x Proof: ¬x ∨ x = x ∨ ¬x = 1 by Cmm1, Cpl1 and ¬x ∧ x = x ∧ ¬x = 0 by Cmm2, Cpl2 hence x = ¬¬x by UNg
A1 x ∨ (¬x ∨ y) = 1 Proof: x ∨ (¬x ∨ y) = (x ∨ (¬x ∨ y)) ∧ 1 by Idn2 = 1 ∧ (x ∨ (¬x ∨ y)) by Cmm2 = (x ∨ ¬x) ∧ (x ∨ (¬x ∨ y)) by Cpl1 = x ∨ (¬x ∧ (¬x ∨ y)) by Dst1 = x ∨ ¬x by Abs2 = 1 by Cpl1	ए2[दोहरी]   x ∧ (¬x ∧ y) = 0
B1 (x ∨ y) ∨ (¬x ∧ ¬y) = 1 Proof: (x ∨ y) ∨ (¬x ∧ ¬y) = ((x ∨ y) ∨ ¬x) ∧ ((x ∨ y) ∨ ¬y) by Dst1 = (¬x ∨ (x ∨ y)) ∧ (¬y ∨ (y ∨ x)) by Cmm1 = (¬x ∨ (¬¬x ∨ y)) ∧ (¬y ∨ (¬¬y ∨ x)) by DNg = 1 ∧ 1 by A1 = 1 by Idn2	बी2[दोहरी] (x ∧ y) ∧ (¬x ∨ ¬y) = 0
C1 (x ∨ y) ∧ (¬x ∧ ¬y) = 0 Proof: (x ∨ y) ∧ (¬x ∧ ¬y) = (¬x ∧ ¬y) ∧ (x ∨ y) by Cmm2 = ((¬x ∧ ¬y) ∧ x) ∨ ((¬x ∧ ¬y) ∧ y) by Dst2 = (x ∧ (¬x ∧ ¬y)) ∨ (y ∧ (¬y ∧ ¬x)) by Cmm2 = 0 ∨ 0 by A2 = 0 by Idn1	सी2[दोहरी] (x ∧ y) ∨ (¬x ∨ ¬y) = 1
DMg1 ¬(x ∨ y) = ¬x ∧ ¬y Proof: by B1, C1, and UNg	डीएमजी2[दोहरी] ¬(x ∧ y) = ¬x ∨ ¬y
D1 (x∨(y∨z)) ∨ ¬x = 1 Proof: (x ∨ (y ∨ z)) ∨ ¬x = ¬x ∨ (x ∨ (y ∨ z)) by Cmm1 = ¬x ∨ (¬¬x ∨ (y ∨ z)) by DNg = 1 by A1	डी2[दोहरी]   (x∧(y∧z)) ∧ ¬x = 0
E1 y ∧ (x∨(y∨z)) = y Proof: y ∧ (x ∨ (y ∨ z)) = (y ∧ x) ∨ (y ∧ (y ∨ z)) by Dst2 = (y ∧ x) ∨ y by Abs2 = y ∨ (y ∧ x) by Cmm1 = y by Abs1	और2[दोहरी] y ∨ (x∧(y∧z) = y
F1 (x∨(y∨z)) ∨ ¬y = 1 Proof: (x ∨ (y ∨ z)) ∨ ¬y = ¬y ∨ (x ∨ (y ∨ z)) by Cmm1 = (¬y ∨ (x ∨ (y ∨ z))) ∧ 1 by Idn2 = 1 ∧ (¬y ∨ (x ∨ (y ∨ z))) by Cmm2 = (y ∨ ¬y) ∧ (¬y ∨ (x ∨ (y ∨ z))) by Cpl1 = (¬y ∨ y) ∧ (¬y ∨ (x ∨ (y ∨ z))) by Cmm1 = ¬y ∨ (y ∧ (x ∨ (y ∨ z))) by Dst1 = ¬y ∨ y by E1 = y ∨ ¬y by Cmm1 = 1 by Cpl1	एफ2[दोहरी]   (x∧(y∧z)) ∧ ¬y = 0
G1 (x∨(y∨z)) ∨ ¬z = 1 Proof: (x ∨ (y ∨ z)) ∨ ¬z = (x ∨ (z ∨ y)) ∨ ¬z by Cmm1 = 1 by F1	जी2[दोहरी]   (x∧(y∧z)) ∧ ¬z = 0
H1 ¬((x∨y)∨z) ∧ x = 0 Proof: ¬((x ∨ y) ∨ z) ∧ x = (¬(x ∨ y) ∧ ¬z) ∧ x by DMg1 = ((¬x ∧ ¬y) ∧ ¬z) ∧ x by DMg1 = x ∧ ((¬x ∧ ¬y) ∧ ¬z) by Cmm2 = (x ∧ ((¬x ∧ ¬y) ∧ ¬z)) ∨ 0 by Idn1 = 0 ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z)) by Cmm1 = (x ∧ ¬x) ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z)) by Cpl2 = x ∧ (¬x ∨ ((¬x ∧ ¬y) ∧ ¬z)) by Dst2 = x ∧ (¬x ∨ (¬z ∧ (¬x ∧ ¬y))) by Cmm2 = x ∧ ¬x by E2 = 0 by Cpl2	एच2[दोहरी]   ¬((x∧y)∧z) ∨ x = 1
I1 ¬((x∨y)∨z) ∧ y = 0 Proof: ¬((x ∨ y) ∨ z) ∧ y = ¬((y ∨ x) ∨ z) ∧ y by Cmm1 = 0 by H1	मैं2[दोहरी]   ¬((x∧y)∧z) ∨ y = 1
J1 ¬((x∨y)∨z) ∧ z = 0 Proof: ¬((x ∨ y) ∨ z) ∧ z = (¬(x ∨ y) ∧ ¬z) ∧ z by DMg1 = z ∧ (¬(x ∨ y) ∧ ¬z) by Cmm2 = z ∧ ( ¬z ∧ ¬(x ∨ y)) by Cmm2 = 0 by A2	जे2[दोहरी] ¬((x∧y)∧z) ∨ z = 1
K1 (x ∨ (y ∨ z)) ∨ ¬((x ∨ y) ∨ z) = 1 Proof: (x∨(y∨z)) ∨ ¬((x ∨ y) ∨ z) = (x∨(y∨z)) ∨ (¬(x ∨ y) ∧ ¬z) by DMg1 = (x∨(y∨z)) ∨ ((¬x ∧ ¬y) ∧ ¬z) by DMg1 = ((x∨(y∨z)) ∨ (¬x ∧ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z) by Dst1 = (((x∨(y∨z)) ∨ ¬x) ∧ ((x∨(y∨z)) ∨ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z) by Dst1 = (1 ∧ 1) ∧ 1 by D1,F1,G1 = 1 by Idn2	क2[दोहरी]   (x ∧ (y ∧ z)) ∧ ¬((x ∧ y) ∧ z) = 0
L1 (x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) = 0 Proof: (x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) = ¬((x∨y)∨z) ∧ (x ∨ (y ∨ z)) by Cmm2 = (¬((x∨y)∨z) ∧ x) ∨ (¬((x∨y)∨z) ∧ (y ∨ z)) by Dst2 = (¬((x∨y)∨z) ∧ x) ∨ ((¬((x∨y)∨z) ∧ y) ∨ (¬((x∨y)∨z) ∧ z)) by Dst2 = 0 ∨ (0 ∨ 0) by H1,I1,J1 = 0 by Idn1	एल2[दोहरी]   (x ∧ (y ∧ z)) ∨ ¬((x ∧ y) ∧ z) = 1
Ass1 x ∨ (y ∨ z) = (x ∨ y) ∨ z Proof: by K1, L1, UNg, DNg	नितंब2[दोहरी]   x ∧ (y ∧ z) = (x ∧ y) ∧ z
Abbreviations UId Unique Identity Idm Idempotence Bnd Boundaries Abs Absorption law UNg Unique Negation DNg Double negation DMg De Morgan's Law Ass Associativity

| अलाइन = राइट क्लास = विकिटेबल कोलैप्सिबल कोलैप्सिबल कोलैप्सिबल स्टाइल = टेक्स्ट-अलाइन: लेफ्ट ! कोलस्पैन = 4 | हंटिंगटन 1904 बूलियन बीजगणित स्वयंसिद्ध |- वेलिग्न = शीर्ष | आईडीएन₁|| x ∨ 0 = x | आईडीएन₂|| एक्स ∧ 1 = एक्स |- वेलिग्न = शीर्ष | सीएमएम₁|| x ∨ y = y ∨ x | सीएमएम₂|| x ∧ y = y ∧ x |- वेलिग्न = शीर्ष | डीएसटी₁|| x ∨ (y∧z) = (x∨y) ∧ (x∨z) | डीएसटी₂|| x ∧ (y∨z) = (x∧y) ∨ (x∧z) |- वेलिग्न = शीर्ष | कारपोरल₁|| x ∨ ¬x = 1 | कारपोरल₂|| x ∧ ¬x = 0 |- | कोलस्पैन = 4 |

Abbreviations
Idn	Identity
Cmm	Commutativity
Dst	Distributivity
Cpl	Complements

|}

1898 में अंग्रेजी दार्शनिक और गणितज्ञ अल्फ्रेड नॉर्थ व्हाइटहेड द्वारा सामान्य रूप से बूलियन लैटिस/अल्जेब्रा का पहला स्वयंसिद्धीकरण दिया गया था। इसमें #परिभाषा और अतिरिक्त रूप से x∨1=1 और x∧0=0 शामिल है। 1904 में, अमेरिकी गणितज्ञ एडवर्ड वी. हंटिंगटन (1874-1952) ने संभवतः ∧, ∨, ¬ पर आधारित सबसे पारिश्रमिक स्वयंसिद्धीकरण दिया, यहां तक ​​कि साहचर्य के नियमों को भी साबित किया (बॉक्स देखें)। उन्होंने यह भी सिद्ध किया कि ये अभिगृहीत एक दूसरे की स्वतंत्रता (गणितीय तर्क) हैं। 1933 में, हंटिंगटन ने बूलियन बीजगणित के लिए निम्नलिखित सुरुचिपूर्ण स्वसिद्धीकरण की स्थापना की। इसे 'पूरक' के रूप में पढ़ने के लिए केवल एक बाइनरी ऑपरेशन + और एक एकात्मक कार्यात्मक प्रतीक n की आवश्यकता होती है, जो निम्नलिखित कानूनों को पूरा करता है:

1. क्रमविनिमेयता: x + y = y + x।
2. सहयोगीता: (x + y) + z = x + (y + z)।
3. हंटिंगटन समीकरण: एन (एन (एक्स) + वाई) + एन (एन (एक्स) + एन (वाई)) = एक्स।

हर्बर्ट रॉबिन्स ने तुरंत पूछा: यदि हंटिंगटन समीकरण को इसके दोहरे से बदल दिया जाए, तो बुद्धि के लिए:

4. रॉबिन्स समीकरण: n(n(x + y) + n(x + n(y))) = x,

क्या (1), (2), और (4) बूलियन बीजगणित के लिए आधार बनाते हैं? कॉलिंग (1), (2), और (4) एक रॉबिन्स बीजगणित, फिर प्रश्न बन जाता है: क्या प्रत्येक रॉबिन्स बीजगणित एक बूलियन बीजगणित है? यह प्रश्न (जिसे रॉबिन्स अनुमान के रूप में जाना जाता है) दशकों तक खुला रहा और अल्फ्रेड टार्स्की और उनके छात्रों का पसंदीदा प्रश्न बन गया। 1996 में, लैरी वोस, स्टीव विंकर, और बॉब वेरॉफ द्वारा किए गए पहले के काम पर निर्माण करते हुए, Argonne राष्ट्रीय प्रयोगशाला में विलियम मैकक्यून ने रॉबिन्स के प्रश्न का सकारात्मक उत्तर दिया: प्रत्येक रॉबिन्स बीजगणित एक बूलियन बीजगणित है। मैकक्यून के प्रमाण के लिए महत्वपूर्ण कंप्यूटर प्रोग्राम समतामूलक कहावत था जिसे उन्होंने डिजाइन किया था। मैकक्यून के प्रमाण के सरलीकरण के लिए, दहन (1998) देखें।

अभिगृहीतों की संख्या को कम करने के लिए आगे कार्य किया गया है; बूलियन बीजगणित के लिए न्यूनतम स्वयंसिद्ध देखें।

सामान्यीकरण

बूलियन बीजगणित के स्वयंसिद्धों से एक इकाई के अस्तित्व की आवश्यकता को हटाने से सामान्यीकृत बूलियन बीजगणित प्राप्त होता है। औपचारिक रूप से, एक वितरण जाली बी एक सामान्यीकृत बूलियन जाली है, अगर इसमें सबसे छोटा तत्व 0 है और बी में किसी भी तत्व ए और बी के लिए ऐसा है कि ए ≤ बी, एक तत्व एक्स मौजूद है जैसे कि ∧ x = 0 और एक ∨ x = ख। a ∖ b को अद्वितीय x के रूप में परिभाषित करना जैसे कि (a ∧ b) ∨ x = a और (a ∧ b) ∧ x = 0, हम कहते हैं कि संरचना (B,∧,∨,∖,0) एक सामान्यीकृत बूलियन है बीजगणित, जबकि (बी,∨,0) एक सामान्यीकृत बूलियन अर्द्ध लेटेक्स है। सामान्यीकृत बूलियन लैटिस बूलियन लैटिस के बिल्कुल आदर्श (आदेश सिद्धांत) हैं।

एक संरचना जो बूलियन बीजगणित के लिए दो वितरण स्वयंसिद्धों को छोड़कर सभी स्वयंसिद्धों को संतुष्ट करती है, एक ऑर्थोकम्प्लीमेंटेड जाली कहलाती है। अलग-अलग हिल्बर्ट रिक्त स्थान के लिए बंद उप-स्थानों की जाली के रूप में orthocomplemented जाली क्वांटम तर्क में स्वाभाविक रूप से उत्पन्न होते हैं।

यह भी देखें

• List of Boolean algebra topics
• Boolean domain
• Boolean function
• Boolean logic
• Boolean ring
• Boolean-valued function
• Canonical form (Boolean algebra)
• Complete Boolean algebra
• De Morgan's laws
• Finitary boolean function
• Forcing (mathematics)
• Free Boolean algebra
• Heyting algebra
• Hypercube graph
• Karnaugh map
• Laws of Form
• Logic gate
• Logical graph
• Logical matrix
• Propositional logic
• Quine–McCluskey algorithm
• Two-element Boolean algebra
• Venn diagram
• Conditional event algebra

संदर्भ

उद्धृत कार्य

• Davey, B.A.; Priestley, H.A. (1990). जाली और व्यवस्था का परिचय. Cambridge Mathematical Textbooks. Cambridge University Press.
• Cohn, Paul M. (2003), Basic Algebra: Groups, Rings, and Fields, Springer, pp. 51, 70–81, ISBN 9781852335878
• Givant, Steven; Halmos, Paul (2009), Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer, ISBN 978-0-387-40293-2.
• Goodstein, R. L. (2012), "Chapter 2: The self-dual system of axioms", Boolean Algebra, Courier Dover Publications, pp. 21ff, ISBN 9780486154978
• Hsiang, Jieh (1985). "टर्म रिराइटिंग सिस्टम का उपयोग करके खंडन प्रमेय साबित करना". Artificial Intelligence. 25 (3): 255–300. doi:10.1016/0004-3702(85)90074-8.
• Huntington, Edward V. (1904). "तर्क के बीजगणित के लिए स्वतंत्र अभिधारणाओं के समुच्चय". Transactions of the American Mathematical Society. 5 (3): 288–309. doi:10.1090/s0002-9947-1904-1500675-4. JSTOR 1986459.
• Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axioms for lattices and boolean algebras, World Scientific, ISBN 978-981-283-454-6.
• Stone, Marshall H. (1936). "बूलियन बीजगणित के लिए प्रतिनिधित्व का सिद्धांत". Transactions of the American Mathematical Society. 40: 37–111. doi:10.1090/s0002-9947-1936-1501865-8.
• Whitehead, A.N. (1898). यूनिवर्सल बीजगणित पर एक ग्रंथ. Cambridge University Press. ISBN 978-1-4297-0032-0.

सामान्य संदर्भ

• Brown, Stephen; Vranesic, Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd ed.), McGraw–Hill, ISBN 978-0-07-249938-4. खंड 2.5 देखें।
• Boudet, A.; Jouannaud, J.P.; Schmidt-Schauß, M. (1989). "बूलियन रिंग्स और एबेलियन ग्रुप्स में एकीकरण". Journal of Symbolic Computation. 8 (5): 449–477. doi:10.1016/s0747-7171(89)80054-9.
• Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3. अध्याय 2 देखें।
• Dahn, B. I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem", Journal of Algebra, 208 (2): 526–532, doi:10.1006/jabr.1998.7467.

• Halmos, Paul (1963), Lectures on Boolean Algebras, Van Nostrand, ISBN 978-0-387-90094-0.
• Halmos, Paul; Givant, Steven (1998), Logic as Algebra, Dolciani Mathematical Expositions, vol. 21, Mathematical Association of America, ISBN 978-0-88385-327-6.
• Huntington, E. V. (1933a), "New sets of independent postulates for the algebra of logic" (PDF), Transactions of the American Mathematical Society, American Mathematical Society, 35 (1): 274–304, doi:10.2307/1989325, JSTOR 1989325.
• Huntington, E. V. (1933b), "Boolean algebra: A correction", Transactions of the American Mathematical Society, 35 (2): 557–558, doi:10.2307/1989783, JSTOR 1989783
• Mendelson, Elliott (1970), Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw–Hill, ISBN 978-0-07-041460-0
• Monk, J. Donald; Bonnet, R., eds. (1989), Handbook of Boolean Algebras, North-Holland, ISBN 978-0-444-87291-3. 3 खंडों में। (खंड 1:ISBN 978-0-444-70261-6, खंड 2:ISBN 978-0-444-87152-7, खंड 3:ISBN 978-0-444-87153-4)
• Sikorski, Roman (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag.
• Stoll, R. R. (1963), Set Theory and Logic, W. H. Freeman, ISBN 978-0-486-63829-4. डोवर प्रकाशन द्वारा पुनर्मुद्रित, 1979।

बाहरी संबंध

• "Boolean algebra", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra," by J. Donald Monk.
• McCune W., 1997. Robbins Algebras Are Boolean JAR 19(3), 263—276
• "Boolean Algebra" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
• Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
• Weisstein, Eric W. "Boolean Algebra". MathWorld.