\begin{slide}{Basis-Funktionen}

Die Funktionen 
\begin{itemize}
\item Nicht (einstellig)
\item Oder (beliebig viele Stellen)

  $\verb|Oder|(x_1,\ldots,x_n)=1$ gdw. wenigstens ein $x_i=1$
\item Und (beliebig viele Stellen)

  $\verb|Und|(x_1,\ldots,x_n)=1$ gdw. alle $x_i=1$
\end{itemize}
bilden eine \emph{Basis}: man kann jede andere Boolesche Funktion
durch Kombination von Nicht, Oder, Und darstellen
(evtl. Autotool-Aufgabe dazu).


Beispiele:
\(
\begin{array}{rcl}
(x \to y) & = & \text{Oder}(\text{Nicht}(x),y) = !x \oder y \\
(x \verb|==| y) & = &  (!x \und !y) \oder (x \und y).
\end{array}
\)

\end{slide}

\begin{slide}{Basis-Satz (Beweis-Idee)}

Man stellt $f$ als \emph{Disjunktion} von Funktionen $f_1, f_2, \dots$ dar
(je eine Funktion f�r jede $1$ in der Wertetabelle von $f$)
\begin{small}
\[
\begin{array}{cc|c}
x & y & f(x,y) \\ \hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 
\end{array}
\quad
\begin{array}{cc|c}
f_1(x,y) \\ \hline
1 \\
0 \\
0 \\
0 
\end{array}
\quad
\begin{array}{cc|c}
f_2(x,y) \\ \hline
0 \\
0 \\
0 \\
1 
\end{array}
\]
\end{small}
Jedes solche $f_i$ hat dann genau eine $1$ in seiner Wertetabelle,
kann also selbst als \emph{Konjunktion} dargestellt werden.
\[
f_1(x,y) = !x \und !y, \quad  f_2(x,y)= x\und y
\]

\end{slide}




