%blatt11
\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 18.1.2023, 10 Uhr.}



\begin{center}
 \textbf{BLATT 11}\\
 (11.1.2023)
\end{center}


\begin{ubung}[4 Punkte]~\\
Es sei $\tau=\{+,\cdot\}$ mit zwei zweistelligen Funktionen $+$ und $\cdot$. Wir betrachten die $\cL(\tau)$-Struktur $\fN=(\bN,+,\cdot)$, in der $+$ und $\cdot$ wie \"ublich interpretiert werden, eine Belegung $s: \{v_0,v_1,\dots\} \to \bN$ mit $s(v_0)=5$, $s(v_1)=4$ und $s(v_2)=13$, sowie die folgenden drei $\cL(\tau)$-Formeln:
\begin{align*}
\varphi_1:\quad &+\cdot v_0v_0\cdot v_1 v_1 = \cdot v_2 v_2, \mbox{ oder }
(v_0 \cdot v_0) + (v_1 \cdot v_1) = v_2 \cdot v_2, \\
\varphi_2:\quad &\exists x \; \cdot xx = v_1, \mbox{ oder } \exists x \;  x \cdot x = v_1,\\
\varphi_3:\quad &\forall x\forall y (\cdot xy = v_2 \to (x=v_2\vee y=v_2)), \mbox{ oder } \forall x\forall y (x\cdot y = v_2 \to (x=v_2\vee y=v_2)).
\end{align*}
\begin{itemize}
\item[a)]Entscheiden Sie  f\"ur $i=1,2,3$ ob $\fN \models \varphi_i[s]$ gilt.
\item[b)]Gilt $\fN \models \varphi_i[s(\frac{12}{v_1})]$ f\"ur $i=1,2$?
\item[c)]Geben Sie eine Belegung $s'$ an, sodass $\fN \models \varphi_i[s']$ gilt f\"ur $i=1,2,3$.
\end{itemize}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Es sei $\tau=\{R\}$ mit einem zweistelligen Relationszeichen $R$. Geben Sie f\"ur die folgenden $\cL(\tau)$-Formeln jeweils eine $\cL(\tau)$-Struktur $\fA$ und eine Belegung $s$ an, sodass die jeweilige Formel von $\fA$ mit der Belegung $s$ erf\"ullt wird.
\begin{itemize}
\item[a)] $Rxy\wedge Ryz \wedge \neg Rxz$
\item[b)] $\forall x Rxy$
\item[c)] $\neg x=y \wedge Rxy \wedge \forall z (Rzy \to z=x)$
\item[d)] $\forall x\forall y(Rxy\to\exists z(Rxz\wedge Rzy))$
\end{itemize}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Es sei $\tau = \{R\}$ mit einem zweistelligen Relationszeichen $R$. Geben Sie eine $\cL(\tau)$-Struktur an, welche die folgenden $\cL(\tau)$-S\"atze erf\"ullt, und drei $\cL(\tau)$-Strukturen, welche jeweils zwei der drei S\"atze erf\"ullen, den dritten aber nicht (in jeder m\"oglichen Kombination).
\begin{itemize}
\item[i)] $\forall x \forall y \forall z (( R(x,y) \land R(y,z)) \rightarrow R(x,z))$,
\item[ii)] $\forall x \forall y ((R(x,y) \land R (y,x)) \rightarrow x = y)$,
\item[iii)] $(\forall x \exists y R(x,y) \rightarrow \exists y \forall x R(x,y))$.
\end{itemize}
\end{ubung}
\medskip


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

\begin{ubung}[4 Punkte] ~\\
Es sei $\tau = \{c_1,c_2,f,H\}$ mit zwei Konstanten $c_1$ und $c_2$, einem einstelligen Funktionszeichen $f$ und einem einstelligen Relationszeichen $H$.
\begin{itemize}
\item[a)] Sei $\Sigma = \{ \forall x (fx=c_1 \to Hx), \;\forall y(Hy\to y=c_2)\}$. Gilt dann
$\Sigma \models fc_2=c_1$?
\item[b)] Gilt
$\Sigma \models \exists x( Hx \to \forall y Hy)$?
\end{itemize}
\end{ubung}

\end{document}