XOR à partir de quatre NAND

Posons $g=\text{NAND}(a,b)=\overline{ab}$. On calcule ensuite, par De Morgan puis $a\overline{a}=0$,

$$\text{NAND}(a,g)=\overline{a\overline{ab}}=\overline{a(\overline{a}+\overline{b})}=\overline{a\overline{b}},\text{NAND}(b,g)=\overline{b\overline{a}}.$$

Enfin

$$\text{NAND}(\overline{a\overline{b}},\overline{b\overline{a}})=a\overline{b}+\overline{a}b=a\oplus b,$$

par De Morgan. Quatre NAND suffisent donc ; une recherche exhaustive sur tous les circuits de trois NAND montre qu'elles sont nécessaires. C'est une illustration concrète de l'universalité ; avec des NOR, le même montage donne le XNOR, et le XOR en demande cinq.