\documentclass[10pt,a4paper]{scrartcl}

\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}
\usepackage{scrlayer-scrpage}
\usepackage{lastpage}
\usepackage{stmaryrd}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage[intlimits]{mathtools}
\usepackage{paralist}
\usepackage{ebproof}
\usepackage{xspace}


\setcounter{secnumdepth}{0}
\DeclareMathOperator{\Res}{Res}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\AL}{\ensuremath{\mathrm{AL}}\xspace}
\newcommand{\AVAR}{\textsc{AVar}}
\newcommand*{\eval}[2]{\ensuremath{\left\llbracket #1 \right\rrbracket}^{#2}}
\newcommand{\LRarrow}{\ensuremath{\Leftrightarrow}}

\cfoot{\thepage \hspace{1pt} / \pageref*{LastPage}}

\begin{document}

\begin{center}
\Huge 1. Schriftliche Leistungskontrolle Logik: Gedächnisprotokoll\\[1em]
\large WS 18/19
\end{center}

\section{Vorbemerkungen}

Die Aufgabenstellungen sind durch mich z.T. paraphrasiert. Ich habe mich bemüht,
dass die Aufgabenstellungen soweit stimmen, kann aber nicht garantieren, dass
sie fehlerfrei sind. Mir entfallene Details habe ich entsprechend gekenntzeichnet.\\
Es sind keine Hilfsmittel zugelassen gewesen (keine Formelsammlung, kein
Skript, etc.; es wurden auch nur die Aufgabenstellungen ausgeteilt, keine
weiteren Hilfestellungen).\\
Die Bearbeitsungszeit betrug 60 Minuten + 15 Minuten Lesezeit (insgesammt 75
Minuten, in denen geschrieben werden durften). Ab einer Punktzahl von 52 Punkten
(von 66 Gesamtpunkten) hat man die volle Portfoliepunkte für die
Prüfungsleistung bekommen.

\section{Aufgabe 1}
\hfill \(4 + 4 + 8 = 16\) Punkte

\begin{enumerate}[(i)]
\item Seien \(\Phi \subseteq \AL\), \(\varphi \in \AL\).

Geben Sie die Definition von
\begin{enumerate}[a)]
  \item \(\Phi \models \varphi\) und
  \item "`\(\varphi\) ist erfüllbar"'
\end{enumerate}
an. Verwenden Sie lediglich die Begriffe \textit{Formel} und \textit{Belegung},
sowie die Auswertungsfunktion \(\eval{\cdot}{\cdot}\).
\item Sei \(\varphi \in \AL\).

Erklären Sie den Kontext, in dem die Aussage "`\(\varphi\) ist erfüllt"' getätigt
werden kann. Erklären sie den Unterschied zu der Aussage "`\(\varphi\) ist
erfüllbar"'.
\item Geben Sie für die folgenden Aussagenpaare an, ob im Allgemeinen aus der
einen Aussage die jeweilige andere folgert. \textit{(ja/nein)}\\
Seien \(\varphi, \psi \in \AL, \Phi \subseteq \AL, \beta\) passende Belegungen,
beliebig. \textit{(für die jeweiligen Aussagenpaare einzelnd)}

\begin{tabular}{|c|c|c|c|}
\hline
\(A_i\) 												&\(B_i\) 							&\(A_i\) impliziert \(B_i\) &\(B_i\) impliziert \(A_i\)\\
\hline
\(\beta \models \varphi\) und \(\beta \models \psi\)	&\(\varphi \models \psi\)			&							&\\
\hline
\textit{Ist mir leider entfallen.}						&\textit{Ist mir leider entfallen.}	&							&\\
\hline
\(\beta \models \varphi \LRarrow \beta \models \psi\)	&\(\varphi \equiv \psi\)			&							&\\
\hline
\(\Phi\) ist unerfüllbar								&\(\Phi \models \varphi\)			&							&\\
\hline
\end{tabular}
\end{enumerate}

\newpage

\section{Aufgabe 2}
\hfill \(4 + 6 + 6 = 16\) Punkte

\begin{enumerate}[(i)]
\item Erklären Sie, was es bedeutet, dass der Resolutionskalkül
\textit{vollständig} und \textit{korrekt} ist.
\item Sei \(\mathcal{C}\) eine Klauselmenge. Es gilt \(\Res(C_1, C_2) = C\).
Beweisen Sie \(\{C_1, C_2\} \models C\).
\item Beweisen Sie per Resolution, dass \(\varphi\) unerfüllbar ist.\\
\textit{\(\varphi\) war eine längere Formel (mit digitaler Schrift eine Zeile
füllend), welche nicht in KNF war und somit erst mithilfe von logischen
Äquivalenzen in KNF umgewandelt werden musste um die Resolution durchzuführen.}
\end{enumerate}

\section{Aufgabe 3}
\hfill \(2 + 15 = 17\) Punkte

Sei \(n \in \N\). Für alle \(i \in \{1,\ldots,n+1\}, t \in \{1,\ldots,n\}\) sind
\(P_{i,t} \in \AVAR\) aussagenlogische Variablen.

\[\varphi_n := 
\bigwedge_{1\leq i \leq n+1} \left(\bigvee_{1\leq t \leq n} P_{i,t}\right)\]

\[\psi_n := 
\bigwedge_{1\leq t \leq n} \left(\bigvee_{1\leq i < j \leq n+1} P_{i,t} \vee P_{j,t}\right)\]

\begin{enumerate}[(i)]
\item Geben Sie \(\varphi_2, \psi_2\), sowie eine Belegung, welche zugleich
\(\varphi_2\) und \(\psi_2\) erfüllt, ohne Begründung an.
\item Beweisen Sie \(\varphi_n \models \psi_n\)
\end{enumerate}

\section{Aufgabe 4}
\hfill \(1 + 5 + 3 + 5 + 3 = 17\) Punkte

Ein Graph \(G\) heißt k-färbbar, wenn eine Funktion \(c: V(G) \to
{1,\ldots,k}\) existiert, sodass \(c(u) \neq c(v)\) für alle \(\{u,v\} \in
E(G)\).\\
Sei \(G\) unendlich.

\begin{enumerate}[(i)]
\item Zeigen Sie, dass wenn \(G\) 4-färbbar ist, jeder endliche Teilgraph von
\(G\) 4-färbbar ist.
\item Geben Sie eine Formelmenge \(\Phi_G\) ohne Begründung an, die genau dann
erfüllbar ist, wenn \(G\) 4-färbbar ist.
\item Zeigen Sie, wie Sie aus \(\Phi_G\) eine 4-Färbung von \(G\) konstruieren
können und umgekehrt.
\item Zeigen Sie, dass wenn jeder endliche Teilgraph von \(G\) 4-färbbar ist,
jede endliche Teilmenge von \(\Phi_G\) erfüllbar ist.
\item Folgern Sie, dass wenn jeder endliche Teilgraph von \(G\) 4-färbbar ist,
auch \(G\) 4-färbbar ist.
\end{enumerate}

\end{document}