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

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}$.

Lösung

1. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ ableitbar ist, wenn es endlich viele Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma$ derart gibt, dass

   $\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha$

   gilt.

2. Unter einer ${}n$-stelligen Relation ${}R$ auf ${}M$ versteht man eine Teilmenge der ${}n$-fachen Produktmenge ${}M\times \cdots \times M$.
3. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, wenn für jede ${}S$- Interpretation ${}I$ mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.
4. Die Termsubstitution ${}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ wird rekursiv folgendermaßen definiert.
   1. Für eine Variable ${}x$ ist

      ${}x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:={\begin{cases}x,{\text{ falls }}x\neq x_{i}{\text{ für alle }}i\,,\\t_{i},{\text{ falls }}x=x_{i}\,.\end{cases}}\,$

   2. Für eine Konstante ${}c$ ist

      ${}c{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=c\,.$

   3. Für ein ${}n$-stelliges Funktionssymbol ${}f$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ ist

      ${}fs_{1}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.$

5. Die Addition ${}n+k$ wird über die Addition ${}\alpha _{n}$ mit festem ${}n$ definiert, wobei ${}\alpha _{n}$ die eindeutig bestimmte Abbildung

   $\alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),$

   ist, für die

   $\alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N}$

   gilt.

6. Die Teilmenge ${}T$ heißt Register-entscheidbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

   $n\in T{\text{ genau dann, wenn }}P(n){\text{ die Ausgabe }}0{\text{ besitzt}}$

   gilt.

 

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.

Lösung

1. Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$-Terme. Es sei eine ${}S$-Interpretation ${}I$ gegeben. Dann gelten folgende Aussagen.
   1. Für jeden ${}S$-Term ${}s$ gilt

      ${}I\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)=\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)(s)\,.$

   2. Für jeden ${}S$-Ausdruck ${}\alpha$ gilt

      $I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}{\text{ genau dann, wenn }}{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}\vDash \alpha .$

2. Die Menge

   ${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}$

   ist nicht ${}R$-

   entscheidbar.
3. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem ${}\alpha \in L_{1}^{\rm {Ar}}$ einen Satz ${}q\in L_{0}^{\rm {Ar}}$ mit

   $\Gamma \vdash q\longleftrightarrow \alpha (GN(q)).$

 

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

Lösung

${}\neg p\wedge q$.

 

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?

Lösung

1. Da ${}G$ unendlich ist, gibt es darin insbesondere verschiedene Elemente ${}x_{n}$ zu ${}n\in \mathbb {N} _{+}$. Wir betrachten die endlichen Teilmengen

   ${}G_{n}:=\{x_{1},x_{2},\ldots ,x_{n}\}\,.$

   Diese gehören zu ${}M$ und es liegen die (echten) Inklusionen ${}G_{n}\subset G_{n+1}$ vor, d.h. diese Mengen bilden eine Kette. Eine obere Schranke für diese Mengen muss aber alle Elemente ${}x_{n}$ enthalten, also unendlich sein, und eine solche gibt es nicht in ${}M$.

2. Es gibt in ${}M$ keine maximalen Elemente. Ein Element ${}N\in M$ ist eine endliche Menge von ${}G$. Da ${}G$ unendlich ist, gibt es ein Element ${}x\in G$ mit ${}x\notin N$. Dann ist ${}N\cup \{x\}$ eine ebenfalls endliche Teilmenge von ${}G$ (gehört also zu ${}M$), die ${}N$ echt umfasst, sodass ${}N$ nicht maximal ist.

 

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?$

Lösung

1. Wenn drei Vektoren linear unabhängig sind, so sind insbesondere je zwei davon linear unabhängig.
2. Dies gilt im Allgemeinen nicht. Dazu sei ${}V=\mathbb {R} ^{2}$ und wir betrachten die drei Vektoren ${}(1,0),(1,1),(0,1)$. Die drei Vektoren sind insgesamt linear abhängig, da in einem zweidimensionalen Vektorraum drei Vektoren immer linear abhängig sind. Dagegen ist jede Auswahl von zwei der Vektoren linear unabhängig, da keiner der Vektoren ein Vielfaches eines anderen ist.
3. In einem eindimensionalen (oder nulldimensionalen) Vektorraum ${}V$ gilt die Aussage, da es dort keine zwei linear unabhängigen Vektoren gibt und daher der Vordersatz stets falsch ist und somit die Gesamtaussage stimmt.
4. Die Standardvektoren im ${}\mathbb {R} ^{3}$ sind eine Basis und insbesondere linear unabhängig, daher gilt die Aussage.
5. Die ${}{\sqrt {2}}$ ist keine rationale Zahl, daher sind die beiden reellen Zahlen ${}1$ und ${}{\sqrt {2}}$ über ${}\mathbb {Q}$ linear unabhängig, und daher gilt diese Aussage.

 

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.

