%blatt8
\documentclass[A4,11pt]{article}

\usepackage{lmodern}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}


\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\pagestyle{empty}

\usepackage{fancyhdr}

\pagestyle{fancy}
\fancyhf{}
\theoremstyle{definition}
\newtheorem{ubung}{Aufgabe}
\newtheorem{uebung}{Aufgabe}

\newcommand{\bN}{\mathbb{N}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\such}{\; : \;}



\begin{document}

\lhead{Logik f\"ur Studierende der Informatik\\
WS 2022/23
}

\rhead{Dozentin: Prof. Dr. Heike Mildenberger\\\
Assistent: M.Sc. Christian Br\"auninger}


$\,$\\
\\
\\
\cfoot{Abgabe per Ilias bis Mittwoch 14.12.2022, 10 Uhr.}



\begin{center}
 \textbf{BLATT 8}\\
 (7.12.2022)
\end{center}



\begin{ubung}[4 Punkte]~\\
Zur Erinnerung: Ein Literal ist eine Aussagenvariable oder eine negierte Aussagenvariable. Seien nun $B_1,\dots, B_n$ solche Literale.~\\
Zeigen Sie die Aussage aus dem Beweis von Korollar 2.28, dass es f\"ur die aussagenlogische Formel
\(\varphi= B_1\vee \dots \vee B_n \)
genau dann eine erf\"ullende Wahrheitsbelegung $v$ gibt (d.h. $\bar{v}(\varphi)=W$), wenn es f\"ur die Formel
\[(B_1 \vee B_2 \vee C_1) \wedge (\neg C_1 \vee B_3 \vee C_2) \wedge \dots \wedge (\neg C_{n-4} \vee B_{n-2} \vee C_{n-3}) \wedge (\neg C_{n-3} \vee B_{n-1} \vee B_n) \]
eine erf\"ullende Wahrheitsbelegung gibt.
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Ein gerichteter Graph \( G= (V,E) \) hei\ss t \emph{zusammenh\"angend}, wenn es
f\"ur alle Knoten \( s,t \in V \) einen Pfad in \( G \) von \( s \) nach \( t \) gibt. Ist
\[
\mathsf{CONNECTED} = \{ G \mid  G \text{ ist ein zusammenh\"angender Graph} \}
\]
in \( P \)?
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Beschreiben Sie einen Algorithmus, der f\"ur jede aussagenlogische
Formel \(\varphi \) eine Formel \( \psi \) in DNF findet, die \"aquivalent zu \(\varphi\) ist. K\"onnen Sie die Laufzeitkomplexit\"at Ihres Algorithmus in Abh\"angigkeit zu der Anzahl der Aussagenvariablen in \(\varphi \) absch\"atzen?
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Angenommen es gilt $P\neq NP$, kann dann ein Algorithmus wie in Aufgabe 3 auch polynomiale Laufzeit haben?
\end{ubung}


\end{document}