Minimal axioms for Boolean algebra
ગાણિતિક તર્કશાસ્ત્રમાં, બુલિયન બીજગણિત માટે લઘુતમ સ્વયંસિદ્ધ ધારણાઓ એવી ધારણાઓ છે જે બુલિયન બીજગણિત (અથવા પ્રસ્તાવાત્મક કલન) ના સ્વયંસિદ્ધ સિદ્ધાંતોની સમકક્ષ હોય છે, જેને શક્ય તેટલી ટૂંકી પસંદ કરવામાં આવે છે. ઉદાહરણ તરીકે, છ એન. એ. એન. ડી. કામગીરીઓ અને ત્રણ ચલ સાથે સ્વયંસિદ્ધ બુલિયન બીજગણિતની સમકક્ષ છેઃ જ્યાં ઊભી પટ્ટી એન. એ. એન. ડી. તાર્કિક કામગીરીનું પ્રતિનિધિત્વ કરે છે (જેને શેફર સ્ટ્રોક તરીકે પણ ઓળખવામાં આવે છે). તે સ્ટીફન વોલ્ફ્રેમ દ્વારા ઓળખવામાં આવેલી આ મિલકત માટેના 25 ઉમેદવાર સ્વયંસિદ્ધ સિદ્ધાંતોમાંથી એક છે, જેમાં 15 ઘટકો (મિરર ઈમેજ સિવાય) ની લંબાઈ ઓછી અથવા તેની બરાબરની શેફર ઓળખની ગણતરી કરવામાં આવી છે, જેમાં ચાર કે તેથી ઓછા ચલ સાથે કોઈ બિનપરિવર્તનશીલ મોડેલ નથી, અને વિલિયમ મેકક્યુન, બ્રાન્ડેન ફિટલ્સન અને લેરી વોસ દ્વારા પ્રથમ વખત સમકક્ષ સાબિત થયું હતું. વોલ્ફ્રેમ સાથે સંકળાયેલી સાઇટ, મેથવર્લ્ડે સ્વયંસિદ્ધને "વોલ્ફ્રેમ સ્વયંસિદ્ધ" નામ આપ્યું છે. મેકક્યુન એટ અલ. વિચ્છેદન અને નિષેધ પર આધારિત બુલિયન બીજગણિત માટે એક લાંબો એકલ સિદ્ધાંત પણ મળ્યો. 1933માં, એડવર્ડ વર્મિલી હન્ટિંગ્ટને સ્વયંસિદ્ધતાને બુલિયન બીજગણિતની સમકક્ષ હોવાનું ઓળખાવ્યું હતું, જ્યારે તેને OR ઓપરેશનની પરિવર્તનીયતા અને સહયોગીતાની ધારણા સાથે જોડવામાં આવ્યું હતું. હર્બર્ટ રોબિન્સે અનુમાન લગાવ્યું હતું કે હંટીંગ્ટનના સ્વયંસિદ્ધ સિદ્ધાંતને બદલી શકાય છે, જેના માટે લોજિકલ નેગેશન ઓપરેટરનો એક ઓછો ઉપયોગ જરૂરી છે. ન તો રોબિન્સ અને ન તો હન્ટિંગ્ટન આ અનુમાનને સાબિત કરી શક્યા; ન તો આલ્ફ્રેડ ટાર્સ્કી, જેમણે પાછળથી તેમાં નોંધપાત્ર રસ લીધો હતો. આ અનુમાન આખરે 1996 માં પ્રમેય-સાબિત સોફ્ટવેરની મદદથી સાબિત થયું હતું. આ સાબિતીએ સ્થાપિત કર્યું કે રોબિન્સ સ્વયંસિદ્ધ, સહયોગીતા અને વિનિમયક્ષમતા સાથે મળીને બુલિયન બીજગણિત માટે 3-આધાર બનાવે છે. કેરેવ આર્થર મેરેડિથ દ્વારા 1967માં 2-બેસિસના અસ્તિત્વની સ્થાપના કરવામાં આવી હતીઃ તે પછીના વર્ષે, મેરેડિથને શેફર સ્ટ્રોકના સંદર્ભમાં 2-બેસિસ મળ્યા હતાઃ 1973માં, પદ્મનાભન અને ક્વેકેનબુશે એક પદ્ધતિ દર્શાવી હતી, જે સૈદ્ધાંતિક રીતે બુલિયન બીજગણિત માટે 1-બેસિસ આપશે. આ પદ્ધતિને સીધી રીતે લાગુ કરવાથી "પ્રચંડ લંબાઈના સ્વયંસિદ્ધ" મળ્યા, જેનાથી ટૂંકા સ્વયંસિદ્ધ કેટલા મળી શકે છે તે પ્રશ્ન પેદા થાય છે. આ શોધથી ઉપર આપેલા શેફર સ્ટ્રોકના સંદર્ભમાં 1-આધાર મળ્યો, તેમજ 1-આધાર જે OR અને NOT ના સંદર્ભમાં લખવામાં આવ્યો છે. સંદર્ભો બુલિયન બીજગણિત તર્કનો ઇતિહાસ NAND ગેટ પ્રપોઝિશનલ કલન