Per provare la completezza di NOR e NAND, dimostriamo innanzitutto che i connettivi possono essere definiti attraverso formule che contengono solo connettivi NOR o solo NAND:
Avendo dimostrato che i connettivi possono essere definiti attraverso formule che contengono solo NOR o solo NAND, possiamo ora ridurre la dimostrazione della completezza di NOR e NAND alla completezza dell'insieme .
In base alla definizione di insieme funzionalmente completo, si deve dimostrare che, per ogni funzione booleana , esiste una formula proposizionale , costruita mediante i connettivi dell'insieme , tale che .
Per ogni assegnazione booleana tale che , con , siano:
, per ogni , i simboli proposizionali tali che ;
, per ogni , i simboli proposizionali tali che .
è soddisfatta da una qualsiasi delle assegnazioni booleane ; dunque, per rendere vera , basta verificare se effettivamente le è stata assegnata una delle . Per fare ciò, per ogni si controlla se tutti i simboli proposizionali sono effettivamente veri, e se tutti i simboli proposizionali sono effettivamente falsi, negandoli. Formalmente, ciò è tradotto in una disgiunzione di congiunzioni che rappresenta il processo appena descritto, detta forma normale disgiunta.
Estendiamo e al caso più generale di argomenti, definendo i connettivi e :
;
.
Possiamo ora esprimere in forma normale disgiunta come:
.
Quindi, abbiamo dimostrato che effettivamente esiste, dunque la tesi è dimostrata: è funzionalmente completo. Da ciò deriva che anche i connettivi NOR e NAND e, di conseguenza, anche gli insiemi e sono funzionalmente completi.