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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Ableitbarkeit eines Aussage ${}\alpha \in L^{V}$ aus einer Aussagenmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge ${}V$.
2. Eine ${}n$-stellige Relation auf einer Menge ${}M$.
3. Die Folgerungsbeziehung ${}\Gamma \vDash \alpha$, wobei ${}\Gamma$ eine Menge von ${}S$- Ausdrücken und ${}\alpha$ ein ${}S$-Ausdruck ist (und ${}S$ ein Symbolalphabet.)
4. 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).
5. Die Addition in einem Dedekind-Peano-Modell ${}\mathbb {N}$.
6. Die Register-Entscheidbarkeit einer Teilmenge ${}T\subseteq \mathbb {N}$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Substitutionslemma.
2. Der Satz über das Halteproblem.
3. Der Fixpunktsatz für arithmetische Ausdrücke.

Aufgabe * (1 Punkt)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}?$ w w f w f f f w w f f f

Aufgabe * (4 (2+2) Punkte)

Es sei ${}G$ eine unendliche Menge und ${}M\subset {\mathfrak {P}}\,(G)$ die Menge, die aus sämtlichen endlichen Teilmengen von ${}G$ besteht.

1. Ist ${}(M,\subseteq )$ induktiv geordnet?
2. Besitzt ${}M$ maximale Elemente?

Aufgabe * (9 (1+3+2+1+2) Punkte)

Es sei ${}L^{S}$ die prädikatenlogische Sprache, die neben Variablen aus einem zweistelligen Relationssymbol ${}A$ und einem dreistelligen Relationssymbol ${}B$ bestehe. Wir betrachten ${}S$- Interpretationen ${}I$, wobei die Grundmenge jeweils aus einem Vektorraum ${}V$ über einem Körper ${}K$ bestehe und ${}A$ als die lineare Unabhängigkeit von zwei und ${}B$ als die lineare Unabhängigkeit von drei Vektoren interpretiert werde.

1. Zeige

   $I\vDash Bxyz\rightarrow Axy.$

2. Gilt

   $I\vDash Axy\wedge Axz\wedge Ayz\rightarrow Bxyz$

   für einen beliebigen Vektorraum?

3. Gibt es Vektorräume, für die die Aussage in Teil 2 gilt?
4. Es sei ${}V=\mathbb {R} ^{3}$ und ${}e_{1},e_{2},e_{3}$ sei die Standardbasis. Gilt

   $I{\frac {e_{1},e_{2},e_{3}}{x,y,z}}\vDash Bxyz?$

5. Es sei ${}V=\mathbb {R}$ als ${}\mathbb {Q}$-Vektorraum betrachtet. Gilt

   $I{\frac {1,{\sqrt {2}}}{x,y}}\vDash Axy?$

Aufgabe * (4 Punkte)

Zeige durch ein Beispiel, dass für Terme ${}r_{1},r_{2},s$ und eine Variable ${}x$ einer prädikatenlogischen Sprache ${}L^{S}$ der Ausdruck

$r_{1}=r_{2}\rightarrow r_{1}{\frac {s}{x}}=r_{2}{\frac {s}{x}}$

nicht ableitbar sein muss.

Aufgabe * (6 (3+1+2) Punkte)

Es seien ${}x,y,u,v$ Variablen und ${}\Gamma =\{\forall x\forall y{\left(x=y\right)}\}$ und ${}\Delta =\{x=y\}$.

1. Zeige (ohne Bezug auf den Vollständigkeitssatz) ${}\Gamma \vdash u=v$.
2. Charakterisiere die Modelle ${}M$ mit ${}M\vDash \Gamma$.
3. Zeige ${}\Delta \not \vdash u=v$.

Aufgabe * (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.

Aufgabe * (7 Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}I$ eine ${}S$- Interpretation auf einer Menge ${}M$, wobei die Terminterpretation surjektiv sei. Zeige, dass die Gültigkeitsmenge ${}\Gamma =I^{\vDash }$ maximal widerspruchsfrei ist und Beispiele enthält.

Aufgabe (2 Punkte)

Man gebe ein Beispiel für eine mathematische Begriffsbildung, die als ${}S$- Homomorphismus zu einem geeigneten Symbolalphabet ${}S$ verstanden werden kann.

Aufgabe * (3 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Primzahlen ausdruckt.

Aufgabe (3 Punkte)

Erläutere die Churchsche These.

Aufgabe * (12 Punkte)

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge und ${}R\subseteq \mathbb {N}$ eine Relation. Es seien ${}\alpha ,\beta \in L^{\rm {Ar}}$ Ausdrücke in einer freien Variablen ${}x$. Zeige, dass aus

$\Gamma \vdash \alpha \leftrightarrow \beta$

nicht folgt, dass ${}\alpha$ in ${}\Gamma$ die Relation ${}R$ genau dann repräsentiert, wenn ${}\beta$ in ${}\Gamma$ die Relation ${}R$ repräsentiert.