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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 2. 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{Boolesche Terme}{10 Punkte}

\begin{enumerate}
  \item Zeichnen Sie die Baumdarstellung f\"ur die folgenden Booleschen
    Terme. Bestimmen Sie auch den Rang und die Variablenmenge mit Hilfe
    des Baumes.
    \begin{enumerate}
       \item $((p \vee q ) \wedge ((\neg r \vee p) \wedge \neg s))$ und
       \item $\neg \neg ((a \wedge (b \vee b)) \wedge (a \wedge \neg \neg a))$.
     \end{enumerate}
  \item Zeigen Sie jeweils durch Anwendung Boolescher Gesetze und durch 
  eine Wahrheitstabelle. Begr\"unden Sie jeden einzelnen Schritt.
  \begin{enumerate}
    \item $\neg (x_1 \vee ( \neg x_1 \wedge x_2)) \equiv \neg x_1 \wedge \neg x_2$ und
    \item $\neg \neg ((a \wedge (b \vee b)) \wedge (a \wedge \neg \neg a)) \equiv a \wedge b$.
\end{enumerate}
\end{enumerate}

\AUFGABE{Verallgemeinerte Boolesche Terme}{10 Punkte}

\begin{enumerate}

\item Erweitern Sie die Definition  Boolescher Terme aus der Vorlesung,
so dass nun auch die Junktoren $\Rightarrow$ und
$\Leftrightarrow$ zugelassen sind.

\item Erweitern Sie die Definitionen von $\text{rg}(t)$, $V(t)$ und
  $I_\beta(t)$ f\"ur Ihre verallgemeinerten Booleschen Terme.

\item
  Beweisen Sie: F\"ur alle verallgemeinerten Booleschen Terme $s$ und $t$ gilt:
    \begin{enumerate}
      \item  $s \Rightarrow t \equiv \neg s \vee t$, 
      \item  $s \Rightarrow t \equiv \neg t \Rightarrow \neg s$ und
      \item  $s \Leftrightarrow t \equiv (s \wedge t) \vee 
      (\neg s \wedge \neg t)$.
    \end{enumerate}
\end{enumerate}

\AUFGABE{Boolesche Funktionen}{10 Punkte}

Wir betrachten die $n$-stellige \emph{Majorit\"atsfunktion} $f_n : \B^n \rightarrow \B$, 
die genau dann den  Wert $1$ annimmt, falls mindestens die 
H\"alfte der Eingaben aus Einsen besteht. 
\begin{enumerate}
\item Geben Sie Wertetabellen f\"ur $f_3$ und $f_4$ an.
\item  Leiten Sie aus den Wertetabellen die kanonischen disjunktiven Normalformen
$\text{dnf}(f_3)$ und $\text{dnf}(f_4)$ ab.
Geben sie auch die kanonische konjunktive Normalform $\text{knf}(f_3)$ an.
\item
Vereinfachen Sie $\text{dnf}(f_3)$ entsprechend der Booleschen Gesetze. 
\end{enumerate}

\end{description}
\end{document}
