Eine Basis mit einem Element

Die Funktion NAND : (x, y) $\mapsto$ ¬(x $\wedge$ y) bildet eine Basis.

$$\wedge$$ 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 $\wedge$ y = ¬NAND(x, y)
• Oder:      x $\vee$ y = NAND(¬x,¬y).

...und mit dieser Basis auch alle anderen.