\documentclass[12pt]{article}
\usepackage{A4,amsmath,amssymb}
\pagestyle{empty}
\parindent0em
\begin{document}
Prof. Dr. Volker Strehl \hfill 6.5.1999
\\
IMMD-8
\begin{center}
\Large
\"Ubungen zur\\
Einf\"uhrung in die Theoretische Informatik III\\
SS 1999
\end{center}
\begin{enumerate}

\item
Aus dem Logik-Teil der Theorie-Vorlesung kennen Sie
den Formalismus der Aussagenlogik (wenn nicht, w\"are es an der Zeit,
sich das einmal anzusehen). Was ist der Zusammenhang zwischen
aussagenlogischen Formeln, logischen Schaltkreisen, und Booleschen
Funktionen? \"Ubersetzen Sie aussagenlogische Fragestellungen
in die Sprache der Schaltkreise.

\item
Eine Menge $\Omega$ von Booleschen Funktionen ist \textit{funktional vollst\"andig},
wenn sich \underline{jede} Boolesche Funktion (beliebiger Stellenzahl) 
mittels eines Schaltkreises \"uber der Basis $\Omega$ darstellen l\"asst.
\begin{enumerate}
\item
Zeigen Sie, dass die Basen
$\Omega_{\{\neg,\vee\}} = \{\text{\textsc{not}, \textsc{or}}\}$ 
und
$\Omega_{\{\neg,\wedge\}} = \{\text{\textsc{not}, \textsc{and}}\}$ 
vollst\"andig sind.
\item
Zeigen Sie, dass das \textsc{nand}-Gatter 
alleine eine funktional-vollst\"andige Basis bildet.
[N.B. \textsc{nand}(x,y) = \textsc{not} (x \textsc{and} y)]
\item
Zeigen Sie, dass die Basis $\Omega = \{\text{\textsc{and}, \textsc{or}}\}$
nicht funktional-vollst\"andig ist.
\item
Ist die Implikation 
$\text{\textsc{Impl}}(x,y) = (\overline{x} \text{ \textsc{or} } y)$
funktional vollst\"andig? Ist die Implikation assoziativ?

\end{enumerate}

\item
Beweisen Sie die Gleichheiten (f\"ur Boolesche Funktionen):
\begin{eqnarray*}
xy \vee \overline{x} z \vee yz &=& xy \vee \overline{x}z\\
(x\vee y)(\overline{x} \vee z)(y \vee z) &=& (x \vee y)(\overline{x}\vee z)
\end{eqnarray*}
(Hier ist, wie meist \"ublich, das Zeichen f\"ur die Konjunktion
($\wedge$, ``Multiplikation'', ``$\cdot$'', \textsc{And}) unterdr\"uckt, 
mit der Massgabe,
dass die Konjunktion st\"arker bindet als die Disjunktion 
($\vee$, ``Addition'', ``$+$'', \textsc{Or}).

\item
Zeigen Sie, dass sich jede Boolesche Funktion
$f\,:\,\mathcal{B}^n \rightarrow \mathcal{B}$ in der Form
\[
f(x_1,\ldots,x_n)= 
\left(
x_1 \wedge f(1,x_2, \ldots,x_n) 
\right)
\vee
\left(
\overline
{x_1} \wedge
f(0,x_2,\ldots,x_n) 
\right)
\]
(genannt: \textsc{Shannon}-Zerlegung)
darstellen l\"asst.\\
Aus der Aussagenlogik kennt man das sog. Dualit\"atsprinzip. 
Was besagt dies? Was erh\"alt man aus der \textsc{Shannon}-Zerlegung
mittels Dualit\"at?

\begin{enumerate}
\item
Verwenden Sie \textsc{Shannon}-Zerlegung, um die 
\textsc{DNF} der Funktion 
$f(x,y,z) = x \overline{y} \vee y z$
zu berechnen.\\
\item
Zeigen Sie, dass f\"ur einstellige Boolesche Funktionen $f$
die folgenden \\
Gleichungen gelten:
\begin{eqnarray*}
f(x \vee y) \cdot f(\overline{x} \vee y) &=& f(1) \cdot f(y)\\
f(x \vee y) \vee f(xy) &=& f(x) \vee f(y) \\
f(\overline{x} \vee \overline{y}) \vee f(xy)&=&
f(0) \vee f(1)
\end{eqnarray*}
Gilt auch
\[
f(f(x)) = f(0)\cdot f(1) \vee (x [f(0) \vee f(1)])~~\text{?}
\]


\end{enumerate}


\item
Die Menge $\mathcal{B}^n$ wird auf folgende Weise (partiell)
geordnet:
\[
\mathbf{c} = (c_1 ,\ldots,c_n) \leq_n \mathbf{d} = (d_1, \ldots,d_n)
~\Leftrightarrow~
\forall i (1 \leq i \leq n)\,:\, c_i \leq _1 d_i
\]
wobei $\leq_1$ die Ordnung auf $\mathcal{B}$ ist, f\"ur die
$0 \leq 1$ gilt.\\
 M.a.W. $\leq_n$ ist die ``Produktordnung'' auf $\mathcal{B}^n$.
\begin{enumerate}
\item
Zeichnen Sie f\"ur $n=2,3,4,\ldots$ $\mathcal{B}^n$ als
geordnete Menge und machen Sie sich den Zusammenhang mit der 
Algebra der Teilmengen einer $n$-elementigen Menge klar.
\item
Eine Boolesche Funktion 
$f\,:\,\mathcal{B}^n  \rightarrow \mathcal{B}$
heisst \textit{monoton}, wenn gilt:
\[
\forall \mathbf{c,d} \in \mathcal{B}^n ~:~
\mathbf{c} \leq_n \mathbf{d}~\Rightarrow~
f(\mathbf{c}) \leq_1 f(\mathbf{d})
\]
\begin{enumerate}
\item
\"Uberlegen Sie sich, welche der Ihnen bekannten Booleschen Funktionen
monoton sind und welche nicht. Versuchen Sie f\"ur $n=2,3,4,\ldots$
herauszufinden, wieviele monotone Boolesche Funktionen in $n$ Variablen es gibt.
(Vorsicht: das ist eine
 schwieriges Problem!). \\
K\"onnen Sie herausfinden,
warum es mindestens $2^{\binom{n}{\lfloor n/2 \rfloor}}$
monotone Boolesche Funktionen mit $n$ Variablen gibt?
\item
Zeigen Sie, dass jeder Schaltkreis \"uber der Basis
$\Omega_{\text{mon}} = \{\text{\textsc{and}, \textsc{or}}\}$ eine monotone
Boolesche Funktion berechnet.
\item
Zeigen Sie, dass sich jede monotone Boolesche Funktion mittels
eines Schaltkreises \"uber der Basis $\Omega_{\text{mon}}$ berechnen l\"asst.\\
Hinweis: \"uberlegen Sie sich eine f\"ur monotone Funktionen geeignete
\textsc{Shannon}-Zerlegung.
\end{enumerate}

\end{enumerate}
\end{enumerate}
\end{document}