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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{am 24. 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}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}



\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{Hornformeln}{10 Punkte}

\begin{enumerate}
\item Wenden Sie den Markierungsalgorithmus auf die folgende Hornformel an:
  \[
    \{\{\neg a, \neg b, \neg d\}, \{\neg e\}, \{\neg c, a\}, \{c\}, \{b\}, \{\neg g, d\}, \{g\}\}.
   \]
\item Angenommen, uns stehen Apparate zur Verf\"ugung, um folgende
chemischen Reaktionen durchzuf\"uhren:
\begin{align*}
  \text{Mg}\text{O} + \text{H}_2 & \rightarrow \text{Mg} + \text{H}_2\text{O},\\
  \text{C} + \text{O}_2 & \rightarrow \text{C}\text{O}_2,\\
  \text{H}_2\text{O} + \text{C}\text{O}_2 & \rightarrow \text{H}_2\text{C}\text{O}_3.
\end{align*}
Ferner sind in unserem Labor folgende Grundstoffe vorhanden:
$\text{Mg}\text{O}$, $\text{H}_2$, $\text{O}_2$ und $\text{C}$.
Man beweise mit Hilfe des Markierungsalgorithmus, dass es unter diesen Umst\"anden m\"oglich ist,
$\text{H}_2\text{C}\text{O}_3$ herzustellen.

\item 
  Diskutieren Sie den Zusammenhang zwischen
  dem Markierungsalgorithmus und dem Resolutionskalk\"ul.
\end{enumerate}

\AUFGABE{Vollst\"andige Induktion I}{10 Punkte}

Beweisen Sie mit vollst\"andiger Induktion.
\begin{enumerate}
\item 
F\"ur $a, r \in \R$ mit $r \neq 1$ und f\"ur alle
$n \in \N$ gilt:
\[
  \sum_{i=0}^n ar^i = \frac{ar^{n+1}-a}{r-1}.
\]
\item
Jede Menge mit $n$ Elementen besitzt genau $2^n$ Teilmengen,
f\"ur $n \in \N$.
\end{enumerate}

\AUFGABE{Vollst\"andige Induktion II}{10 Punkte}

\begin{enumerate}
\item
Beweisen Sie mit vollst\"andiger Induktion, dass
f\"ur eine aufsteigend sortierte Folge $s = a_1 a_2 \dots a_{2^n}$
von reellen Zahlen und eine Zahl $b$  h\"ochstens $n + 1$ Abfragen der Form 
$b \leq a_i$ ausreichen, um zu bestimmen, ob
$b$ ein Glied der Folge ist.

\emph{Achtung}: Eine Abfrage hat drei m\"ogliche Antworten:
$a_i < b$, $a_i = b$ und $a_i > b$.

\item
Beweisen Sie mit vollst\"andiger Induktion
\"uber den Formelrang, dass man jeden Booleschen Term 
\"uber der Standardsignatur semantisch \"aquivalent 
in DNF und in KNF schreiben kann.
\end{enumerate}

\end{description}
\end{document}
