%% Allgemeine Definitionen
\documentclass{article} %% Bestimmt die allgemeine Formatierung der Abgabe.
\usepackage{a4wide} %% Papierformat: A4.
\usepackage[utf8]{inputenc} %% Datei wird im UTF-8 Format geschrieben.
%% Unter Windows werden Dateien je nach Editor nicht in diesem Format
%% gespeichert und Umlaute werden dann nicht richtig erkannt.
%% Versucht in diesem Fall "utf8" auf "latin1" (ISO 8859-1) wechseln.
\usepackage[T1]{fontenc} %% Format der Zeichen im erstellten PDF.
\usepackage[ngerman]{babel} %% Regeln für automatische Worttrennung.
\usepackage{fancyhdr} %% Paket um einen Header auf jeder Seite zu erstellen.
\usepackage{lastpage} %% Wird für "Seite X von Y" im Header benötigt.
                      %% Damit das funktioniert, muss pdflatex zweimal
                      %% aufgerufen werden.
\usepackage{enumerate} %% Hiermit kann der Stil der Aufzählungen
                       %% verändert werden (siehe unten).

\usepackage{amssymb} %% Definitionen für mathematische Symbole.
\usepackage{amsmath} %% Definitionen für mathematische Symbole.

%% Linke Seite des Headers
\lhead{\course\\\semester\\Übungsblatt \homeworkNumber}
%% Rechte Seite des Headers
\rhead{\authorname\\Seite \thepage\ von \pageref{LastPage}}
%% Höhe des Headers
\usepackage[headheight=36pt]{geometry}
%% Seitenstil, der den Header verwendet.
\pagestyle{fancy}

\newcommand{\authorname}{A. Student}
\newcommand{\semester}{Frühjahrssemester 2014}
\newcommand{\course}{Theorie der Informatik (CS 206)}
\newcommand{\homeworkNumber}{1}


\begin{document}
\section{Aufgabe 1.1}

Atomare Aussagen: EsRegnet, EsIstKalt, DieSonneScheint,
BobHatLustAufEis, BobIsstEis.

%% Mit enumerate können Aufzählungen gemacht werden.
%% Die Standardeinstellung ist die Aufzählung zu nummerieren, wir
%% wollen aber die Einstellungen aus dem Aufgabenblatt übernehmen
%% und geben den Stil in eckigen Klammern an. Dazu haben wir oben das
%% Paket "enumerate" geladen.
\begin{enumerate}[(a)]
    %% Text zwischen zwei Dollarzeichen ist im sogenannten Mathemodus.
    %% In diesem Modus werden Formeln und Gleichungen gesetzt und viele
    %% mathematische Symbole funktionieren nur im Mathemodus.
    %% Im Mathemodus werden Zeichen anders gesetzt, zum Beispiel werden
    %% einzelne Buchstaben im Mathemodus als Variablen behandelt.
    %% Wenn wir "$EsRegnet$" schreiben, sieht das komisch aus, weil
    %% wir damit latex sagen es soll die Variablen "E", "s", "R", usw.
    %% hintereinanderschreiben (wie in einer Multiplikation).
    %% Wir verwenden daher den Befehl "\text{...}" um Text im Mathemodus
    %% wieder als normalen Text zu behandeln.
    \item $(\text{EsRegnet} \rightarrow \text{EsIstKalt})$
    \item $(\lnot\text{EsRegnet} \rightarrow (\lnot\text{EsIstKalt}
            \land \text{DieSonneScheint}))$
    \item $((\lnot\text{EsRegnet}\lor\text{DieSonneScheint})
            \rightarrow \text{BobHatLustAufEis})$
    \item $(\text{BobHatLustAufEis} \rightarrow \text{BobIsstEis})$
\end{enumerate}

