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

For विषय का परिचय, see बूलियन बीजगणित. For एक वैकल्पिक प्रस्तुति, see बूलियन बीजगणित विहित रूप से परिभाषित.

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

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

उपसमुच्चयों का बूलियन जालक

इतिहास

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

परिभाषा

बूलियन बीजगणित एक समुच्चय A वाला छह-ट्यूपल है, जो दो द्विआधारी संक्रियाओं ∧ (जिसे "मीट" या "और") कहा जाता है), ∨ ("ज्वाइन" या "या" कहा जाता है), एक एकाधारी संक्रिया ¬ (जिसे " पूरक" या "नहीं" कहा जाता है) और A के दो तत्वों 0 और 1 (जिन्हें "निम्न" और "शीर्ष", या "न्यूनतम" और "महत्तम" तत्व कहा जाता है, जिन्हें क्रमशः ⊥ और ⊤ प्रतीकों द्वारा भी निरूपित किया जाता है) से इस प्रकार सुसज्जित है कि A के सभी तत्वों a, b और c के लिए, निम्न अभिगृहीत सत्य हैं:

a ∨ (b ∨ c) = (a ∨ b) ∨ c	a ∧ (b ∧ c) = (a ∧ b) ∧ c	साहचर्यता
a ∨ b = b ∨ a	a ∧ b = b ∧ a	क्रमविनिमेयता
a ∨ (a ∧ b) = a	a ∧ (a ∨ b) = a	अवशोषण
a ∨ 0 = a	a ∧ 1 = a	तत्समक
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)	a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)	वितरण
a ∨ ¬a = 1	a ∧ ¬a = 0	पूरक

ध्यान दें, हालाँकि, अवशोषण नियम और यहाँ तक ​​​​कि साहचर्यता नियम को सिद्धांतों के समुच्चय से बाहर रखा जा सकता है क्योंकि इन्हें अन्य सिद्धांतों से प्राप्त किया जा सकता है (सिद्ध गुण देखें)।

केवल एक तत्व वाली बूलियन बीजगणित को तुच्छ बूलियन बीजगणित या विकृत बूलियन बीजगणित कहा जाता है। (पुराने कार्यों में, कुछ लेखकों को इस स्थिति को बाहर करने के लिए 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)
  • (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

• $S$ के सभी उपसमुच्चयों का समुच्चय $A$ (परिमित या सहपरिमित), एक बूलियन बीजगणित और समुच्चयों का बीजगणित है जिसे परिमित-सहपरिमित बीजगणित कहा जाता है। यदि $S$ अपरिमित है तो $S$ के सभी सहपरिमित उपसमुच्चयों का समुच्चय, (जिसे फ्रेचेट फिल्टर कहा जाता है), $A$ पर एक मुक्त अल्ट्राफिल्टर है। हालाँकि, फ्रेचेट फिल्टर $S$ के घात समुच्चय पर एक अल्ट्राफिल्टर नहीं है ।
• κ वाक्य प्रतीकों वाले प्रतिज्ञप्ति कलन के साथ प्रारंभ करते हुए, लिंडेनबाउम बीजगणित (अर्थात्, प्रतिज्ञप्ति कलन मॉड्यूलो तार्किक तुल्यता में वाक्यों का समुच्चय) का निर्माण करें। यह निर्माण एक बूलियन बीजगणित उत्पन्न करता है। यह वास्तव में κ उत्पादकों पर मुक्त बूलियन बीजगणित है। तब प्रतिज्ञप्ति कलन में एक सत्य आवंटन, इस बीजगणित से दो-तत्व बूलियन बीजगणित में एक बूलियन बीजगणित समरूपता है।
• न्यूनतम तत्व वाले किसी भी रैखिक रूप से क्रमित समुच्चय L के लिए, अंतराल बीजगणित L के उपसमुच्चयों की लघुतम बीजगणित है जिसमें ऐसे सभी अर्द्ध-विवृत अंतराल [a, b) होते हैं कि a, L में है और b या तो L में या ∞ बराबर है। अंतराल बीजगणित लिंडेनबाउम-टार्स्की बीजगणित के अध्ययन में उपयोगी होते हैं; प्रत्येक गणनीय बूलियन बीजगणित एक अंतराल बीजगणित के लिए समाकृतिक है।
• किसी प्राकृतिक संख्या n के लिए, यह परिभाषित करने वाले n के सभी धनात्मक विभाजकों का समुच्चय एक वितरण जालक का निर्माण करता है, कि $a\leq b$, यदि a, b को विभाजित करता है। यह जालक एक बूलियन बीजगणित है यदि और केवल यदि n वर्ग-मुक्त है। इस बूलियन बीजगणित के निम्न और शीर्ष तत्व क्रमशः प्राकृतिक संख्याएँ 1 और n है। a का पूरक n/a द्वारा दिया जाता है। a और b के मीट और ज्वाइन क्रमशः a और b के महत्तम समापवर्तक (जीसीडी) और लघुतम समापवर्त्य (एलसीएम) द्वारा दिए जाते हैं। वलय योग a+b, ल०स०(a,b)/म०स०(a,b) द्वारा दिया जाता है। चित्र n = 30 के लिए एक उदाहरण दर्शाता है। एक प्रति-उदाहरण के रूप में, गैर-वर्ग-मुक्त n = 60 पर विचार करते हुए, 30 का म०स० और इसका पूरक 2, 2 होता है, जबकि यह निम्न तत्व 1 होना चाहिए।

30 के भाजकों के बूलियन बीजगणितों का हेस आरेख।

• बूलियन बीजगणित के अन्य उदाहरण सांस्थितीय अंतरिक्ष से उत्पन्न होते हैं: यदि 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),

