%blatt10
\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{multicol}

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

\pagestyle{empty}

\usepackage{fancyhdr}

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

\newcommand{\fA}{\mathfrak{A}}
\newcommand{\fB}{\mathfrak{B}}
\newcommand{\fN}{\mathfrak{N}}
\newcommand{\lra}{\leftrightarrow}
\newcommand{\cL}{\mathcal{L}}
\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 11.1.2023, 10 Uhr.}



\begin{center}
 \textbf{BLATT 10}\\
 (21.12.2022)
\end{center}


\begin{ubung}[4 Punkte]~\\
\begin{itemize}
\item[a)] Geben Sie jeweils eine $\cL(\emptyset)$-Aussage $\varphi$ an, so dass $\fA\models\varphi$ bzw. $\fA\not\models\varphi$ f\"ur jede Symbolmenge $\tau$ und jede $\cL(\tau)$-Struktur $\fA$ gilt.
\item[b)] Wir nehmen an, es g\"abe eine Struktur $\fB$ mit leerem Universum. Haben ihre Formeln aus Teil a) immer noch dieselbe Eigenschaft bez\"uglich $\fB$? Finden Sie eine $\cL(\emptyset)$-Aussage, die von leeren Strukturen erf\"ullt aber von \glqq regul\"aren'' Strukturen nicht erf\"ullt werden?
\end{itemize}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Es sei $\tau = \{E\}$ mit einer zweistelligen Relation $E$. Formalisieren Sie die folgenden in Worten geschriebenen Aussagen als $\cL(\tau)$-Aussagen.
\begin{itemize}
\item[a)] Die Relation $E$ ist eine \"Aquivalenzrelation.
\end{itemize}
Sei $n\in \bN^+$ beliebig.
\begin{itemize}
\item[b)] Es existiert mindestens eine \"Aquivalenzklasse von $E$ mit mindestens $n$ Elementen.
\item[c)] Es existiert mindestens eine \"Aquivalenzklasse von $E$ mit genau $n$ Elementen.
\item[d)] Es existiert genau eine \"Aquivalenzklasse von $E$ mit genau $n$ Elementen.
\end{itemize}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Es sei $\tau=\{E\}$ mit einer zweistelligen Relation $E$. Ein ungerichteter Graph $G=(V,E)$ l\"asst sich auf nat\"urliche Art als $\cL(\tau)$-Struktur mit Universum $V$ auffassen, indem man $E^G$ durch $\{(v,w)\such \{v,w\}\in E\}$ interpretiert.~\\ Beschreiben Sie in Worten, welche Graphen die folgenden $\cL(\tau)$-Aussagen erf\"ullen, und zeichnen Sie jeweils einen erf\"ullenden und einen nicht erf\"ullenden Graphen. 
\begin{itemize}
\item[a)]$\forall x\exists y \exists z (\neg Exy\wedge Exz)$
\item[b)]$\exists x \exists y \exists z \big( \neg y=z \wedge Exy \wedge Exz \wedge \forall w(Exw\to (w=y \vee w=z))\big)$
\end{itemize}
\end{ubung}
\medskip
\begin{flushright}
\textbf{R\"uckseite beachten!}
\end{flushright}
\newpage~\\

\begin{ubung}[4 Punkte] ~\\
Es sei $\tau=\{0,1,+,\cdot,P,E \}$ mit zwei Konstanten $0$ und $1$, zwei zweistelligen Funktionen $+$ und $\cdot$ sowie einer einstelligen Relation $P$. Ferner sei $\fN=(\bN,0,1,+,\cdot,\mathbb{P},2\bN)$ die $\cL(\tau)$-Struktur, in der $0$, $1$, $+$ und $\cdot$ wie \"ublich interpretiert werden, $P$ durch die Primzahlen $\mathbb{P}$ und $E$ durch die geraden Zahlen $2\bN$.~\\ Formalisieren Sie die \emph{Goldbach'sche Vermutung} als $\cL(\tau)$-Aussage: Jede gerade Zahl gr\"o{\ss}er als $2$ ist die Summe zweier Primzahlen.\\~\\
 \emph{Bonus (4 Punkte):} Es sei $\tau'=\{+,\cdot\}$ und $\fN'=(\bN, +,\cdot)$ die $\cL(\tau')$-Struktur in der $+$ und $\cdot$ wie \"ublich interpretiert werden. K\"onnen Sie die Goldbachsche Vermutung auch als $\cL(\tau')$-Aussage formalisieren?

\end{ubung}

\end{document}