Basis-Funktionen

Die Funktionen

• Nicht (einstellig)
• Oder (beliebig viele Stellen)

  Oder(x₁,..., x_n) = 1 gdw. wenigstens ein x_i = 1

• Und (beliebig viele Stellen)

  Und(x₁,..., x_n) = 1 gdw. alle x_i = 1

bilden eine Basis: man kann jede andere Boolesche Funktion durch Kombination von Nicht, Oder, Und darstellen (evtl. Autotool-Aufgabe dazu).

Beispiele:

$$\to$$ = Oder(Nicht(x), y) = !x | y

(x==y) = (!x &&!y) |(x &&y).