f(0) = 0,

f(1) = 1।

तब इस प्रकार, A के सभी a के लिए f(¬a) = ¬f(a)। रूपवाद की इस धारणा के साथ सभी बूलियन बीजगणितों का वर्ग (समुच्चय सिद्धांत), जालकों की श्रेणी की एक पूर्ण उपश्रेणी बनाता है।

दो बूलियन बीजगणितों A और B के बीच एक समाकृतिकता, एक व्युत्क्रम समरूपता, g: B → A के साथ एक ऐसी समरूपता f: A → B है कि संयोजन g ∘ f: A → A, A पर तत्समक फलन है, और संयोजन f ∘ g: B → B, B पर तत्समक फलन है। बूलियन बीजगणितों की एक समरूपता, एक समाकृतिकता होती है यदि और केवल यदि यह एकैकी-आच्छादक है।

बूलियन वलय

Main article: बूलियन वलय

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

इसके विपरीत, यदि एक बूलियन वलय A दिया गया है, तो हम x ∨ y := x + y + (x · y) और x ∧ y:= x · y को परिभाषित करके इसे एक बूलियन बीजगणित में बदल सकते हैं। चूंकि ये दो निर्माण एक दूसरे के व्युत्क्रम हैं, इसलिए हम कह सकते हैं कि प्रत्येक बूलियन वलय एक बूलियन बीजगणित से उत्पन्न होता है, और इसके विपरीत। इसके अलावा, एक नक्शा f : A → B बूलियन बीजगणित का एक समरूपता है यदि और केवल यदि यह बूलियन छल्ले का एक समरूपता है। बूलियन छल्ले और बूलियन बीजगणित की श्रेणियां समतुल्य हैं।

ह्सियांग (1985) ने यह जांचने के लिए एक नियम-आधारित एल्गोरिथम दिया कि क्या दो मनमाने भाव प्रत्येक बूलियन वलय में समान मान को दर्शाते हैं। अधिक सामान्यतः, बॉडेट, जौनौड, और श्मिट-शाउस (1989) ने मनमाना बूलियन-वलय अभिव्यक्तियों के बीच समीकरणों को हल करने के लिए एक एल्गोरिथ्म दिया। बूलियन वलय और बूलियन बीजगणित की समानता को नियोजित करते हुए, दोनों एल्गोरिदम में स्वचालित प्रमेय साबित करने में अनुप्रयोग हैं।

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

Main articles: आदर्श (आदेश सिद्धांत) and फ़िल्टर (गणित)

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

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

निरूपण

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

बूलियन बीजगणितों के लिए स्टोन के प्रसिद्ध निरूपण प्रमेय में कहा गया है कि प्रत्येक बूलियन बीजगणित 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

सामान्य रूप में बूलियन जालक/बीजगणित का पहला अभिगृहीतीकरण वर्ष 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. हंटिंगटन समीकरण: n(n(x) + y) + n(n(x) + n(y)) = x।

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

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

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

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

सामान्यीकरण

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

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

यह भी देखें

• बूलियन बीजगणित विषयों की सूची
• बूलियन प्रांत
• बूलियन फलन
• बूलियन तर्क
• बूलियन वलय
• बूलियन-मान फलन
• प्रामाणिक रूप (बूलियन बीजगणित)
• पूर्ण बूलियन बीजगणित
• डी मॉर्गन के नियम
• अंतिम बूलियन फलन
• प्रेरण (गणित)
• मुक्त बूलियन बीजगणित
• हेटिंग बीजगणित
• अतिविम आलेख
• कर्नाघ प्रतिचित्र
• लॉज़ ऑफ़ फॉर्म
• तर्क द्वार
• तार्किक आलेख
• तार्किक आव्यूह
• प्रस्तावित तर्क
• क्विन-मैक्लुस्की एल्गोरिथम
• दो-तत्व बूलियन बीजगणित
• वेन आरेख
• सशर्त घटना बीजगणित

संदर्भ

उद्धृत कार्य

• 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.