\section{Aufgabe 1.2}
\begin{enumerate}[(a)]
    \item Da $\mathcal I(A) = 0$, gilt $\mathcal
      I\not\models A$ und damit mit der Semantik für Konjunktionen 
      auch $\mathcal I\not\models (A\land B)$. Daraus folgt, dass 
      $\mathcal I\models \lnot(A\land B)$ (*). Löst man die 
      Abkürzung der Implikation auf, erhält man $\phi = 
      (\lnot(A\land B)\lor C)$.  Aus der Semantik für 
      Disjunktionen folgt mit (*) direkt, dass $\mathcal I\models 
      \phi$. 

      Oder alternativ mit einem systematischeren Beweis:
      %% Text zwischen \begin{align*} und \end{align*} enthält mehrere
      %% Zeilen die durch "\\" getrennt werden und an dem Zeichen "&"
      %% ausgerichtet werden.
      %% Der Text in dieser Umgebung ist automatisch im Mathemodus, d.h.
      %% um Text richtig darzustellen, müssen wir wieder "\text{...}"
      %% verwenden.
      \begin{align*}
        \mathcal I\models((A\land B)\rightarrow C)
        &\text{ gdw.\ }\mathcal I\models(\lnot(A\land B)\lor C)\\
        &\text{ gdw.\ }\mathcal I\models\lnot(A\land B)
                        \text{ oder }\mathcal I\models C\\
        &\text{ gdw.\ }[\text{nicht }\mathcal I\models(A\land B)]
                        \text{ oder }\mathcal I\models C\\
        &\text{ gdw.\ }[\text{nicht } [\mathcal I\models A
                                \text{ und }\mathcal I\models B]]
                        \text{ oder }\mathcal I\models C\\
        &\text{ gdw.\ }[\text{nicht } [\mathcal I(A) = 1
                                \text{ und }\mathcal I(B) = 1]]
                        \text{ oder }\mathcal I\models C\\
        &\text{ gdw.\ }[\text{nicht 
                         \textless falsche Aussage\textgreater}]
                         \text{ oder }\mathcal I\models C\\
        &\text{ gdw.\ }\text{\textless wahre Aussage\textgreater\
                        oder }\mathcal I\models C\\
        &\text{ gdw.\ }\text{\textless wahre Aussage\textgreater}
      \end{align*}

    \item Löst man die Abkürzung des Bikonditionals auf, erhält man 
      %% Eine andere Möglichkeit in den Mathemodus zu wechseln ist "\[...\]".
      %% Damit wir eine einzelne Zeile in den Mathemodus gesetzt und kommt
      %% in einen eigenen Absatz. Das macht man für wichtigere Formeln,
      %% die man vom normalen Text etwas abheben will.
      \[\phi = ((A\rightarrow (B\lor C)) \land ((B\lor C)\rightarrow A)).\]
      Wir betrachten $\phi_1 = (A\rightarrow (B\lor C))$ und
      $\phi_2 = ((B\lor C)\rightarrow A)$ zunächst getrennt.
    
      Wir beginnen mit $\phi_1$. Löst man die Implikation auf, 
      ergibt sich $\phi_1 = (\lnot A\lor (B\lor C))$. Da
      $\mathcal I(C) = 1$, gilt $\mathcal I\models C$ und damit wegen 
      der Semantik für Disjunktionen auch $\mathcal I\models (B\lor C)$. 
      Das ergibt (wiederum mit der Semantik für Disjunktionen) 
      $\mathcal I\models\phi_1$ (*).
    
      Löst man die Implikation in $\phi_2$ auf, erhält man $\phi_2 = (\lnot(B\lor
      C)\lor A)$. Da $\mathcal I(A) = 1$, gilt $\mathcal I\models A$, was mit der
      Semantik für Disjunktionen direkt ergibt, dass $\mathcal I\models \phi_2$ (**).
      
      Die Zwischenergebnis (*) und (**) ergeben mit der Semantik für Konjunktionen,
      dass $\mathcal I\models \phi$.
    
      Natürlich könnten wir auch hier wieder alternativ einen systematischen Beweis
      machen, das würde allerdings recht unübersichtlich.
\end{enumerate}

\section{Aufgabe 1.3}
\begin{enumerate}[(a)]
  \item Wahrheitstafel für $\phi$:

    \begin{tabular}{rr|ccc}
    $\mathcal I(A)$ & $\mathcal I(B)$ & $\mathcal I\models (A\rightarrow B)$ &
    $\mathcal I\models (B\rightarrow A)$ 
    &$\mathcal I\models ((A\rightarrow B) \lor (B\rightarrow A))$\\\hline
    $0$ & $0$ & Ja & Ja & Ja\\
    $0$ & $1$ & Ja & Nein & Ja\\
    $1$ & $0$ & Nein & Ja & Ja\\
    $1$ & $1$ & Ja & Ja & Ja
    \end{tabular}
    \bigskip

    Da das Ergebnis für alle Interpretation "`Ja"' ist, ist die Formel $\phi$ eine
    Tautologie und damit auch erfüllbar. Sie ist aus dem gleichen Grund nicht
    falsifizierbar und damit auch nicht unerfüllbar.
  \item Die Formel enthält $4$ atomare Aussagen. Daher hätte die Tafel $2^4=16$
    Zeilen (zuzüglich der einen Kopfzeile).
  \item Die Formel ist erfüllbar, was man zum Beispiel aus der Interpretation
    $\mathcal I = \{A\mapsto 1,B\mapsto 0, C\mapsto 1, D\mapsto 1\}$ erkennen
    kann: Da $\mathcal I(A) = 1$, gilt $\mathcal I\models A$ und mit der Semantik
    für Disjunktionen $\mathcal I\models (A\lor B)$. Mit $\mathcal I(C)=1$ kann
    man analog argumentieren, dass $\mathcal I\models (C\lor D)$. Zusammen folgt
    mit der Semantik für Konjunktionen, dass $\mathcal I\models\psi$.

    Aus der Erfüllbarkeit können wir direkt schliessen, dass $\psi$ nicht
    unerfüllbar ist.

    Die Formel $\psi$ ist ausserdem falsifizierbar, was wir mit der
    Interpretation $\mathcal I' = \{A\mapsto 0,B\mapsto 0, C\mapsto 1, D\mapsto 1\}$
    zeigen: Da $\mathcal I'(A)=0$ und $\mathcal I'(B) = 0$, gilt $\mathcal
    I'\not\models (A\lor B)$. Damit kann $\mathcal I'$ auch kein Modell der
    Konjunktion $\psi$ sein.

    Da $\psi$ falsifizierbar ist, kann die Formel keine Tautologie sein.
\end{enumerate}

\end{document}
