\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{verbatim}

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 9. November 2015 bis 12 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\B}{\mathbb{B}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Informatik A}\hfill WiSe 2015/16 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Umgang mit Booleschen Termen}{10 Punkte}

\begin{enumerate}
  \item 
     \"Uberpr\"ufen Sie, ob der folgende erweiterte Boolesche Term
     eine Tautologie ist. Verwenden Sie keine Wertetabelle!
     \[
       [(a \vee b ) \wedge (a \Rightarrow c) \wedge (b \Rightarrow c)]
         \Rightarrow c
     \]
  \item Betrachten Sie den folgenden erweiterten Booleschen Ausdruck:
     \[
       a \Leftrightarrow b \vee \neg c \wedge b.
     \]
     Geben Sie eine vollst\"andige Klammerung und eine
     Baumdarstellung f\"ur diesen Ausdruck an ($\Leftrightarrow$
     bindet schw\"acher als alle anderen Junktoren).
     Bilden Sie dann die kanonische DNF und die kanonische KNF.
  \item
    Finden Sie heraus, wie Boolesche Terme in \emph{Haskell}
    dargestellt werden. Wie werden Junktoren repr\"asentiert?
    Was entspricht den Elementaraussagen \emph{true} und \emph{false}?
\end{enumerate}

\AUFGABE{Funktional vollst\"andige Signaturen}{10 Punkte}

\begin{enumerate}
\item
In der Vorlesung wurde erw\"ahnt, dass sowohl der NAND-Operator 
$a \uparrow b = \neg (a \wedge b)$  als auch der NOR-Operator
$a \downarrow b = \neg (a \vee b)$ funktional vollst\"andig ist. 
Stellen Sie den NOR-Operator 
mittels des NAND-Operators dar und umgekehrt.
\item Zeigen Sie, dass $\{\neg, \Rightarrow\}$ funktional 
vollst\"andig ist.
\item Zeigen Sie, dass $\{\Leftrightarrow\}$
 nicht funktional vollst\"andig ist.
\item Es ist bekannt, dass $\{\oplus, \neg\}$ nicht funktional
vollst\"andig ist. Folgern Sie daraus, dass dann auch 
$\{\oplus, \neg, \Leftrightarrow, \text{true}\}$ nicht 
funktional vollst\"andig ist.
\end{enumerate}

\AUFGABE{XOR}{10 Punkte}

\begin{enumerate}
\item 
Beweisen Sie: Die Antivalenz $a \oplus b$ ist kommutativ
und assoziativ. Ist sie idempotent?
\item Betrachten Sie die $n$-stellige \emph{Parit\"atsfunktion}
$f_n: \mathbb{B}^n \rightarrow \mathbb{B}$ definiert durch
$f_n(x_1, x_2, \dots, x_n) = x_1 \oplus x_2 \oplus \dots \oplus x_n$.
Stellen Sie eine Wertetabelle f\"ur $f_3$ und $f_4$ auf.
Beschreiben Sie mit einem Satz, was $f_n$ tut.
\item
Geben Sie die kanonische DNF und die kanonische KNF f\"ur $f_4$ an.
Wie viele Minterme bzw. Maxterme kommen in der
kanonischen KNF bzw. DNF f\"ur $f_n$ vor?
K\"onnen Sie eine k\"urzere DNF finden?
\item(freiwillig, 5 Zusatzpunkte) 
Zeigen Sie, dass $\{\oplus, \neg\}$ nicht funktional vollst\"andig
ist.

\emph{Hinweis}:
Benutzen Sie Assoziativit\"at und Kommutativit\"at von $\oplus$.
\end{enumerate}
\end{description}
\end{document}
