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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 17. 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{\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{Resolutionskalk\"ul I}{10 Punkte}
\begin{enumerate}
\item Man teste mit dem Resolutionskalk\"ul, ob die folgende Boolesche Formel eine 
Tautologie ist.
\[
t_1 = \neg x \vee (w \wedge \neg x) \vee (x \wedge \neg w) \vee 
  (y \wedge z \wedge x) \vee (x \wedge \neg y \wedge z) \vee (w \wedge \neg z \wedge x).
\]
\item Ist der folgende Term erf\"ullbar? Verwenden Sie den Resolutionskalk\"ul!
\[
t_2 = (x_1 \vee x_2 ) \wedge (x_1 \vee \neg x_2 \vee x_3 ) \wedge (\neg x_1 \vee 
  \neg x_2 ) \wedge (\neg x_1 \vee x_2 \vee x_3 ) \wedge \neg x_3.
\]
\item Ist der folgende Term eine Tautologie? Verwenden Sie den Resolutionskalk\"ul!
\[
t_3 = (x_1 \wedge x_2 \wedge x_3) \vee (x_1 \wedge \neg x_3 ) \vee (\neg x_1 
\wedge x_3 ) \vee \neg x_2.
\]
\item Zeigen Sie mittels Resolutionsmethode, dass $x_1 \wedge x_2 \wedge x_3$ eine Folgerung ist aus der
Klauselmenge
\[
t_4 = \{\{\neg x_1 , x_2\}, \{\neg x_2 , x_3\}, \{x_1, \neg x_3\}, 
\{x_1, x_2 , x_3\}\}
\]
ist.
\end{enumerate}

\AUFGABE{Resolutionskalk\"ul II}{10 Punkte}

In dieser Aufgaben fixieren wir die Variablenmenge
$V_n = \{x_1, \dots, x_n\}$.

\begin{enumerate}
\item   Wie viele m\"ogliche Klauseln kann es f\"ur $V_n$ 
   geben?
\item
  Sei nun $n \geq 3$.
  Geben Sie ein Beispiel f\"ur eine Klauselmenge  \"uber $V_n$ mit
  Klauseln der L\"ange $3$, f\"ur die der Resolutionskalk\"ul eine
  Klausel der L\"ange $n$ erzeugen kann. Begr\"unden Sie Ihre Antwort.
\item
  Was passiert, wenn alle Klauseln die L\"ange $2$ haben?
  Wie viele Klauseln k\"onnen dann bei Anwendung des
  Resolutionskalk\"uls maximal entstehen? Was folgt daraus
  \"uber die Anzahl der Resolutionsschritte?
\end{enumerate}

\newpage 
\AUFGABE{Quantoren}{10 Punkte}

\begin{enumerate}
\item Schreiben Sie die folgenden Formeln in Negationsnormalform, das hei\ss{}t, die 
verwendeten Negationen beziehen sich nur auf atomare Teilformeln und es werden
au\ss{}er den Quantoren nur die Junktoren $\neg$, $\wedge$ , $\vee$ benutzt. 
Au\ss{}erdem soll die Formel in Pr\"anexform sein, also alle Quantoren vorne stehen.
\begin{enumerate}
\item $\neg \forall x\,\, \exists y\,\, (P (x, y) \wedge Q(x, y) \wedge R(x, y))$.
\item $\neg \forall x \,\,(\exists y \,\,(P (x, y) \Rightarrow Q(x, y)) \wedge \exists z\,\, R(x, z))$.
\end{enumerate}
\item Wir betrachten die folgende Aussageform: $Q(x, y, z) : x \cdot y = z$.
Bestimmen Sie die Wahrheitswerte der folgenden Aussagen und begr\"unden Sie
Ihre Antworten:
\begin{enumerate}
\item $\forall z \in \Z\,\, \exists x \in \Z \,\,\forall y \in \Z : Q(x, y, z)$.
\item $\exists x \in \Q \,\,\forall z \in \Q \,\, \exists y \in  \Q : Q(x, y, z)$.
\end{enumerate}
\end{enumerate}

\end{description}
\end{document}
