बूलियन बीजगणित के लिए न्यूनतम स्वयंसिद्ध

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

$((a\mid b)\mid c)\mid (a\mid ((a\mid c)\mid a))=c$

जहां ऊर्ध्वाधर पट्टी NAND तार्किक ऑपरेशन (जिसे शेफ़र लाइन के रूप में भी जाना जाता है) का प्रतिनिधित्व करती है।

यह स्टीफन वोल्फ्राम द्वारा पहचानी गई इस संपत्ति के लिए 25 उम्मीदवार सिद्धांतों में से एक है, जिसमें 15 तत्वों (दर्पण छवियों को छोड़कर) की लंबाई से कम या बराबर की शेफ़र पहचान की गणना की गई है, जिसमें चार या उससे कम चर के साथ कोई गैर-अनुवांशिक मॉडल नहीं है, और पहली बार समकक्ष साबित हुआ था विलियम मैकक्यून, ब्रैंडन फिटेलसन, और लैरी वोस। वोल्फ्राम से जुड़ी साइट मैथवर्ल्ड ने इस स्वयंसिद्ध को वोल्फ्राम स्वयंसिद्ध नाम दिया है। मैकक्यून एट अल. विच्छेदन और निषेध के आधार पर बूलियन बीजगणित के लिए एक लंबा एकल स्वयंसिद्ध भी पाया गया।

1933 में, एडवर्ड वर्मिली हंटिंगटन ने स्वयंसिद्ध की पहचान की

${\neg ({\neg x}\lor {y})}\lor {\neg ({\neg x}\lor {\neg y})}=x$

बूलियन बीजगणित के समतुल्य होने के नाते, जब इसे तार्किक OR ऑपरेशन की क्रमविनिमेयता के साथ जोड़ा जाता है, $x\lor y=y\lor x$, और साहचर्य की धारणा, $(x\lor y)\lor z=x\lor (y\lor z)$. हर्बर्ट रॉबिंस ने अनुमान लगाया कि हंटिंगटन के स्वयंसिद्ध को प्रतिस्थापित किया जा सकता है

$\neg (\neg (x\lor y)\lor \neg (x\lor {\neg y}))=x,$

जिसके लिए तार्किक निषेध ऑपरेटर के एक कम उपयोग की आवश्यकता होती है $\neg$. न तो रॉबिंस और न ही हंटिंगटन इस अनुमान को सिद्ध कर सके; न ही अल्फ्रेड टार्स्की, जिन्होंने बाद में इसमें काफी रुचि ली, ऐसा कर सके। अंततः 1996 में स्वचालित प्रमेय सिद्ध करने वाले सॉफ़्टवेयर की सहायता से यह अनुमान सिद्ध हो गया। इस प्रमाण ने स्थापित किया कि रॉबिंस स्वयंसिद्ध, साहचर्यता और क्रमविनिमेयता के साथ मिलकर, बूलियन बीजगणित के लिए 3-आधार बनाते हैं। 2-आधार का अस्तित्व 1967 में कैरव आर्थर मेरेडिथ द्वारा स्थापित किया गया था:

$\neg ({\neg x}\lor y)\lor x=x,$

$\neg ({\neg x}\lor y)\lor (z\lor y)=y\lor (z\lor x).$

अगले वर्ष, मेरेडिथ को शेफ़र स्ट्रोक के संदर्भ में 2-आधार मिला:

$(x\mid x)\mid (y\mid x)=x,$

$x|(y\mid (x\mid z))=((z\mid y)\mid y)\mid x.$

1973 में, पद्मनाभन और क्वेकेनबश ने एक ऐसी विधि का प्रदर्शन किया, जो सिद्धांत रूप में, बूलियन बीजगणित के लिए 1-आधार प्रदान करेगी। इस विधि को सीधे तरीके से लागू करने से विशाल लंबाई के स्वयंसिद्ध परिणाम प्राप्त हुए,जिससे यह प्रश्न उठता है कि छोटे स्वयंसिद्ध कैसे पाए जा सकते हैं। इस खोज से ऊपर दिए गए शेफ़र स्ट्रोक के संदर्भ में 1-आधार, साथ ही 1-आधार प्राप्त हुआ

$\neg (\neg (\neg (x\lor y)\lor z)\lor \neg (x\lor \neg (\neg z\lor \neg (z\lor u))))=z,$

जो लॉजिकल OR और लॉजिकल NOT के संदर्भ में लिखा गया है।