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

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

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

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

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

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

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

बूलियन बीजगणित के समतुल्य होने के नाते, जब इसे तार्किक ओआर ऑपरेशन की क्रमविनिमेयता के साथ जोड़ा जाता है, $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,$

जो ओआर और एनओटी के संदर्भ में लिखा गया है।