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.