Lösung

Wir betrachten ${}r_{1}=x$, ${}r_{2}=y$ und ${}s=c$, wobei ${}x,y$ Variablen seien und ${}c$ eine Konstante sei. Dann ist ${}r_{1}{\frac {s}{x}}=c$ und ${}r_{2}{\frac {s}{x}}=y$. Die Aussage lautet also in diesem Spezialfall

$x=y\rightarrow c=y.$

Dieser Ausdruck ist aber nicht allgemeingültig, da man ${}x$ und ${}y$ durch ein gemeinsames, von ${}c^{M}$ verschiedenes Element belegen kann.

 

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$.

Lösung

1. Nach der Allversion zu Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

   $\vdash \forall x{\left(\forall y{\left(x=y\right)}\right)}\rightarrow {\left(\forall y{\left(x=y\right)}\right)}{\frac {u}{x}}$

   eine Tautologie. Der Nachsatz ist ${}\forall y{\left(u=y\right)}$. Aus dem gleichen Grund ist

   $\vdash \forall y{\left(u=y\right)}\rightarrow {\left(u=y\right)}{\frac {v}{y}}$

   eine Tautologie. Der Nachsatz ist ${}u=v$. Mit Modus ponens gilt daher

   $\Gamma \vdash \forall y{\left(u=y\right)}$

   und

   $\Gamma \vdash u=v.$

2. Das bedeutet, dass die Grundmenge der Struktur einelementig sein muss, da alle Elemente gleich sind.
3. Um die Nichtableitbarkeit ${}\Delta \not \vdash u=v$ zu zeigen, genügt es aufgrund des Korrektheitssatzes, eine Interpretation ${}I$ mit ${}I\vDash \Delta$, aber ${}I\not \vDash u=v$ anzugeben. Dazu sei ${}M=\{a,b\}$ eine zweielementige Menge und die Variablenbelegung sei durch ${}I(x)=I(y)=I(u)=a$ und

   ${}I(v)=b\,$

   festgelegt.

 

Aufgabe * (7 Punkte)

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

Lösung

Es sei ${}\alpha {\frac {y}{x}}\rightarrow \beta$ allgemeingültig, d.h.

$I\vDash \alpha {\frac {y}{x}}\rightarrow \beta$

für jede ${}S$- Interpretation ${}I$. Wir müssen zeigen, dass dann auch ${}\exists x\alpha \rightarrow \beta$ allgemeingültig ist (unter den gegebenen Voraussetzungen). Es sei dazu ${}I$ eine Interpretation mit

$I\vDash \exists x\alpha .$

Aufgrund der Modellbeziehung bedeutet dies, dass es ein ${}m\in M$ (aus der Grundmenge der Interpretation) mit

$I{\frac {m}{x}}\vDash \alpha$

gibt. Die Variable ${}y$ kommt nach Voraussetzung in ${}\exists x\alpha$ nicht frei vor, d.h. bei ${}y\neq x$, dass ${}y$ in ${}\alpha$ nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten

${\left(I{\frac {m}{x}}\right)}{\frac {m}{y}}\vDash \alpha .$

Diese Aussage gilt trivialerweise auch bei ${}x=y$. Damit gilt auch

${\left(I{\frac {m}{y}}\right)}{\frac {m}{x}}\vDash \alpha .$

Wir schreiben dies (etwas künstlich) als

${\left(I{\frac {m}{y}}\right)}{\frac {{\left(I{\frac {m}{y}}\right)}(y)}{x}}\vDash \alpha .$

Darauf können wir das Substitutionslemma (für die Interpretation ${}J=I{\frac {m}{y}}$ und den Term ${}y$) anwenden und erhalten

$I{\frac {m}{y}}\vDash \alpha {\frac {y}{x}}.$

Wegen der vorausgesetzten Allgemeingültigkeit von ${}\alpha {\frac {y}{x}}\rightarrow \beta$ folgt

$I{\frac {m}{y}}\vDash \beta .$

Da ${}y$ in ${}\beta$ nicht frei vorkommt, liefert das Koinzidenzlemma

$I\vDash \beta .$

 

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.

Lösung

