%blatt7
\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 7.12.2022, 10 Uhr.}



\begin{center}
 \textbf{BLATT 7}\\
 (30.11.2022)
\end{center}



\begin{ubung}[4 Punkte] ~\\
Entscheiden Sie (ohne Beweis), ob die folgenden Aussagen wahr oder falsch sind.
\begin{center}
\begin{tabular}{|p{5cm}|c|c|} \hline
   & Wahr  & Falsch \\\hline
$n^4 = O(n^5)$  &  &  \\\hline
$5n+6n^2+200n^3=O(n^3) $ &  &  \\\hline
$3^n=o(n^3)$  &  &  \\\hline
$n^2=O(n \log(n))$ &  &  \\\hline
$O(f)+O(g)= O(f+g)$  &  &  \\\hline
$O(f)\cdot O(g) = O(f\cdot g)$  &  &  \\\hline
Falls $f=O(g)$ und $g=O(h)$, dann auch $f=O(h)$   & \; &  \\\hline
Es ist $f\neq O(g)$ genau dann, wenn $g=o(f)$  &  &  \\\hline
\end{tabular}
\end{center}

\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Es seien $G=(V,E)$ ein ungerichteter Graph mit Knotenmenge $V=\{v_0,\dots,v_n\}$ und $c: V\to \{0,\dots, m\}$ eine F\"arbung der Knoten in $m+1$ Farben f\"ur zwei nat\"urliche Zahlen $n,m\in \bN$. (Die Gleichheit $c(v_i)=j$ besagt dabei, dass der Knoten $v_i$ gerade die Farbe $j$ besitzt.)~\\ Geben Sie eine aussagenlogische Formel an, die besagt, dass zwei im Graphen $G$ benachbarte Knoten nie dieselbe Farbe haben. Definieren Sie dazu Aussagenvariablen die besagen, dass zwei Knoten benachbart sind bzw. dieselbe Farbe haben.
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Eine nat\"urliche Zahl ist eine Primzahl, wenn sie genau zwei Teiler besitzt. (Inbesondere ist $1$ keine Primzahl). F\"ur alle $n\in\bN^+=\bN\setminus\{0\}$ definieren einen Graphen $G_n=(V_n,E_n)$ durch
\begin{align*}
&V_n=\{m\in \bN^+ \such m \text{ teilt } n\}\quad\text{und}\\
&E_n=\{(k,m)\such k \text{ teilt } m\text{ und }\frac{m}{k} \text{ ist eine Primzahl}\}.
\end{align*}
\begin{itemize}
\item[a)] Zeichnen Sie $G_{12}$ und $G_{16}$.
\item[b)] Geben Sie eine hinreichende und notwendige Bedingung f\"ur $n\in \bN^+$ an, damit $G_n$  die folgende Eigenschaft hat:~\\
F\"ur je zwei Knoten in $G_n$ gibt es einen \emph{eindeutigen} Pfad in $G_n$ zwischen diesen Knoten.
\item[c)] Seien nun $m,n\in \bN^+$ und $m$ teile $n$. Ist dann $G_m$ immer ein Teilgraph von $G_n$, d.h. ist immer $V_m\subseteq V_n$ und $E_m\subseteq E_n$?
\end{itemize}

\end{ubung}

\begin{flushright}
\textbf{R\"uckseite beachten!}
\end{flushright}



\newpage~\\


\begin{ubung}[4 Punkte]~\\
Es seien zwei Zahlen $k$, $\ell$ in bin\"arer Notation als Eingabe gegeben, so dass die L\"ange $n$ der Eingabe $(k,\ell)$ von der Gr\"o\ss enordnung $n=O(\log_2(k) + \log_2(\ell)) $ ist. Gibt es eine Turingmaschine von in $n$ polynomialer Zeitklasse, die $k + \ell$ berechnet? Skizzieren Sie so eine Maschine oder begr\"unden Sie, warum es keine solche Maschine gibt.

\end{ubung}


\end{document}