Kurs:Einführung in die mathematische Logik/19/Klausur/latex
%Daten zur Institution
%\input{Dozentdaten}
%\renewcommand{\fachbereich}{Fachbereich}
%\renewcommand{\dozent}{Prof. Dr. . }
%Klausurdaten
\renewcommand{\klausurgebiet}{ }
\renewcommand{\klausurtyp}{ }
\renewcommand{\klausurdatum}{ . 20}
\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}
%Daten für folgende Punktetabelle
\renewcommand{\aeins}{ 3 }
\renewcommand{\azwei}{ 3 }
\renewcommand{\adrei}{ 4 }
\renewcommand{\avier}{ 2 }
\renewcommand{\afuenf}{ 4 }
\renewcommand{\asechs}{ 3 }
\renewcommand{\asieben}{ 4 }
\renewcommand{\aacht}{ 3 }
\renewcommand{\aneun}{ 8 }
\renewcommand{\azehn}{ 10 }
\renewcommand{\aelf}{ 5 }
\renewcommand{\azwoelf}{ 3 }
\renewcommand{\adreizehn}{ 6 }
\renewcommand{\avierzehn}{ 2 }
\renewcommand{\afuenfzehn}{ 4 }
\renewcommand{\asechzehn}{ 64 }
\renewcommand{\asiebzehn}{ }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellefuenfzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabegibtloesung
{3}
{
Definiere die folgenden
\zusatzklammer {kursiv gedruckten} {} {} Begriffe.
\aufzaehlungsechs{Ein
\stichwort {maximales Element} {}
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einer
\definitionsverweis {geordneten Menge}{}{}
\mathl{(I,\preccurlyeq)}{.}
}{Die
\stichwort {Termsubstitution} {}
\mathl{s { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} für $S$-Terme $s$
\zusatzklammer {dabei sei $S$ ein Symbolalphabet einer
\definitionsverweis {Sprache erster Stufe}{}{,}
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte
$S$-\definitionsverweis {Terme}{}{}} {} {.}
}{Der \stichwort {Rang} {} eines prädikatenlogischen Ausdrucks
\mathl{\alpha}{.}
}{Die
\stichwort {elementare Äquivalenz} {}
von zwei
$S$-\definitionsverweis {Strukturen}{}{}
$M$ und $N$ über einem
\definitionsverweis {erststufigen Symbolalphabet}{}{}
$S$.
}{Eine \stichwortpraemath {R} {berechenbare Funktion}{} \maabbdisp {F} {\N^k} {\N } {.}
}{Die $\beta$-\stichwort {Funktion} {}
\mathl{\beta(p,n,i)}{.}
}
}
{} {}
\inputaufgabegibtloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der \stichwort {Satz von Euklid} {} über Primzahlen.}{Das \stichwort {Substitutionslemma} {.}}{Der \stichwort {Satz über die induktive Definition einer Abbildung} {} auf einem Peano-Dedekind-Modell $(N,0,\prime)$.}
}
{} {}
\inputaufgabegibtloesung
{4}
{
Hanny, Nanny, Fanny und Sanny leben auf dem Ponyhof. Heute machen sie einen Ausflug mit den Ponies Pona, Pone, Pono und Ponu. Jedes der Mädchen sitzt dabei genau auf einem Pony, und sie reiten hintereinander. Folgende Fakten sind bekannt. \aufzaehlungneun{Fanny sitzt nicht auf Pona. }{Pone und Ponu vertragen sich nicht so gut und laufen daher nicht direkt hintereinander. }{Nanny sitzt auf Pone oder auf Pono. }{Sanny reitet auf Pona oder auf Pone. }{Nanny reitet direkt hinter Sanny. }{Auf Ponu sitzt nicht Sanny. }{Pona läuft direkt zwischen Pone und Pono. }{Auf Pono sitzt weder Fanny noch Hanny. }{Sanny reitet weiter vorne als Hanny. } Wer sitzt auf welchem Pony und in welcher Reihenfolge laufen sie?
}
{} {}
\inputaufgabe
{2}
{
Man gebe signifikante Beispiele zum Stichwort \anfuehrung{Fortsetzung einer Abbildung}{} aus der Mathematik und aus der mathematischen Logik.
}
{} {}
\inputaufgabegibtloesung
{4 (1+3)}
{
Wir betrachten Wörter über dem Alphabet
\mathl{\{a,x\}}{} und den Prozess $P$, der in einem solchen Wort jedes Vorkommen von $x$ durch das Wort
\mathl{xax}{} ersetzt.
\aufzaehlungzwei {Bestimme das Ergebnis von
\mathl{axxax}{} unter diesem Prozess.
} {Diesen Prozess kann man iterieren. Mit
\mathl{P^n(w)}{} bezeichnen wir das Ergebnis, wenn man den Prozess $n$-mal hintereinander auf das Startwort $w$ anwendet. Bestimme die Anzahl der Buchstaben in
\mathl{P^n(w)}{} zum Startwort
\mavergleichskette
{\vergleichskette
{w
}
{ = }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
{} {}
\inputaufgabegibtloesung
{3}
{
Es sei
\mathl{L^V}{} die
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer
\definitionsverweis {Aussagenvariablenmenge}{}{}
$V$ und es sei $\lambda$ eine
\definitionsverweis {Wahrheitsbelegung}{}{}
der Variablen mit zugehöriger
\definitionsverweis {Interpretation}{}{}
$I$. Zeige, dass $I^\vDash$
\definitionsverweis {maximal widerspruchsfrei}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Es seien
\mathl{A,B,C}{} einstellige Relationssymbole. Erstelle eine Ableitung im Prädikatenkalkül für den \stichwort {Modus Disamis} {,} also die Aussage
\mathdisp {( \exists x (Ax \wedge Bx) \wedge \forall x (Ax \rightarrow Cx) ) \rightarrow \exists x (Cx \wedge Bx)} { . }
}
{} {}
\inputaufgabegibtloesung
{3}
{
In einem
\definitionsverweis {angeordneten Körper}{}{}
ist durch
\mavergleichskettedisp
{\vergleichskette
{ \betrag { x }
}
{ \geq} { \betrag { y }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine zweistellige
\definitionsverweis {Relation}{}{}
gegeben. Drücke diese Relation mit den üblichen Symbolen
\mathl{0, -,\geq}{,} Variablen und aussagenlogischen Junktoren aus.
}
{} {}
\inputaufgabegibtloesung
{8}
{
Beweise den Satz von Henkin.
}
{} {}
\inputaufgabegibtloesung
{weiter}
{
Es sei $S$ das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol $G$ besteht. Wir betrachten die KO-Runden
\zusatzklammer {also ab dem Achtelfinale} {} {}
der Fußballweltmeisterschaften von 2014 und von 2018, ohne das Spiel um Platz $3$, als $S$-Modelle, wobei wir $G$ als die Gewinnrelation interpretieren, d.h.
\mathl{xGy}{} besagt, dass $x$ gegen $y$
\zusatzklammer {gespielt und} {} {}
gewonnen hat.
\aufzaehlungacht{Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
}{Ist
\mathl{\forall y xGy}{} eine Charakterisierung des Weltmeisters?
}{Charakterisiere durch einen $S$-Ausdruck in der einen freien Variablen $x$, dass eine Mannschaft mindestens das Halbfinale erreicht hat.
}{Charakterisiere durch einen $S$-Ausdruck in der einen freien Variablen $x$, dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
}{Betrachte Schweden bei der WM 2018. Man gebe einen $S$-Ausdruck in der einen freien Variablen $x$, der Schweden charakterisiert.
}{Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den $S$-Ausdruck, der Schweden bei der WM 2018 charakterisiert?
}{Definiere einen
$S$-\definitionsverweis {Isomorphismus}{}{}
zwischen der WM 2014 und der WM 2018.
}{Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz $3$ mitberücksichtigt?
}
}
{} {}
\inputaufgabegibtloesung
{5}
{
Schreibe einen Programmabschnitt
\mathl{C(i,j,k)}{} für eine
\definitionsverweis {Registermaschine}{}{,}
das zum Befehl $j$ wechselt, wenn im $i$-ten Register der Wert $k$ steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.
}
{} {}
\inputaufgabe
{3}
{
Es seien
\mavergleichskette
{\vergleichskette
{T_1, T_2
}
{ \subseteq }{L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {aufzählbar axiomatisierbare Theorien}{}{.}
Zeige, dass dann auch
\mathl{(T_1 \cup T_2)^\vdash}{}
\definitionsverweis {aufzählbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{6}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{T
}
{ =} { \N 2
}
{ \subseteq} {\N
}
{ } {
}
{ } {
}
}
{}{}{}
die Menge der geraden natürlichen Zahlen. Es sei $\Gamma$ die Ausdrucksmenge, die besagt, dass $+$ eine assoziative, kommutative Verknüpfung mit $0$ als neutralem Element ist. Es sei
\mavergleichskettedisp
{\vergleichskette
{\psi
}
{ =} { \exists y (x = y+y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige, dass $T$ durch $\psi$ in $\Gamma$
\definitionsverweis {schwach repräsentiert}{}{}
wird, aber nicht stark.
}
{} {}
\inputaufgabegibtloesung
{2}
{
Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat mit
\mathdisp {\Gamma \vdash \alpha (n)} { }
für alle
\mathl{n \in \N}{.} Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.
}
{} {}
\inputaufgabegibtloesung
{4}
{
Beweise das Unvollständigkeitslemma.
}
{} {}