

\begin{slide}{Eine Basis mit einem Element}

Die Funktion $\nand: (x,y) \mapsto ~!(x \und y)$
bildet eine Basis.
\begin{small}
\[
\begin{array}{cc|c|c}
x & y & x \und y & \nand(x,y) \\ \hline
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 1\\
1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0
\end{array}
\]
\end{small}
Beweis: wir können diese Funktionen darstellen:
\begin{itemize}
\item
  Nicht: \quad $!x = \nand(x,x)$
\item
  Und: \quad $x \und y = !\nand(x,y)$
\item
  Oder: \quad $x \oder y = \nand(!x,!y)$.
\end{itemize}
\dots und mit dieser Basis auch alle anderen.


\end{slide}