Zunächst ist ${}\Gamma =I^{\vDash }$ aufgrund des Korrektheitssatzes abgeschlossen unter Ableitungen. Für jeden ${}S$- Ausdruck ${}\alpha$ gilt die Alternative: Entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$. Insbesondere ist ${}\Gamma$ widerspruchsfrei. Wenn ${}\alpha \notin \Gamma$ ist, so ist ${}\neg \alpha \in \Gamma$ und daher ist ${}\Gamma \cup \{\alpha \}$ widersprüchlich. Also ist ${}\Gamma$ maximal widerspruchsfrei.
Wir betrachten nun einen Ausdruck der Form ${}\alpha =\exists x\beta$. Wenn ${}\alpha \notin \Gamma$ gilt, so gilt ${}\exists x\beta \rightarrow \beta {\frac {t}{x}}$ in ${}I$ für jeden Term ${}t$, da ja der Vordersatz nicht gilt. Wenn hingegen ${}\alpha \in \Gamma$ gilt, so gibt es aufgrund des semantischen Aufbaus der Gültigkeitbeziehung ein ${}m\in M$ derart, dass ${}I{\frac {m}{x}}\vDash \beta$ gilt. Wegen der vorausgesetzten Surjektivität der Belegung gibt es einen Term ${}t$, der durch ${}m$ interpretiert wird. Daher gilt nach dem Substitutionslemma ${}\beta {\frac {t}{x}}$ in ${}I$. Also gilt ${}\exists x\beta \rightarrow \beta {\frac {t}{x}}$ in ${}I$.

 

Aufgabe (2 Punkte)

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

Lösung

S-Homomorphismus/Mathematisches Beispiel/Aufgabe/Lösung

 

Aufgabe * (3 Punkte)

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

Lösung

 

Aufgabe (3 Punkte)

Erläutere die Churchsche These.

Lösung

Churchsche These/Erläutere/Aufgabe/Lösung

 

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.

Lösung

Es sei ${}R=\mathbb {N}$, ${}\alpha =\exists y{\left(x=y+0\right)}$ und ${}\beta =\exists y{\left(x=y+1\right)}$. Wir setzen

${}\Gamma =\{\alpha \leftrightarrow \beta ,\alpha {\frac {0}{x}},\alpha {\frac {1}{x}},\alpha {\frac {1+1}{x}},\alpha {\frac {1+1+1}{x}},{\rm {{etc}\}\,.}}$

Der Ausdruck ${}\alpha$ repräsentiert in ${}\Gamma$ die volle Relation ${}R=\mathbb {N}$, da ja für jedes ${}n\in \mathbb {N}$ gilt ${}n\in R$, aber auch ${}\Gamma \vdash \alpha {\frac {n}{x}}$. Ferner gilt ${}\Gamma \vdash \alpha \leftrightarrow \beta$. Wir behaupten, dass ${}\beta$ nicht die Relation in ${}\Gamma$ repräsentiert, wobei wir ${}\Gamma \not \vdash \beta {\frac {0}{x}}$ nachweisen wollen. Um diese Nichtableitbarkeit zu zeigen, müssen wir aufgrund des Korrektheitssatzes eine Interpretation angeben, für die ${}\Gamma$ gilt, aber ${}\beta {\frac {0}{x}}$ nicht gilt. Dazu wählen wir als Grundmenge ${}\mathbb {Z}$, wobei wir die ${}0,1$ und die Multiplikation (die keine Rolle spielt) natürlich interpretieren, und wo wir die Addition auf ${}\mathbb {N}$ natürlich interpretieren und ${}m+n=-2$ setzen, sobald ein Summand negativ ist. Die Variable ${}x$ wird als ${}-1$ interpretiert. Bei dieser Interpretation gilt dann weder ${}\alpha$ noch ${}\beta$, da ${}-1$ überhaupt nicht als Wert der gewählten Addition auftaucht. Daher gilt wiederum die Äquivalenz ${}\alpha \leftrightarrow \beta$ bei dieser Interpretation. Die Ausdrücke ${}\alpha {\frac {n}{x}}$ für ${}n\in \mathbb {N}$ gelten bei der Interpretation, der Ausdruck ${}\beta {\frac {0}{x}}$ bedeutet ${}\exists y{\left(0=y+1\right)}$ und gilt hingegen nicht, da bei ${}y\geq 0$ der Wert von ${}y+1$ größer als ${}0$ ist und bei ${}y<0$ der Wert nach Definition gleich ${}-2\neq 0$ ist.