path: root/dt-boolesche-funktionen.tex

% !TEX root = dt-slides-dt.tex
\section{Boolesche Variable}

\begin{frame}
\frametitle{Boolesche Variablen}
\begin{center}
\LARGE Boolesche Variablen
\end{center}
\end{frame}

\begin{frame}
\frametitle{Boolesche Variablen}
\begin{block}{Boolesche Variablen}
können nur zwei Werte annehmen. Die zwei Werte können 0 und 1 sein oder wahr und falsch
oder true und false. Es kommt darauf an, dass eine boolesche Variable nur zwei Werte annehmen kann. In dieser Veranstaltung hat eine boolesche Variable die möglichen Werte 0 und 1.
\end{block}
\begin{block}{Kodierung}
ist die Zuordnung von einem Zustand oder einer Bedeutung zu dem Wert einer booleschen Variable.
\end{block}
\begin{exampleblock}{Kodierungsbeispiel - Pumpe}
In einem Tank gibt es ein Füllstandsschalter. Mit einer Pumpe wird Wasser in den Tank gepumpt. Das System wird mit zwei booleschen Variablen beschrieben. Die Variable f gibt den Zustand des Füllstandsschalters an und die Variable p gibt an ob die Pumpe ein- oder ausgeschaltet ist. Der Füllstand ist naturgemäß ein kontinuierlicher Wert, z.B. 3849 Liter. Ein solcher Parameter kann nicht mit einer booleschen Variable abgebildet werden. Darstellbar ist aber in diesem Beispiel, ob der Füllstand größer oder kleiner zum Beispiel 5000 Liter ist. Ob der Zustand "Füllstand größer 5000 Liter" mit einer 0 oder einer 1 kodiert wird, muss definiert werden. In der folgenden Tabelle ist eine mögliche Kodierung angegeben. 
\begin{center}
\begin{tabular}{c|c|c}
Boolesche Variable & Wert & Bedeutung \\\hline
f & 0 &  Füllstand ist größer 5000 Liter \\
f & 1 & Füllstand ist kleiner 5000 Liter \\
p & 0 & Pumpe ist ausgeschaltet \\
p & 1 & Pumpe ist eingeschaltet \\
\end{tabular}
\end{center}
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Boolesche Variablen}

\begin{exampleblock}{Kodierungsbeispiel - Abstimmung}
Drei Teilnehmer Alfred, Berti und Carola stimmen über einen Vorschlag ab. Die Stimmen werden durch die Variablen a, b und c für Alfred, Berti und Carola repräsentiert. Das Ergebnis der Abstimmung ist "Vorschlag angenommen" oder "Vorschlag abgelehnt" und wird mit der Variable y repräsentiert. Eine mögliche Kodierung der Abstimmung ist:
\begin{center}
\begin{tabular}{c|c|c}
Boolesche Variable & Wert & Bedeutung \\\hline
y & 0 & Vorschlag abgelehnt \\
y & 1 & Vorschlag angenommen \\
a, b, c & 0 & Teilnehmer stimmt gegen den Vorschlag \\
a, b, c & 1 & Teilnehmer stimmt für den Vorschlag\\
\end{tabular}
\end{center}
Mit einer booleschen Variable lässt sich keine Abstimmung darstellen, bei denen es "dafür", "dagegen" und "Enthaltung" gibt, denn das sind drei Möglichkeiten.
\end{exampleblock}
\end{frame}


\section{Boolesche Funktionen}

\begin{frame}
\frametitle{Boolesche Funktionen}
\begin{center}
\Large Boolesche Funktionen
\end{center}
\end{frame}


\begin{frame}
\frametitle{Boolesche Funktionen}
\begin{block}{Boolesche Funktionen}
bilden eine oder mehrere boolesche Variablen auf den Wert 0 oder 1 ab. Das Ergebnis ist also auch zweiwertig.
\end{block}
\begin{exampleblock}{Beispiel Abstimmungsfunktion mit Einstimmigkeit}
Drei Teilnehmer Alfred, Berti und Carola stimmen über einen Vorschlag ab. Der Vorschlag ist angenommen, wenn alle drei dem Vorschlag zustimmen. Bei der Abstimmung kann man nur dafür oder dagegen sein. Mit der Kodierung aus dem vorherigen Kapitel ergibt sich: Wenn a, b und c den Wert 1 haben, dann ist der Funktionswert y auch 1. In allen anderen Fällen ist y 0.
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Boolesche Funktionen}
\begin{exampleblock}{Beispiel Katzenerkennungsfunktion}
\begin{center}
\includegraphics[width=0.48\textwidth]{booleanfunctions/katze-rene}
\includegraphics[width=0.48\textwidth]{booleanfunctions/katze-grafi}
\captionof{figure}{Katzenbilder mit 500 mal 333 Punkten schwarz/weiß. Quelle: Eigene Bearbeitung eines Fotos von Rene Schwietzke(links) und von Olybrius}
\end{center}
Die Funktion f hat den Wert 1, wenn auf einem Bild mit 500 mal 333 Punkten eine Katze abgebildet ist. Ansonsten hat die Funktion den Wert 0. Jeder Punkt des Bildes ist entweder schwarz oder weiß. Jedem Punkt des Bildes wird eine boolesche Variable zugeordnet. Wenn ein Punkt schwarz ist, hat die zugehörige Variable den Wert 1 und wenn der Punkt weiß ist hat sie den Wert 0. Die Funktion f hängt von 166500 booleschen Variablen ab. 
\center
$y = f(x_1, x_2, ... , x_{166500})$. 
\end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Boolesche Funktionen - Darstellung als Wahrheitstabelle}
\begin{exampleblock}{Abstimmung mit Einstimmigkeit als Wahrheitstabelle}
\begin{center}
\begin{tabular}{ccc|c}
a  & b & c & f(a,b,c)\\\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 \\
\end{tabular}
\end{center}
\end{exampleblock}
Eine Wahrheitstabelle lässt sich schematisch konstruieren. Dazu wechselt der Wert der ersten Variablen (hier: c) in jeder Zeile. Die nächste Variable (hier: b) wechselt den Wert in jeder zweiten Zeile. Die folgende (hier: a) nach der vierten Zeile. Mit diesem Schema kann man sicherstellen, das keine Kombination vergessen wird oder doppelt in der Tabelle auftaucht. Die Anzahl der Kombinationsmöglichkeiten K der Werte von n Variablen ist durch Gleichung \ref{equ:kombvar} gegeben.
%
\begin{equation}
K = 2^n 
\label{equ:kombvar}
\end{equation}
\end{frame}

