%blatt9
\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{\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 21.12.2022, 10 Uhr.}



\begin{center}
 \textbf{BLATT 9}\\
 (14.12.2022)
\end{center}
Es sei $\tau=\{R,P,f,g,c\}$ eine Symbolmenge, die aus den 2-stelligen Relationszeichen $R$, 1-stelligen Relationszeichen $P$, $2$-stelligen Funktionszeichen $f$, $1$-stelligen Funktionszeichen $g$ und aus dem Konstantenzeichen  $c$  besteht.


\begin{ubung}[4 Punkte]~\\
Entscheiden Sie, welche der folgenden Ausdr\"ucke $\cL(\tau)$-Terme sind und welche nicht. Sie m\"ussen dabei keine Begr\"undung angeben.
\begin{multicols}{2}
\begin{itemize}
\item[a)] $c$
\item[b)] $v_{73}$
\item[c)] $v_1 f c$
\item[d)] $fcv_5$
\item[e)] $Rcfv_1c$
\item[f)] $fffv_1v_2v_3v_4$
\item[g)] $gcfcc$
\item[h)] $fgcfcc$
\end{itemize}
\end{multicols}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Entscheiden Sie, welche der folgenden Ausdr\"ucke $\cL(\tau)$-Formeln sind und welche nicht. Sie m\"ussen dabei keine Begr\"undung angeben.
\begin{multicols}{2}
\begin{itemize}
\item[a)] $fv_1c$
\item[b)] $gv_1=c$
\item[c)] $Rcfv_1c$
\item[d)] $(Pc \lra fv_1v_2)$
\item[e)] $\forall x Ryz $
\item[f)] $Rv_1gc = gv_7 c$
\item[g)] $(\exists x (Pc \wedge Rcx) \wedge \forall x (\neg Pc \vee \neg Rcx))$
\item[h)] $\forall v_1 (Pv_1 \rightarrow (\exists v_1 \lnot Pv_1 \vee \exists v_1 Rgv_1v_1 fv_2))$
\end{itemize}
\end{multicols}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Bestimmen Sie, ohne Beweis, die Menge der freien Variablen f\"ur die folgenden $\cL(\tau)$-Formeln.
\begin{enumerate}
\item[a)] $Rcv_1 \to \exists v_2 fv_2c = v_1$
\item[b)] $\exists v_2 (\forall v_1 Pc \to Rv_1v_2)\wedge fv_1v_2=c$
\item[c)] $\exists x\big(\forall y\forall z (gx = fyz \to (Px \wedge Ryz))\wedge fgxgx \neq c \big) $
\item[d)] $\forall v_0\exists v_1 (((gv_0 = c \wedge Pv_1) \rightarrow \exists v_0 f v_0v_0=gv_0))\leftrightarrow (\forall v_2 R v_1 v_2 \vee Pv_2)$
\end{enumerate}
\end{ubung}

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

\begin{ubung}[4 Punkte] ~\\
Beweisen Sie die folgenden Aussagen oder widerlegen Sie sie durch ein Beispiel
\begin{itemize}
\item[a)] Keine Formel ist echtes Endst\"uck einer anderen Formel.
\item[b)] Jedes nicht-leere Endst\"uck eines Terms l\"asst sich eindeutig als eine endliche Folge von Termen schreiben.
\end{itemize}
\end{ubung}


\end{document}