Eine Basis mit einem Element

Die Funktion nand : (x, y) $\mapsto$  !(x &&y) bildet eine Basis.

x y x &&y nand(x, y)

0 0 0 1

0 1 0 1

1 0 0 1

1 1 1 0

Beweis: wir können diese Funktionen darstellen:

• Nicht:      !x = nand(x, x)
• Und:      x &&y = !nand(x, y)
• Oder:      x | y = nand(!x,!y).

...und mit dieser Basis auch alle anderen.