Minimale Axiome für Boolesche Algebra - Minimal axioms for Boolean algebra

In der mathematischen Logik sind minimale Axiome für die Boolesche Algebra Annahmen, die den Axiomen der Booleschen Algebra (oder der Aussagenkalküle ) äquivalent sind und so kurz wie möglich gewählt werden. Wenn man zum Beispiel die Kommutativität als selbstverständlich ansieht, entspricht ein Axiom mit sechs NAND- Operationen und drei Variablen der Booleschen Algebra:

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

wobei der vertikale Balken die logische NAND-Operation darstellt (auch als Sheffer-Strich bekannt ).

Es ist eines von 25 Kandidaten-Axiomen für diese Eigenschaft, die von Stephen Wolfram identifiziert wurden , indem die Sheffer-Identitäten mit einer Länge von weniger oder gleich 15 Elementen (ohne Spiegelbilder) aufgezählt wurden, die keine nichtkommutativen Modelle mit vier oder weniger Variablen haben, und wurde zuerst als gleichwertig nachgewiesen durch William McCune , Branden Fitelson und Larry Wos . MathWorld , eine mit Wolfram verbundene Site, hat das Axiom "Wolfram-Axiom" genannt. McCuneet al. fanden auch ein längeres einzelnes Axiom für die Boolesche Algebra basierend auf Disjunktion und Negation.

1933 identifizierte Edward Vermilye Huntington das Axiom

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

als äquivalent zur Booleschen Algebra, wenn sie mit der Kommutativität der ODER- Operation, , und der Annahme der Assoziativität, kombiniert wird . Herbert Robbins vermutete, dass Huntingtons Axiom ersetzt werden könnte durch ${\displaystyle x\lor y=y\lor x}$${\displaystyle (x\lor y)\lor z=x\lor (y\lor z)}$

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

was eine Verwendung des logischen Negationsoperators weniger erfordert . Weder Robbins noch Huntington konnten diese Vermutung beweisen; auch Alfred Tarski , der sich später sehr dafür interessierte, konnte es nicht. Die Vermutung wurde schließlich 1996 mit Hilfe einer theorembeweisenden Software bewiesen . Dieser Beweis stellte fest, dass das Robbins-Axiom zusammen mit Assoziativität und Kommutativität eine 3-Basis für die Boolesche Algebra bildet. Die Existenz einer 2-Basis wurde 1967 von Carew Arthur Meredith begründet : ${\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).}$

Im folgenden Jahr fand Meredith eine 2-Basis in Bezug auf den Sheffer-Schlaganfall:

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

${\displaystyle x|(y\mid (x\mid z))=((z\mid y)\mid y)\mid x.}$

1973 demonstrierten Padmanabhan und Quackenbush eine Methode, die im Prinzip eine 1-Basis für die Boolesche Algebra liefern würde. Die einfache Anwendung dieser Methode lieferte "Axiome von enormer Länge", was die Frage aufwarf, wie kürzere Axiome gefunden werden könnten. Diese Suche ergab die 1-Basis in Bezug auf den oben angegebenen Sheffer-Strich sowie die 1-Basis

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

die in Bezug auf ODER und NICHT geschrieben wird.

Verweise