\begin{frame}
\frametitle{Boolesche Grundfunktionen}
\begin{block}{Alle möglichen Funktionen von einer booleschen Variablen}
\begin{center}
\begin{tabular}{c|cccc}
a & $f_0$ & $f_1$ & $f_2$ & $f_3$   \\\hline
0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 \\
   & & & not & \\
\end{tabular}
\end{center}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Boolesche Grundfunktionen}
\begin{block}{Alle möglichen Funktionen von zwei booleschen Variablen}
\begin{center}
\begin{tabular}{cc|cccccccccccccccc}
a & b & $f_0$ & $f_1$ & $f_2$ & $f_3$ & $f_4$ & $f_5$ & $f_6$ & $f_7$ & $f_8$ & $f_9$ & $f_{10}$ & $f_{11}$ & $f_{12}$ & $f_{13}$ & $f_{14}$ & $f_{15}$  \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
   &    &     & and & & & &  & xor & or & nor & xnor &not b&&not a&& nand \\ 
\end{tabular}
\end{center}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Boolesche Grundfunktionen}
\begin{tabu}{ccccc}
Name & Wahrheitstabelle & \begin{tabular}{c} Algebraische \\ Darstellung \end{tabular} & \begin{tabular}{c} Schaltsymbol \\ IEC 60617-12   \end{tabular} & \begin{tabular}{c} Schaltsymbol\\ US ANSI/IEEE\\Std 91a-1991 \end{tabular} \\\hline
BUFFER & 
\begin{tabular}{c|c}
a & y \\\hline
0 & 0 \\
1 & 1  \\
\end{tabular}
&
$y = a$
&
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[buffer gate] (inv) {};
\draw (inv.input) -- ++(left:5mm)node[left]{a};
\draw (inv.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[buffer gate] (inv) {};
\draw (inv.input) -- ++(left:5mm)node[left]{a};
\draw (inv.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} \\
NOT & 
\begin{tabular}{c|c}
a & $\overline{a}$ \\\hline
0 & 1 \\
1 & 0  \\
\end{tabular}
&
$y = \overline{a} $
&
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[not gate] (inv) {};
\draw (inv.input) -- ++(left:5mm)node[left]{a};
\draw (inv.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[not gate] (inv) {};
\draw (inv.input) -- ++(left:5mm)node[left]{a};
\draw (inv.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} \\
\end{tabu}
\end{frame}


\begin{frame}
\frametitle{Boolesche Grundfunktionen}
\begin{tabu}{ccccc}
Name & Wahrheitstabelle & \begin{tabular}{c} Algebraische \\ Darstellung \end{tabular} & \begin{tabular}{c} Schaltsymbol \\ IEC 60617-12   \end{tabular} & \begin{tabular}{c} Schaltsymbol\\ US ANSI/IEEE\\Std 91a-1991 \end{tabular} \\\hline
AND 
& 
\begin{tabular}{cc|c}
a & b & $a \cdot b$ \\\hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 
\end{tabular}
&
$y = a \cdot b$ 
& 
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[and gate] (and) {};
\draw (and.input 1) -- ++(left:5mm) node[left]{a};
\draw (and.input 2) -- ++(left:5mm) node[left]{b};
\draw (and.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[and gate] (and) {};
\draw (and.input 1) -- ++(left:5mm) node[left]{a};
\draw (and.input 2) -- ++(left:5mm) node[left]{b};
\draw (and.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
 \\
NAND 
& 
\begin{tabular}{cc|c}
a & b & $\overline{a \cdot b}$ \\\hline
0 & 0 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 
\end{tabular}
&
$y = \overline{a \cdot b}$ 
& 
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[nand gate] (and) {};
\draw (and.input 1) -- ++(left:5mm) node[left]{a};
\draw (and.input 2) -- ++(left:5mm) node[left]{b};
\draw (and.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[nand gate] (and) {};
\draw (and.input 1) -- ++(left:5mm) node[left]{a};
\draw (and.input 2) -- ++(left:5mm) node[left]{b};
\draw (and.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
 \\
OR
& 
\begin{tabular}{cc|c}
a & b & $a + b$ \\\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 
\end{tabular}
&
$y = a + b$ 
& 
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[or gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[or gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
 \\
NOR
& 
\begin{tabular}{cc|c}
a & b & $\overline{a + b}$ \\\hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 0 
\end{tabular}
&
$y = \overline{a + b}$ 
& 
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[nor gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[nor gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
\end{tabu}
\end{frame}


\begin{frame}
\frametitle{Boolesche Grundfunktionen}
\begin{tabu}{ccccc}
Name & Wahrheitstabelle & \begin{tabular}{c} Algebraische \\ Darstellung \end{tabular} & \begin{tabular}{c} Schaltsymbol \\ IEC 60617-12   \end{tabular} & \begin{tabular}{c} Schaltsymbol\\ US ANSI/IEEE\\Std 91a-1991 \end{tabular} \\\hline
XOR
& 
\begin{tabular}{cc|c}
a & b & $a \oplus b$ \\\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 
\end{tabular}
&
$y = a \oplus b$ 
& 
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[xor gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[xor gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
 \\
XNOR
& 
\begin{tabular}{cc|c}
a & b & $\overline{a \oplus b}$ \\\hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 
\end{tabular}
&
$y = \overline{a \oplus b}$ 
& 
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[xnor gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
&
\begin{tikzpicture}[circuit logic US, circuit ee IEC]
\draw node[xnor gate] (g) {};
\draw (g.input 1) -- ++(left:5mm) node[left]{a};
\draw (g.input 2) -- ++(left:5mm) node[left]{b};
\draw (g.output) -- ++(right:5mm)node[right]{y};
\end{tikzpicture} 
 \\
\end{tabu}
\end{frame}


\begin{frame}
\frametitle{Grundfunktion UND}
$y = a \cdot b \cdot c \cdot ...$ wird 1, wenn alle Variablen a, b, c, ... den Wert 1 haben. Ansonsten hat die Funktion y den Wert 0. 

\vspace{1cm}

\begin{tabular}{cccc|c}
a & b & c & d & $a \cdot b \cdot c \cdot d$  \\\hline
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 \\ 
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1   
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Grundfunktion ODER}
$y = a + b + c + ...$ wird 0, wenn alle Variablen a, b, c, ... den Wert 0 haben. Ansonsten hat die Funktion y den Wert 1.

\vspace{1cm}

\begin{tabular}{cccc|c}
a & b & c & d & $a + b + c + d$  \\\hline
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 & 1 \\ 
1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1   
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Grundfunktion XOR (Parity)}
$y = a \oplus b \oplus c \oplus ...$ wird 1, wenn eine ungerade Anzahl von Variablen den Wert 1 hat, ansonsten ist der Wert 0.

\vspace{1cm}
\begin{tabular}{lp{5cm}}
\begin{tabular}{cccc|c}
a & b & c & d & $a + b + c + d$  \\\hline
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 \\ 
1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0   
\end{tabular}
& 
Eine Änderung bei einem Bit führt\newline
zu einer Änderung des XOR Ergebnisses.

Die XOR Funktion wird auch "Parity" genannt.
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Beispielfunktion mit graphischer Darstellung, booleschem Ausdruck und WHT}
\begin{columns}
\column[T]{0.5\textwidth}
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw node[and gate] (and) {};
\draw (and.input 1) -- ++(left:5mm) node[left]{a};
\draw (and.input 2) -- ++(left:5mm) node[left](b) {b};
\draw (and.output) -- ++(right:5mm) -- ++(down:5mm) -- ++(right:5mm) node[or gate, anchor= input 1](or){} ;
\draw (or.output) -- ++(right:5mm)node[right]{y};
\draw (or.input 2) -- (or.input 2 -| b.east) node[left]{c};
\end{tikzpicture}
\column[T]{0.3\textwidth}
$y = a \cdot b + c$

\vspace{2cm}

\begin{tabular}{ccc|c}
a & b & c & y \\\hline
0 & 0 & 0 & 0  \\
0 & 0 & 1 & 1  \\
0 & 1 & 0 & 0  \\
0 & 1 & 1 & 1  \\
1 & 0 & 0 & 0  \\
1 & 0 & 1 & 1  \\
1 & 1 & 0 & 1  \\
1 & 1 & 1 & 1  
\end{tabular}
\end{columns} 
\end{frame}

\begin{frame}
\frametitle{Abstimmungsfunktion mit Mehrheitsentscheid - boolescher Ausdruck aus WHT}
\begin{tabular}{ccc|c}
a & b & c & y \\\hline
0 & 0 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 1 & 0 & 0  \\
0 & 1 & 1 & 1  \\
1 & 0 & 0 & 0  \\
1 & 0 & 1 & 1  \\
1 & 1 & 0 & 1  \\
1 & 1 & 1 & 1  
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Abstimmungsfunktion mit Mehrheitsentscheid aus Grundgattern}

\begin{tikzpicture}[circuit logic IEC, circuit ee IEC,scale=0.8]
\draw (0,2) node[or gate] (orbc) {};
\draw (0,0) node[and gate] (andbc) {};
\draw (2,3) node[and gate] (anda) {};
\draw (4,2) node[or gate] (orall) {};
\draw (orbc.input 1) -- ++(left:1cm) node[contact] (cb) {} -- ++(left:1cm) node[anchor=east] {b};
\draw (orbc.input 2) -- ++(left:1.5cm) node[contact] (cc) {} -- ++(left:0.5cm) node[anchor=east] {c};
\draw (orbc.output) -- ++(right:3mm) |- (anda.input 2);
\draw (anda.input 1) -- ++(left:4cm) node[anchor=east] {a};
\draw (andbc.input 1) -| (cb);
\draw (andbc.input 2) -| (cc);
\draw (andbc.output) -- ++(right:3cm) |- (orall.input 2);
\draw (anda.output) -- ++(right:1cm) |- (orall.input 1);
\draw (orall.output) -- ++(right:1cm) node[anchor=west] {y};
\end{tikzpicture}

\vspace{1cm}
\hspace{4cm}
\begin{tabular}{ccc||c|c|c|c}
a & b & c & $b + c$ & $a \cdot (b + c)$ & $bc$ & $a \cdot (b + c) + bc$ \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 0 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1  
\end{tabular}

\end{frame}

\begin{frame}
\frametitle{Shannons Theoreme}
\begin{tabular}{llp{4cm}}
Nummer & Theorem & Bemerkung\\\hline
1a & $x + y = y + x$                      & Kommutativgesetz\\
1b & $x \cdot y = y \cdot x$           & \\[2mm] 
2a & $x + (y + z) = (x + y) + z$      & Assoziativgesetz\\
2b & $x \cdot (y \cdot z) = (x \cdot y) \cdot z$  & \\[2mm] 
3a & $x \cdot (y + z) = x\cdot y + x \cdot z$      & Distributivgesetz\\
3b & $x + y \cdot z = (x + y) \cdot (x + z)  $        & \\[2mm] 
4a & $1 \cdot x = x$ & \\
4b & $0 + x = x$ &\\[2mm] 
5a & $1 + x = 1$ &\\
5b & $0 \cdot x = 0$ & \\[2mm] 
6a & $x + \overline{x} = 1$ & \\
6b & $x \cdot \overline{x} = 0$ \\[2mm] 
7a & $\overline{0} = 1$\\
7b & $\overline{1} = 0$\\[2mm] 
8   & $\overline{\overline{x}} = x$\\[2mm] 
9a & $\overline{x + y + z + ....} = \overline{x} \cdot \overline{y} \cdot \overline{z} \cdot .... $ & De Morgan \\
9b & $\overline{x \cdot y \cdot z \cdot ...} = \overline{x} + \overline{y} + \overline{z} + .... $ \\[2mm] 
14a & $x = x + x = x + x + x + ... $ & \\
14b & $x = x \cdot x = x \cdot x \cdot x \cdot ...$ & \\
\end{tabular}
\end{frame}



\begin{frame}
\frametitle{Minterm}
\begin{enumerate}
\item{alle Variablen der Funktion genau einmal vorkommen,}
\item{alle Variablen entweder negiert sind oder nicht,}
\item{alle Variablen mit der UND Funktion verknüpft sind.}
\end{enumerate}
Beispiele für Minterme der Funktion $y=f(a,b,c,d)$ sind
\begin{itemize}
\item{$a \cdot b \cdot c \cdot d$}
\item{$a \cdot \overline{b} \cdot c \cdot d$}
\item{$a \cdot b \cdot \overline{c} \cdot \overline{d}$}
\end{itemize}

Keine Minterme
\vspace{5mm}

\begin{tabular}{ll}
Ausdruck & Begründung\\\hline
$a \cdot b \cdot c$ & Es fehlt die Variable d \\
$a \cdot \overline{b \cdot c} \cdot d$ & $\overline{b \cdot c}$ ist nicht zulässig\\
$(a + b) \cdot \overline{c} \cdot \overline{d}$ & $a+b$ ist nicht zulässig
\end{tabular}
\end{frame}



\begin{frame}
\frametitle{Minterm Wahrheitstabelle}
\center
\begin{tabular}{cccc|ccc}
a & b & c & d & $a \cdot b \cdot c \cdot d$ & $a \cdot \overline{b} \cdot c \cdot d$ & $a \cdot b \cdot \overline{c} \cdot \overline{d}$ \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0  \\ 
1 & 0 & 0 & 0 & 0 & 0 & 0  \\
1 & 0 & 0 & 1 & 0 & 0 & 0  \\
1 & 0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 0  \\
1 & 1 & 1 & 0 & 0 & 0 & 0  \\
1 & 1 & 1 & 1 & 1 & 0 & 0   
\end{tabular}

\end{frame}


\begin{frame}
\frametitle{Maxterm}
\begin{enumerate}
\item{alle Variablen der Funktion genau einmal vorkommen,}
\item{alle Variablen entweder negiert sind oder nicht,}
\item{alle Variablen mit der ODER Funktion verknüpft sind.}
\end{enumerate}
Beispiele für Maxterme der Funktion $y=f(a,b,c,d)$ sind
\begin{itemize}
\item{$a + b + c + d$}
\item{$a + \overline{b} + c + d$}
\item{$a + b + \overline{c} + \overline{d}$}
\end{itemize}

Keine Maxterme

\begin{tabular}{ll}
Ausdruck & Begründung\\\hline
$a + b + c$ & Es fehlt die Variable d \\
$a + \overline{b + c} + d$ & $\overline{b + c}$ ist nicht zulässig\\
$a + b + \overline{c} \cdot \overline{d}$ & $ \overline{c} \cdot \overline{d}$ ist nicht zulässig
\end{tabular}

\end{frame}

\begin{frame}
\frametitle{Maxterme Wahrheitstabelle}
\center
\begin{tabular}{cccc|ccc}
a & b & c & d & $a + b + c + d$ & $a + \overline{b} + c + d$ & $a + b + \overline{c} + \overline{d}$ \\\hline
0 & 0 & 0 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 & 0\\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 & 1 & 1  \\ 
1 & 0 & 0 & 0 & 1 & 1 & 1  \\
1 & 0 & 0 & 1 & 1 & 1 & 1  \\
1 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 1  \\
1 & 1 & 1 & 0 & 1 & 1 & 1  \\
1 & 1 & 1 & 1 & 1 & 1 & 1   
\end{tabular}
\end{frame}


\begin{frame}
\frametitle{Disjunktive Normalform}
\center
\begin{tabular}{ccc||ccccc}
a & b & c & $m_3 = \overline{a} \cdot b \cdot c$ & $m_5 = a \cdot \overline{b} \cdot c$ & $m_6 = a \cdot b \cdot \overline{c}$ & $m_7 = a \cdot b \cdot c$ & $m_3 + m_5 + m_6 + m_7$  \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1  
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Konjunktive Normalform}
\center
\begin{tabular}{ccc||ccccc}
a & b & c & $m_0 = a + b + c$ &$m_1 = a+b+\overline{c}$&$m_2 = a + \overline{b} + c$ & $m_4 = \overline{a} + b + c$ & $m_0\mathord{\cdot}m_1\mathord{\cdot}m_2\mathord{\cdot}m_4$  \\\hline
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1  
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Beispiele Anwendung boolescher Theoreme}
$y = \left( a \oplus b \right) + ab$ 
\vspace{2cm}

$y = a + \left( \overline{a} b \right)$
\vspace{2cm}

Nur mit NAND
$y = \overline{a \oplus b}$
\vspace{2cm}
\end{frame}

\subsection{Vollständige Operatorensysteme}

\begin{frame}
\frametitle{NAND und NOR als vollständige Operatorensysteme}
\begin{block}{Vollständige Operatorensysteme}
Vollständige Operatorensysteme sind Kombinationen aus Operatoren mit denen man ALLE möglichen booleschen Funktionen darstellen kann. Mit der Disjunktiven Normalform (DNF) kann man jede boolesche Funktion mit einer Kombination aus UND, ODER und NICHT darstellen. Deshalb bilden UND, ODER und NICHT ein vollständiges Operatorensystem.
\end{block}
\begin{exampleblock}{NAND ist ein vollständiges Operatorensystem}
Die NAND Funktion ist ein vollständiges Operatorensystem. 
\begin{align}
\overline{x} &= \overline{x \cdot x}\\
x \cdot y &= \overline{\overline{x \cdot y}}\\
               &= \overline{\overline{x \cdot y} \cdot 1}\\
x  + y &= \overline{\overline{x + y}}\\
          &=  \overline{\overline{x} \cdot \overline{y} }\\
          &= \overline{\overline{x \cdot x} \cdot \overline{y \cdot y} }
\end{align}
\end{exampleblock}
NOR bildet auch ein vollständiges Operatorensystem.
\end{frame}


\begin{frame}
\frametitle{1962 - Apollo Guidance Computer }
\begin{columns}
  \begin{column}{0.5\textwidth}
    \includegraphics[width=\textwidth]{booleanfunctions/1962-apollo-guidance-computer} 
    
    \includegraphics[width=\textwidth]{booleanfunctions/1962-apollo-nor-gate} 
  \end{column}
  \begin{column}{0.5\textwidth}
  \begin{itemize}
    \item Micrologic Type "G" 3-NOR
    \item 4000 identische NOR Gates mit drei Eingängen
    \item \$20-\$30 pro Chip
    \item 16 Bit Wortbreite
    \item 1 MHz Taktfrequenz
    \item 70W Leistungsverbrauch
    \item 28V Spannung
    \item Fairchild Semiconductor
\end{itemize}  
    \end{column}
\end{columns}        
\end{frame}

\section{Beispielanwendung ECC}

\begin{frame}
\frametitle{Beispielanwendung ECC}

\begin{block}{Error Checking and Correction (ECC)}
Fehlererkennung und Fehlerkorrektur kann bei der Datenübertragung und z.B. beim Speichern in NAND Flash eingesetzt werden.
\end{block}

\begin{block}{Problem}
Wie kann man bei Übertragungs- oder Speicherfehlern herausfinden, ob es zu Bitfehlern kam? Kann man zusätzlich die Bitfehler korrigieren?
\end{block}

\begin{block}{Idee}
Aus den Datenbits werden Prüfbits berechnet. Die Prüfbits werden zusammen mit den Datenbits gespeichert oder übertragen. Nach der Übertragung werden aus den empfangenen Datenbits wieder die Prüfbits berechnet und mit den empfangenen Prüfbits verglichen. 
\end{block}

\begin{columns}
\column[T]{0.4\textwidth}
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw (0,0) node[fill=yellow!80, minimum width=4cm,minimum height=1cm] (db) {Datenbits};
\draw (db.east) node[fill=blue!20,anchor=west,minimum height=1cm] {Prüfbits};
\end{tikzpicture}

\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw (0,0) node {$d_7$};
\draw (0.5,0) node {$d_6$};
\draw (1,0) node {$d_5$};
\draw (1.5,0) node {$d_4$};
\draw (2.0,0) node {$d_3$};
\draw (2.5,0) node {$d_2$};
\draw (3.0,0) node {$d_1$};
\draw (3.5,0) node {$d_0$};
\draw (0.75,-0.5) node[fill=magenta!20, minimum width=2cm] {P2};
\draw (2.75,-0.5) node[fill=magenta!40, minimum width=2cm] {P2'};
\draw (0.25,-1) node[fill=green!20, minimum width=1cm] {P1};
\draw (2.25,-1) node[fill=green!20, minimum width=1cm] {P1};
\draw (1.25,-1) node[fill=green!40, minimum width=1cm] {P1'};
\draw (3.25,-1) node[fill=green!40, minimum width=1cm] {P1'};
\draw (0,-1.5) node[fill=orange!20, minimum width=0.4cm] {\small{P0}};
\draw (1,-1.5) node[fill=orange!20, minimum width=0.4cm] {\small{P0}};
\draw (2,-1.5) node[fill=orange!20, minimum width=0.4cm] {\small{P0}};
\draw (3,-1.5) node[fill=orange!20, minimum width=0.4cm] {\small{P0}};
\draw (0.5,-1.5) node[fill=orange!40, minimum width=0.4cm] {\small{P0'}};
\draw (1.5,-1.5) node[fill=orange!40, minimum width=0.4cm] {\small{P0'}};
\draw (2.5,-1.5) node[fill=orange!40, minimum width=0.4cm] {\small{P0'}};
\draw (3.5,-1.5) node[fill=orange!40, minimum width=0.4cm] {\small{P0'}};
\end{tikzpicture}
\column[T]{0.6\textwidth}
\begin{align*}
\text{P2} &= d_7 \oplus d_6 \oplus d_5 \oplus d_4
\hspace{1cm}
\text{P2'} = d_3 \oplus d_2 \oplus d_1 \oplus d_0\\
\text{P1} &= d_7 \oplus d_6 \oplus d_3 \oplus d_2
\hspace{1cm}
\text{P1'} = d_5 \oplus d_4 \oplus d_1 \oplus d_0\\
\text{P0} &= d_7 \oplus d_5 \oplus d_3 \oplus d_1
\hspace{1cm}
\text{P0'} = d_6 \oplus d_4 \oplus d_2 \oplus d_0
\end{align*}

\begin{itemize}
\item P2,P2',P1,P1',P0,P0' als Prüfbits
\item Ein Bitfehler im Datenblock kann korrigiert werden
\item Zwei Bitfehler im Datenblock können erkannt werden
\item Ein Bitfehler im Prüfblock kann erkannt werden
\end{itemize}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Beispielanwendung ECC - Samsung Algorithmus}

\begin{block}{Ein Fehler in den Datenbits}
Ein Fehler bei einem Bit in den Datenbits $d_7$ bis $d_0$ wirkt sich immer auf drei Prüfbits aus. Wenn beispielsweise ein Fehler im Bit $d_3$ auftritt, dann sind P2', P1 und P0 betroffen, d.h. bei diesen drei Prüfbits gibt es eine Abweichung zwischen gespeicherten und berechneten Prüfbits.
\end{block}

\begin{block}{Beispiel für einen Bitfehler in den Datenbits}
d = "10110001" ergibt
\begin{align*}
\text{P2} &= 1 \oplus 0 \oplus 1 \oplus 1 = 1
\hspace{1cm}
\text{P2'} = 0 \oplus 0 \oplus 0 \oplus 1 = 1\\
\text{P1} &= 1 \oplus 0 \oplus 0 \oplus 0 = 1
\hspace{1cm}
\text{P1'} = 1 \oplus 1 \oplus 0 \oplus 1 = 1\\
\text{P0} &= 1 \oplus 1 \oplus 0 \oplus 0 = 0
\hspace{1cm}
\text{P0'} = 0 \oplus 1 \oplus 0 \oplus 1 = 0
\end{align*}
Wenn dann beim Lesen ein Bitfehler bei $d_3$ auftritt ($\Rightarrow$ d = "1011\textcolor{red}{1}001") ergibt sich
\begin{align*}
\text{P2} &= 1 \oplus 0 \oplus 1 \oplus 1 = 1
\hspace{1cm}
\text{P2'} = \textcolor{red}{1} \oplus 0 \oplus 0 \oplus 1 = \textcolor{red}{0} \\
\text{P1} &= 1 \oplus 0 \oplus \textcolor{red}{1} \oplus 0 = \textcolor{red}{0}
\hspace{1cm}
\text{P1'} = 1 \oplus 1 \oplus 0 \oplus 1 = 1\\
\text{P0} &= 1 \oplus 1 \oplus \textcolor{red}{1} \oplus 0 = \textcolor{red}{1}
\hspace{1cm}
\text{P0'} = 0 \oplus 1 \oplus 0 \oplus 1 = 0
\end{align*} 
\end{block}

\begin{block}{Ein Fehler in den Prüfbits}
Ein Bitfehler in den Prüfbits führt nur zu einem Unterschied bei einem Prüfbit zwischen berechneten und gespeicherten Prüfbits. So können Fehler in den Daten und in den Prüfbits unterschieden werden.
\end{block}

\end{frame}

\begin{frame}
\frametitle{Beispielanwendung ECC - weitere Codes}

\begin{block}{Redundanz}
Bei jedem Code zur Fehlererkennung und -behebung werden zusätzliche redundante Informationen mitgeschickt oder gespeichert. Es steigt damit die erforderliche Datenrate oder Speichergröße.
\end{block}

\begin{block}{Eigenschaften}
Wieviel Redundanz ist in den übertragenen Codeworten? Wieviele und welche Fehler können erkannt oder korrigiert werden?
\end{block}

\begin{itemize}
\item 1950: Hammingcodes: Lochkarten
\item 1959: Bose-Chaudhuri-Hocquenghem Codes (BCH): DVB-T
\item 1960: Reed Solomon Codes (RS): Compact Discs, QR Codes
\item 1962: Low Density Parity Check Codes (LDPC): Wifi 802.11ax
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Hamming Code für 4 Datenbits mit 3 Prüfbits}

\begin{block}{Hammingcode}
Beim Hammingcode werden Prüfbits auch durch überlappende XOR Bereiche in den Daten konstruiert. Hier ein Bespiel mit vier Datenbits und drei Prüfbits.
\end{block}

\begin{tabular}{l|cccc}
    & $d_3$ & $d_2$ & $d_1$ & $d_0$ \\\hline
P3  &   x   &   x   &       &   x   \\
P2  &   x   &       &   x   &   x   \\
P1  &       &   x   &   x   &   x   \\
\end{tabular}
\begin{align*}
\text{P3} &= d_3 \oplus d_2 \oplus d_0 \\
\text{P2} &= d_3 \oplus d_1 \oplus d_0 \\
\text{P1} &= d_2 \oplus d_1 \oplus d_0
\end{align*}

\begin{itemize}
\item Bei einem Bitfehler in den Daten ändern sich zwei oder drei Prüfbits
\item Bei einem Bitfehler bei einem Prüfbit ändert sich nur das eine Prüfbit
\item Die Position des Bitfehlers lässt sich rekonstruieren - wenn beispielsweise P3, P2 und P1 aus den Daten berechnet werden und sich nur P2 und P1 gegenüber den übertragenen Prüfbits unterscheiden, dann muss es einen Fehler in $d_1$ gegeben haben.
\item Damit lässt sich mit drei Prüfbits ein Fehler beheben
\end{itemize}

\end{frame}

\section{Multiplexer}

\begin{frame}
\frametitle{Multiplexer Schaltsymbol}
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw (0,0) node[mux] (m) {};
\draw (m.izero) -- ++(left:1cm) node[anchor=east] {a};
\draw (m.ione) -- ++(left:1cm) node[anchor=east] {b};
\draw (m.output) -- ++(right:1cm) node[anchor=west] {y};
\draw (m.sel) -- ++(down:1cm) node[anchor=north] {s};
\end{tikzpicture} 
\end{frame}

\begin{frame}
\frametitle{Multiplexer Wahrheitstabelle}
\begin{tabular}{ccc||c}
s & a & b & y\\\hline
0 & 0 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 1 & 0 & 1\\
0 & 1 & 1 & 1\\
1 & 0 & 0 & 0\\
1 & 0 & 1 & 1\\
1 & 1 & 0 & 0\\
1 & 1 & 1 & 1  
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Multiplexer boolescher Ausdruck}
\begin{align}
y &= \overline{s} \cdot a \cdot \overline{b} + \overline{s} \cdot a  \cdot b + s \cdot \overline{a} \cdot b + s \cdot a \cdot b \label{equ:muxdnf}\\ 
   &=  \overline{s}  \cdot a \left( \overline{b} + b \right) + s \cdot b \left( \overline{a} + a \right)\nonumber \\
    &= \overline{s} \cdot a + s \cdot b \label{equ:mux}
\end{align}
\end{frame}


\begin{frame}
\frametitle{Multiplexer aus Grundgattern}
\center
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw (0,2) node[and gate,inputs=ni] (anda) {};
\draw (0,0) node[and gate] (andb) {};
\draw (2,1) node[or gate] (or) {};
\draw (anda.input 1) -- ++(left:1cm) node[anchor=east] {a};
\draw (andb.input 1) -- ++(left:1cm) node[anchor=east] {b};
\draw (or.output) -- ++(right:1cm) node[anchor=west] {y};
\draw (anda.input 2) -- ++(left:3mm) coordinate (s) -- ++(down:3cm) node[anchor=north] {s};
\draw (andb.input 2) -- (s |- andb.input 2) node[contact] {};
\draw (anda.output) -- ++(right:5mm) |- (or.input 1);
\draw (andb.output) -- ++(right:5mm) |- (or.input 2);
\end{tikzpicture} 
\end{frame}


\begin{frame}
\frametitle{Multiplexer mit mehr als zwei Dateneingängen}
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw (0,0) -- (0,4) -- (2,3) -- (2,1) -- (0,0);
\draw (0,0.8) node[anchor=west] (d) {11};
\draw (0,1.6) node[anchor=west] (c) {10};
\draw (0,2.4) node[anchor=west] (b) {01};
\draw (0,3.2) node[anchor=west] (a) {00};
\draw (a) -- ++(left:1) node[anchor=east] {a};
\draw (b) -- ++(left:1) node[anchor=east] {b};
\draw (c) -- ++(left:1) node[anchor=east] {c};
\draw (d) -- ++(left:1) node[anchor=east] {d};
\draw (2,2) -- ++(right:1) node[anchor=west] {y};
\coordinate (s1) at ($(0,0)!0.3!(2,1)$);
\coordinate (s0) at ($(0,0)!0.7!(2,1)$);
\draw (s0) -- ++(down:1) coordinate (s0t) node[anchor=north] {s0};
\draw (s1) -- (s1 |- s0t) node [anchor=north] {s1};
\end{tikzpicture} 

\end{frame}

\begin{frame}
\frametitle{Aufbau aus zwei zu eins Multiplexern}
\center
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
\draw (0,2) node[mux] (m0) {};
\draw (0,0) node[mux] (m1) {};
\draw (2,1) node[mux] (m2) {};
\draw (m0.izero) -- ++(left:1) node[anchor=east] {a};
\draw (m0.ione) -- ++(left:1) node[anchor=east] {b};
\draw (m1.izero) -- ++(left:1) node[anchor=east] {c};
\draw (m1.ione) -- ++(left:1) node[anchor=east] {d};
\draw (m0.sel) -- ++(down:0.3) -- ++(left:0.7) -- ++(down:3) coordinate (s0) node[anchor=north] {s0};
\draw (m1.sel) -- ++(down:0.3) -- ++(left:0.7) node[contact] {};
\draw (m2.sel) -- ++(down:0.3) -- ++(left:0.7) -- ++(down:2) node[anchor=north] {s1};
\draw (m2.output) -- ++(right:1) node[anchor=west] {y};
\draw (m0.output) -- ++(right:0.5) |- (m2.izero);
\draw (m1.output) -- ++(right:0.5) |- (m2.ione);
\end{tikzpicture} 
\end{frame}


\begin{frame}
\frametitle{Boolesche Funktionen mit Multiplexern - Beispiel Abstimmungsfunktion}
\begin{tabular}{ccc|c}
a & b & c & y \\\hline
0 & 0 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 1 & 0 & 0  \\
0 & 1 & 1 & 1  \\
1 & 0 & 0 & 0  \\
1 & 0 & 1 & 1  \\
1 & 1 & 0 & 1  \\
1 & 1 & 1 & 1  
\end{tabular}

\end{frame}

\begin{frame}
\frametitle{Baumstruktur und Kettenstruktur}
\begin{columns}
\begin{column}{0.4\textwidth}
\center
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC,scale=0.6]
\draw (0,0) node[and gate] (g0) {};
\draw (0,2) node[and gate] (g1) {};
\draw (0,4) node[and gate] (g2) {};
\draw (0,6) node[and gate] (g3) {};
\draw (2,1) node[and gate] (g4) {};
\draw (2,5) node[and gate] (g5) {};
\draw (4,3) node[and gate] (g6) {};
\foreach \i in {0,1,2,3}
{
\draw (g\i.input 1) -- ++(left:0.5);
\draw (g\i.input 2) -- ++(left:0.5);
}
\draw (g0.output) -- ++(right:0.5) |- (g4.input 2);
\draw (g1.output) -- ++(right:0.5) |- (g4.input 1);
\draw (g2.output) -- ++(right:0.5) |- (g5.input 2);
\draw (g3.output) -- ++(right:0.5) |- (g5.input 1);
\draw (g4.output) -- ++(right:0.5) |- (g6.input 2);
\draw (g5.output) -- ++(right:0.5) |- (g6.input 1);
\draw (g6.output) -- ++(right:0.5);
\end{tikzpicture}
Baumstruktur 
\end{column}
\begin{column}{0.6\textwidth}
\center
\begin{tikzpicture}[circuit logic IEC, circuit ee IEC, scale=0.6]
\coordinate (start) at (0,0) ;
\draw (0,0) -- ++(right:0.5) node [and gate, anchor=input 2] (g0) {};
\draw (g0.input 1) -- ++(left:0.5);
\foreach \i / \in in {0/1,1/2,2/3,3/4,4/5,5/6}
{
\draw (g\i.output) -- ++(right:0.25) -- ++(up:0.5) -- ++(right:0.25) node[and gate, anchor=input 2] (g\in) {};
\draw (g\in.input 1) -- (start |- g\in.input 1);
}
\draw (g6.output) -- ++(right:0.25);
\end{tikzpicture} 
Kettenstruktur
\end{column}
\end{columns}
\begin{block}{Pfad}
Ein Pfad in einer Schaltung ist der Weg von einem Netz oder Eingang durch ein oder mehrere Gatter zu einem anderen Netz oder einem Ausgang.
\end{block}
\begin{block}{Schaltungstiefe}
Jeder Pfad von einem Eingang zu einem Ausgang führt durch eine Anzahl von Gattern. Die Schaltungstiefe ist bestimmt durch den Pfad, der von einem Eingang startet und an einem Ausgang endet und der durch die maximal mögliche Anzahl von Gattern in der Schaltung führt. Die Schaltung links mit der Baumstruktur hat eine Schaltungstiefe von 3. Die Schaltung rechts mit der Kettenstruktur hat eine Schaltungstiefe von 7.
\end{block}

\end{frame}


\begin{frame}
\frametitle{Komplexität - Shannon}
\includegraphics[width=\textwidth]{booleanfunctions/shannon-complexity}

\begin{exampleblock}{Beispiel: Funktion mit 100 Variablen - wieviele Gatter sind notwendig?}
100 Variablen: $\frac{2^{100}}{100} = \frac{2^\frac{3.3 \cdot 100}{3.3}}{100} = \frac{{2^{3.3}}^\frac{100}{3.3}}{100}= \frac{10^{30}}{100} = 10^{28}$ Gatter. 1 Billarde = $10^{15}$. Also mehr als eine Milliarde Billiarden Gatter mit jeweils zwei Eingängen für die allermeisten Funktionen.

Aber: Ein UND Gatter mit 100 Eingängen kann mit 99 UND Gattern mit jeweils zwei Eingängen gebaut werden.
\end{exampleblock}
\vspace{1cm}
aus: Claude Elwood Shannon, The Synthesis of Two-Terminal Switching Circuits, Bell System Technical Journal, Volume 28, pp. 59-98, 1949
\end{frame}