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:

(x $\to$ y) = Oder(Nicht(x), y) = ¬x $\vee$ y

(x==y) = (¬x $\wedge$ ¬y) $\vee$ (x $\wedge$ y).

Johannes Waldmann 2008-04-08

(x $\to$ y)	=	Oder(Nicht(x), y) = ¬x $\vee$ y
(x`==`y)	=	(¬x $\wedge$ ¬y) $\vee$ (x $\wedge$ y).