Kurs:Einführung in die mathematische Logik/2/Klausur mit Lösungen/kontrolle

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (1 Punkt)Referenznummer erstellen

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

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

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

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

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

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

Aufgabe * (7 Punkte)Referenznummer erstellen

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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

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

Aufgabe (3 Punkte)Referenznummer erstellen

Erläutere die Churchsche These.

Aufgabe * (12 Punkte)Referenznummer erstellen

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.