Kurs:Einführung in die mathematische Logik/3a/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Termmenge zu einer Grundtermmenge ${}(V,K,F_{n})$.
2. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge ${}\Gamma \subseteq L^{S}$.
3. Die Multiplikation mit ${}n\in \mathbb {N}$ in einem Dedekind-Peano-Modell ${}\mathbb {N}$.
4. Die Befehle für eine Registermaschine.
5. Das modallogische Löb-Axiom.
6. Ein modallogisches Modell.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Vollständigkeitssatz für Tautologien (Prädikatenlogik).
3. Der zweite Gödelsche Unvollständigkeitssatz.

Aufgabe * (2 (1+1) Punkte)

Im Pokal spielt Bayern München gegen den TSV Wildberg. Der Trainer vom TSV Wildberg, Herr Tor Acker, sagt „Wir haben in dem Spiel nichts zu verlieren“. Die Logiklehrerin von Wildberg, Frau Loki Schummele, sagt „Wenn die Wildberger in dem Spiel nichts zu verlieren haben, dann haben auch die Münchner in dem Spiel nichts zu gewinnen“. Der Trainer von Bayern München, Herr Roland Rollrasen, sagt „Wir haben in dem Spiel etwas zu gewinnen“.

1. Ist die Aussage von Frau Schummele logisch korrekt?
2. Es sei vorausgesetzt, dass die Aussage des Bayerntrainers wahr ist. Welche Folgerung kann man dann für die Aussage von Herrn Acker ziehen?

Aufgabe * (5 (1+1+3) Punkte)

1. Löse das folgende Minisudoku

   ${\begin{pmatrix}-&-&2&-\\3&-&-&4\\-&-&-&-\\-&4&-&1\end{pmatrix}}.$

2. Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
3. Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?

Aufgabe * (3 Punkte)

Beweise durch Induktion über den rekursiven Aufbau der Sprache ${}L^{V}$, dass in jeder Aussage ${}\alpha \in L^{V}$ die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.

Aufgabe * (3 Punkte)

Zeige, dass eine Regel der Form

Wenn ${}\vdash \alpha$, dann ${}\vdash \beta$ gelten kann, ohne dass ${}\vdash \alpha \rightarrow \beta$ gilt.

Aufgabe * (4 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die Kettenschlussregel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \beta \rightarrow \gamma$, dann auch ${}\Gamma \vdash \alpha \rightarrow \gamma$.

Aufgabe * (7 (3+4) Punkte)

Es sei ${}V=\{x,y,z,u,v,w\}$ eine Variablenmenge, ${}0$ eine Konstante und ${}-,+,\cdot$ zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck ${}\alpha$, der durch

$\forall x\forall y\forall z\forall u\forall v\forall w{\left(\left[(z-x)(z-y)+(w-u)(w-v)=0\right]\longrightarrow \left[(x-y)(x-y)+(u-v)(u-v)=(x-z)(x-z)+(u-w)(u-w)+(y-z)(y-z)+(v-w)(v-w)\right]\right)}$

gegeben ist.

1. Zeige, dass ${}\alpha$ bei Interpretation in einem Körper ${}K$ wahr wird, wenn man ${}0$ als ${}0$ und ${}\{-,+,\cdot \}$ als Subtraktion, Addition und Multiplikation interpretiert.
2. Welcher wichtige mathematische Satz verbirgt sich dahinter?

Aufgabe * (6 Punkte)

Beweise die Termaussage des Substitutionslemmas.

Aufgabe * (2 Punkte)

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet ${}S$, dass ein Untervektorraum in einem Vektorraum über einem Körper vorliegt.

Aufgabe * (4 Punkte)

Zeige, dass in einem Peano-Halbring ${}M$ zu ${}d\geq 1$ die Division mit Rest eindeutig ist.

Aufgabe (4 Punkte)

Beschreibe die wesentlichen Punkte bei der Konstruktion eines Modells, mit dem man die Erfüllbarkeit einer maximal widerspruchsfreien Ausdrucksmenge, die Beispiele enthält, nachweist.

Aufgabe * (3 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe ${}\mathbb {Z} /(2)\times \mathbb {Z} /(2)$ zum Symbolalphabet ${}S=\{0,+\}$.

Aufgabe * (6 Punkte)

Es sei ${}T\subseteq \mathbb {N}$ eine endliche Teilmenge. Man gebe ein Programm für eine Registermaschine an, das nur auf einen einzigen Register ${}R_{1}$ Bezug nimmt, das bei jeder Eingabe (in ${}R_{1}$) immer anhält und das im Anhaltezustand in ${}R_{1}$ genau dann den Wert ${}0$ besitzt, wenn die Eingabe zu ${}T$ gehört.

Aufgabe * (4 Punkte)

Es sei

$F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

eine arithmetisch repräsentierbare Abbildung. Zeige, dass zu jedem Punkt ${}P\in \mathbb {N} ^{s}$ die Faser

${}F^{-1}(P)\subseteq \mathbb {N} ^{r}\,$

arithmetisch repräsentierbar ist.

Aufgabe * (5 Punkte)

Zeige, dass eine aufzählbar axiomatisierbare Theorie ${}T\subseteq L_{0}^{S}$ auch ${}R$-aufzählbar ist.