Basis-Satz (Beweis-Idee)

Man stellt f als Disjunktion von Funktionen f1, f2,... dar (je eine Funktion für jede 1 in der Wertetabelle von f)

xyf (x, y)
001
010
100
111
    $\displaystyle \begin{array}{cc\vert c}
f_1(x,y)   \hline
1 \\
0 \\
0 \\
0
\end{array}$    $\displaystyle \begin{array}{cc\vert c}
f_2(x,y)   \hline
0 \\
0 \\
0 \\
1
\end{array}$

Jedes solche fi hat dann genau eine 1 in seiner Wertetabelle, kann also selbst als Konjunktion dargestellt werden.

f1(x, y) = ¬x $\displaystyle \wedge$ ¬y,    f2(x, y) = x $\displaystyle \wedge$ y



Johannes Waldmann 2007-06-04