Kurs:Einführung in die mathematische Logik/19/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	${}\sum$
Punkte	3	3	4	2	4	3	4	3	8	10	5	3	6	2	4	64

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein maximales Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
2. Die Termsubstitution ${}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ für ${}S$-Terme ${}s$ (dabei sei ${}S$ ein Symbolalphabet einer Sprache erster Stufe, ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme).
3. Der Rang eines prädikatenlogischen Ausdrucks ${}\alpha$.
4. Die elementare Äquivalenz von zwei ${}S$- Strukturen ${}M$ und ${}N$ über einem erststufigen Symbolalphabet ${}S$.
5. Eine ${}R$-berechenbare Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N} .$

6. Die ${}\beta$-Funktion ${}\beta (p,n,i)$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Euklid über Primzahlen.
2. Das Substitutionslemma.
3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Aufgabe * (4 Punkte)

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.

1. Fanny sitzt nicht auf Pona.
2. Pone und Ponu vertragen sich nicht so gut und laufen daher nicht direkt hintereinander.
3. Nanny sitzt auf Pone oder auf Pono.
4. Sanny reitet auf Pona oder auf Pone.
5. Nanny reitet direkt hinter Sanny.
6. Auf Ponu sitzt nicht Sanny.
7. Pona läuft direkt zwischen Pone und Pono.
8. Auf Pono sitzt weder Fanny noch Hanny.
9. Sanny reitet weiter vorne als Hanny.

Wer sitzt auf welchem Pony und in welcher Reihenfolge laufen sie?

Aufgabe (2 Punkte)

Man gebe signifikante Beispiele zum Stichwort „Fortsetzung einer Abbildung“ aus der Mathematik und aus der mathematischen Logik.

Aufgabe * (4 (1+3) Punkte)

Wir betrachten Wörter über dem Alphabet ${}\{a,x\}$ und den Prozess ${}P$, der in einem solchen Wort jedes Vorkommen von ${}x$ durch das Wort ${}xax$ ersetzt.

1. Bestimme das Ergebnis von ${}axxax$ unter diesem Prozess.
2. Diesen Prozess kann man iterieren. Mit ${}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 ${}P^{n}(w)$ zum Startwort ${}w=x$.

Aufgabe * (3 Punkte)

Es sei ${}L^{V}$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ und es sei ${}\lambda$ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation ${}I$. Zeige, dass ${}I^{\vDash }$ maximal widerspruchsfrei ist.

Aufgabe * (4 Punkte)

Es seien ${}A,B,C$ einstellige Relationssymbole. Erstelle eine Ableitung im Prädikatenkalkül für den Modus Disamis, also die Aussage

$(\exists x(Ax\wedge Bx)\wedge \forall x(Ax\rightarrow Cx))\rightarrow \exists x(Cx\wedge Bx).$

Aufgabe * (3 Punkte)

In einem angeordneten Körper ist durch

${}\vert {x}\vert \geq \vert {y}\vert \,$

eine zweistellige Relation gegeben. Drücke diese Relation mit den üblichen Symbolen ${}0,-,\geq$, Variablen und aussagenlogischen Junktoren aus.

Aufgabe * (8 Punkte)

Beweise den Satz von Henkin.

Aufgabe * weiter

Es sei ${}S$ das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol ${}G$ besteht. Wir betrachten die KO-Runden (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. ${}xGy$ besagt, dass ${}x$ gegen ${}y$ (gespielt und) gewonnen hat.

1. Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
2. Ist ${}\forall yxGy$ eine Charakterisierung des Weltmeisters?
3. Charakterisiere durch einen ${}S$-Ausdruck in der einen freien Variablen ${}x$, dass eine Mannschaft mindestens das Halbfinale erreicht hat.
4. Charakterisiere durch einen ${}S$-Ausdruck in der einen freien Variablen ${}x$, dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
5. Betrachte Schweden bei der WM 2018. Man gebe einen ${}S$-Ausdruck in der einen freien Variablen ${}x$, der Schweden charakterisiert.
6. Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den ${}S$-Ausdruck, der Schweden bei der WM 2018 charakterisiert?
7. Definiere einen ${}S$- Isomorphismus zwischen der WM 2014 und der WM 2018.
8. Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz ${}3$ mitberücksichtigt?

Aufgabe * (5 Punkte)

Schreibe einen Programmabschnitt ${}C(i,j,k)$ für eine Registermaschine, das zum Befehl ${}j$ wechselt, wenn im ${}i$-ten Register der Wert ${}k$ steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.

Aufgabe (3 Punkte)

Es seien ${}T_{1},T_{2}\subseteq L^{S}$ aufzählbar axiomatisierbare Theorien. Zeige, dass dann auch ${}(T_{1}\cup T_{2})^{\vdash }$ aufzählbar ist.

Aufgabe * (6 Punkte)

Es sei

${}T=\mathbb {N} 2\subseteq \mathbb {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

${}\psi =\exists y(x=y+y)\,.$

Zeige, dass ${}T$ durch ${}\psi$ in ${}\Gamma$ schwach repräsentiert wird, aber nicht stark.

Aufgabe * (2 Punkte)

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge und ${}\alpha$ ein einstelliges Prädikat mit

$\Gamma \vdash \alpha (n)$

für alle ${}n\in \mathbb {N}$. Zeige, dass es einen Satz ${}q$ mit

$\Gamma \vdash \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe * (4 Punkte)

Beweise das Unvollständigkeitslemma.