Hors programme. La porte NAND, définie par a nand b = not(a and b)…

Les trois constructions.

$$\text{not}a=a\text{nand}a,a\text{and}b=\text{not}(a\text{nand}b),a\text{or}b=(\text{not}a)\text{nand}(\text{not}b).$$

La première : $a\text{nand}a=\text{not}(a\text{and}a)=\text{not}a$. La deuxième est la définition, niée. La troisième est De Morgan : $\text{not}(\text{not}a\text{and}\text{not}b)=a\text{or}b$.

def nand(a, b):
    """NAND sur des bits 0/1. Precondition : a et b valent 0 ou 1."""
    return 1 - (a & b)


def non(a):
    return nand(a, a)


def et(a, b):
    return nand(nand(a, b), nand(a, b))


def ou(a, b):
    return nand(nand(a, a), nand(b, b))

>>> [(a, b, non(a), et(a, b), ou(a, b))
...  for a in (0, 1) for b in (0, 1)]
[(0, 0, 1, 0, 0), (0, 1, 1, 0, 1),
 (1, 0, 0, 0, 1), (1, 1, 0, 1, 1)]

Les colonnes reconstruites coïncident avec a & b et a | b sur les quatre lignes. $✓$

Pourquoi cela compte. Un fondeur qui sait graver une porte sait graver toutes les fonctions logiques. Les circuits réels sont donc massivement construits en NAND — c'est une porte plus simple et plus rapide à fabriquer en technologie CMOS qu'un ET suivi d'un NON.

Prolongement : NOR est l'autre porte universelle. En revanche $\{$and, or$\}$ sans not ne l'est pas : ces deux opérateurs rendent $0$ sur $(0,0)$, donc toute combinaison en fait autant, et not est hors d'atteinte.