Minimalne aksjomaty dla algebry Boole'a - Minimal axioms for Boolean algebra

W logice matematycznej , minimalne aksjomaty dla operacji Algebra to założenia będące odpowiednikiem aksjomatów logicznego Algebra (lub zdań rachunku ), wybranych być tak krótki, jak to możliwe. Na przykład, jeśli zdecydujemy się przyjąć przemienność za pewnik, aksjomat z sześcioma operacjami NAND i trzema zmiennymi jest równoważny algebrze Boole'a:

${\ Displaystyle ((a \ mid b) \ mid c) \ mid (a \ mid ((a \ mid c) \ mid a)) = c}$

gdzie pionowa kreska reprezentuje operację logiczną NAND (znaną również jako pociągnięcie Sheffera ).

Jest to jeden z 25 kandydujących aksjomatów tej własności zidentyfikowanych przez Stephena Wolframa , wyliczając tożsamości Sheffera o długości mniejszej lub równej 15 elementom (z wyłączeniem odbić lustrzanych), które nie mają nieprzemiennych modeli z czterema lub mniej zmiennymi, i po raz pierwszy udowodniono, że są one równoważne przez William McCune , Branden Fitelson i Larry Wos . MathWorld , strona powiązana z Wolframem, nazwała aksjomat „aksjomatem Wolframa”. McCune i in. znalazł również dłuższy pojedynczy aksjomat dla algebry Boole'a opartej na alternatywie i negacji.

W 1933 Edward Vermilye Huntington zidentyfikował aksjomat

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

jako odpowiednik algebry Boole'a, w połączeniu z przemiennością operacji OR , i założeniem asocjatywności, . Herbert Robbins przypuszczał, że aksjomat Huntingtona mógłby zostać zastąpiony przez: ${\displaystyle x\lory y=y\lorx}$${\ Displaystyle (x \ lor y) \ lor z = x \ lor (y \ lor z)}$

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

co wymaga o jeden mniej użycia operatora negacji logicznej . Ani Robbins, ani Huntington nie mogli udowodnić tego przypuszczenia; podobnie Alfred Tarski , który później zainteresował się nią bardzo. Przypuszczenie to zostało ostatecznie udowodnione w 1996 roku za pomocą oprogramowania do dowodzenia twierdzeń . Ten dowód ustalił, że aksjomat Robbinsa, wraz z asocjatywnością i przemiennością, tworzą 3-podstawę dla algebry Boole'a. Istnienie 2-podstawy zostało założone w 1967 roku przez Carew Arthur Meredith : ${\displaystyle \neg}$

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

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

W następnym roku Meredith znalazła 2 podstawy pod względem udaru Sheffera:

${\ Displaystyle (x \ mid x) \ mid (y \ mid x) = x,}$

${\ Displaystyle x | (r \ mid (x \ mid z)) = ((z \ mid r) \ mid r) \ mid x.}$

W 1973 Padmanabhan i Quackenbush zademonstrowali metodę, która w zasadzie dałaby podstawę 1 dla algebry Boole'a. Zastosowanie tej metody w prosty sposób zaowocowało „aksjomatami o ogromnej długości”, prowokując tym samym pytanie, jak można znaleźć krótsze aksjomaty. To wyszukiwanie dało podstawę 1 w kategoriach uderzenia Sheffera podanego powyżej, a także 1 podstawę

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

który jest napisany w terminach OR i NOT.

Bibliografia