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

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)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (4 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe * (4 (1+3) Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Beweise den Satz von Henkin.

Aufgabe * weiterReferenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Beweise das Unvollständigkeitslemma.