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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine widersprüchliche Ausdrucksmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$.
2. Die Produktmenge aus zwei Mengen ${}L$ und ${}M$.
3. Die Ableitbarkeit eines Ausdrucks ${}\alpha \in L^{S}$ im prädikatenlogischen Kalkül.
4. Die Repräsentierbarkeit einer Funktion

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

   in einer Menge ${}\Gamma$ von arithmetischen Ausdrücken.

5. Das modallogische Möglichkeitsaxiom.
6. Die Nachfolgermenge in einem gerichteten Graphen.

Lösung

1. Die Ausdrucksmenge ${}\Gamma$ heißt widersprüchlich, wenn es einen Ausdruck ${}\alpha \in L^{V}$ mit ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$ gibt.
2. Man nennt die Menge

   ${}L\times M={\left\{(x,y)\mid x\in L,\,y\in M\right\}}\,$

   die Produktmenge der Mengen ${}L$ und ${}M$.

3. Der Ausdruck ${}\alpha$ heißt ableitbar, wenn er sich aus den Grundtautologien, also
   • den aussagenlogischen syntaktischen Tautologien,
   • den Gleichheitsaxiomen,
   • der Existenzeinführung im Sukzedens,

durch sukzessive Anwendung der Ableitungsregeln Modus ponens und der Existenzeinführung im Antezedens erhalten lässt.

Die Funktion ${}F$ heißt repräsentierbar in ${}\Gamma$, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die folgenden Eigenschaften

1. Wenn ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$, so ist ${}\Gamma \vdash \psi (n_{1},\ldots ,n_{r+s})$,
2. Wenn ${}F(n_{1},\ldots ,n_{r})\neq (n_{r+1},\ldots ,n_{r+s})$, so ist ${}\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r+s})$,
3. ${}\Gamma \vdash \exists !x_{r+1}\ldots \exists !x_{r+s}\psi (n_{1},\ldots ,n_{r},x_{r+1},\ldots ,x_{r+s})$,

gelten.

Das modallogische Axiomenschema

$\Box \alpha \rightarrow \Diamond \alpha$

nennt man Möglichkeitsaxiom.

Zu einer Teilmenge ${}T\subseteq M$ in einem gerichteten Graphen ${}(M,R)$ nennt man

${}\operatorname {Nachf} {\left(T\right)}={\left\{z\in M\mid {\text{ es gibt }}y\in T{\text{ mit }}yRz\right\}}\,$

die Nachfolgermenge zu ${}T$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Vorgängereigenschaft in einem Peano-Halbring.
2. Der Endlichkeitssatz für die Prädikatenlogik.
3. Die Unentscheidbarkeit der Arithmetik.

Lösung

1. In einem Peano-Halbring ${}M$ gilt für jedes ${}x\in M$ die Eigenschaft: Entweder ist ${}x=0$ oder es gibt ein ${}u\in M$ mit ${}x=u+1$.
2. Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$-Ausdrücken und ${}\alpha$ ein weiterer ${}S$-Ausdruck. Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn es eine endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ gibt mit ${}\Gamma _{e}\vDash \alpha$.
3. Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht ${}R$- entscheidbar.

Aufgabe (1 Punkt)

In einer psychologischen Längsschnittstudie wird die Entwicklung von Einstellungen und Verhaltensweisen von Personen untersucht. Ein Fallbeispiel: Im Alter von ${}20$ Jahren geht Linda regelmäßig auf Demonstrationen, sie hilft im Eine-Welt-Laden mit, braut ökologisches Bier, kocht Bio-Gemüse und studiert manchmal Soziologie.

Welcher der folgenden Befunde ist nach 10 Jahren am unwahrscheinlichsten?

1. Linda arbeitet für eine Versicherungsagentur.
2. Linda engagiert sich bei Attac und arbeitet für eine Versicherungsagentur.
3. Linda engagiert sich bei Attac.

Lösung

(2) ist am unwahrscheinlichsten. Dass zwei Ereignisse gleichzeitig eintreffen ist stets unwahrscheinlicher als die beiden einzelnen Ereignisse.

Aufgabe (3 Punkte)

Erläutere das Prinzip Beweis durch Widerspruch für eine Aussage der Form „Aus ${}A$ folgt ${}B$“.

Lösung

Man möchte zeigen, dass aus einer Aussage ${}A$ eine weitere Aussage ${}B$ folgt. Beim Beweis durch Widerspruch nimmt man an, dass gleichzeitig ${}A$ und nicht ${}B$ gelten. Unter diesen Voraussetzungen zeigt man, dass sich ein Widerspruch ergibt. Dies bedeutet, dass ${}A$ und nicht ${}B$ nicht gleichzeitig gelten können, was eben die Implikation ${}A\implies B$ bedeutet.

Aufgabe (3 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge ${}V$ und es sei ${}\alpha \in L^{V}$. Es gelte

$\Gamma \not \vdash \alpha .$

Zeige, dass dann

$\Gamma \cup \{\neg \alpha \}$

widerspruchsfrei ist.

Lösung

Nehmen wir an, dass ${}\Gamma \cup \{\neg \alpha \}$ widersprüchlich ist. Dann ist ${}\Gamma \cup \{\neg \alpha \}\vdash \alpha$, da aus einer widersprüchlichen Menge alles ableitbar ist. Nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021)) ist dann ${}\Gamma \vdash \neg \alpha \rightarrow \alpha$. Wegen der Tautologie ${}\vdash \alpha \rightarrow \alpha$ folgt mit der Fallunterscheidungsregel ${}\Gamma \vdash \alpha$.

Aufgabe (2 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben, ${}\alpha \in L^{S}$ und ${}I$ eine Interpretation mit ${}I\vDash \alpha$. Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit ${}I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ unter einer Substitution folgt.

Lösung

Die Sprache enthalte Konstanten ${}c\neq d$ und es sei eine Interpretation mit ${}I(c)\neq I(d)$ gegeben. Die Variable ${}x$ sei bei der Interpretation durch ${}I(c)$ belegt. Dann gilt ${}I\vDash x=c$. Die Substitution ${}{\frac {d}{x}}$ führt den Ausdruck ${}x=c$ in ${}d=c$ über, und dieser gilt nicht unter der Interpretation.

Aufgabe (4 Punkte)

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen

$x+0=x{\text{ für alle }}x\in \mathbb {N} {\text{ und }}x+y'=(x+y)'{\text{ für alle }}x,y\in \mathbb {N}$

eindeutig bestimmt ist.

Lösung

Die Addition erfüllt nach Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (1, 2) diese Eigenschaften.

Es seien zwei Verknüpfungen ${}+$ und ${}*$ auf ${}\mathbb {N}$ gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit

${}x+y=x*y\,$

für alle ${}x,y\in \mathbb {N}$ beweisen. Dies machen wir durch Induktion über ${}y$ (für beliebige ${}x$). Bei

${}y=0\,$

ist wegen

${}x+0=x=x*0\,$

die Aussage richtig. Es sei die Aussage nun für ein bestimmtes ${}y$ schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung

${}x+y^{\prime }=(x+y)^{\prime }=(x*y)^{\prime }=x*y^{\prime }\,.$

Aufgabe (4 (1+1+1+1) Punkte)

Es sei ${}(M,\preccurlyeq )$ eine nichtleere geordnete Menge. Wir betrachten die Relation ${}\prec$ auf ${}M$, die durch ${}x\prec y$, falls ${}x\preccurlyeq y$ und ${}x\neq y$ gilt, definiert ist.

1. Ist ${}\prec$ transitiv?
2. Ist ${}\prec$ reflexiv?
3. Charakterisiere, wann ${}\prec$ symmetrisch ist.
4. Ist ${}\prec$ antisymmetrisch?

Lösung

1. Sei ${}x\prec y$ und ${}y\prec z$. Das bedeutet ${}x\preccurlyeq y$ und ${}y\preccurlyeq z$ und somit ist wegen der Transitivität von ${}\preccurlyeq$ auch ${}x\preccurlyeq z$. Wäre ${}x=z$, so wäre wegen der Antisymmetrie von ${}\preccurlyeq$ auch ${}x=y$, was den Voraussetzungen widerspricht.
2. Die Relation ${}\prec$ ist nicht reflexiv, da ${}x\prec y$ die Verschiedenheit von ${}x$ und ${}y$ beinhaltet.
3. Die Relation ${}\prec$ ist nicht symmetrisch, außer wenn ${}\preccurlyeq$ die Identität ist. In diesem Fall ist nämlich ${}\prec$ die leere Relation, und diese ist symmetrisch. Wenn es hingegen ein Paar ${}x\preccurlyeq y$ mit ${}x\neq y$ gibt, so ist ${}x\prec y$, aber nicht umgekehrt.
4. Die Relation ${}\prec$ ist antisymmetrisch. Sei ${}x\prec y$ und ${}y\prec x$. Dann ist insbesondere${}x\preccurlyeq y$ und ${}y\preccurlyeq x$ und die Antisymmetrie der Ordnungsrelation impliziert ${}x=y$. Doch dies ist ein Widerspruch zur Voraussetzung. D.h. die Voraussetzung in der Eigenschaft Antisymmetrie kann gar nicht erfüllt sein und daher ist die Antisymmetrie erfüllt.

Aufgabe (8 Punkte)

Beweise den Satz von Henkin.

Lösung

Es sei ${}M$ das konstruierte Modell zu ${}\Gamma$ und ${}I$ die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

$\alpha \in \Gamma {\text{ genau dann, wenn }}I\vDash \alpha$

für alle Ausdrücke ${}\alpha$, durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von ${}\alpha$ gleich ${}0$, also ${}\alpha$ atomar. D.h. ${}\alpha$ ist entweder von der Form ${}s=t$ oder ${}Rt_{1}\ldots t_{n}$. Im ersten Fall ist ${}s=t\in \Gamma$ äquivalent zu ${}s\sim t$ bzw. ${}[s]=[t]$ in ${}M$. Dies ist nach Lemma 14.9 (Einführung in die mathematische Logik (Osnabrück 2021)) äquivalent zu ${}I(s)=I(t)$ und das bedeutet ${}I\vDash s=t$.

Im zweiten Fall ist ${}Rt_{1}\ldots t_{n}\in \Gamma$ - nach Konstruktion von ${}M$ und ${}R^{M}$ - äquivalent zu ${}R^{M}([t_{1}],\ldots ,[t_{n}])$, und dies ist äquivalent zu ${}I\vDash Rt_{1}\ldots t_{n}$.

Es sei nun die Aussage für alle Ausdrücke vom Rang ${}\leq r$ bewiesen und sei ${}\alpha$ ein Ausdruck vom Rang ${}r+1$. Wir betrachten die mögliche Struktur von ${}\alpha$ gemäß Definition .. Bei

${}\alpha =\neg \beta \,$

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung (${}\beta$ hat kleineren Rang als ${}\alpha$) und Lemma 14.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (1). Bei

${}\alpha =\beta _{1}\wedge \beta _{2}\,$

besitzen die beiden Bestandteile kleineren Rang als ${}\alpha$. Die Zugehörigkeit ${}\alpha \in \Gamma$ ist nach Lemma 14.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (3) äquivalent zur gemeinsamen Zugehörigkeit ${}\beta _{1},\beta _{2}\in \Gamma$. Nach Induktionsvoraussetzung bedeutet dies ${}I\vDash \beta _{1}$ und ${}I\vDash \beta _{2}$. Dies bedeutet wiederum ${}I\vDash \beta _{1}\wedge \beta _{2}$ aufgrund der Modellbeziehung. Bei

${}\alpha =\exists x\beta \,$

besitzt wieder ${}\beta$ einen kleineren Rang. Die Zugehörigkeit ${}\alpha \in \Gamma$ ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) äquivalent zur Existenz eines Terms ${}t$ und der Zugehörigkeit ${}\beta {\frac {t}{x}}\in \Gamma$. Die Substitution von ${}\beta$ nach ${}\beta {\frac {t}{x}}$ verändert nach Aufgabe 14.17 (Einführung in die mathematische Logik (Osnabrück 2021)) nicht den Rang. Wir können also auf ${}\beta {\frac {t}{x}}$ die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu ${}I\vDash \beta {\frac {t}{x}}$. Nach dem Substitutionslemma ist dies äquivalent zu ${}I{\frac {I(t)}{x}}\vDash \beta$ bzw. ${}I{\frac {[t]}{x}}\vDash \beta$ wegen Lemma 14.9 (Einführung in die mathematische Logik (Osnabrück 2021)). Dies ist äquivalent zu ${}I\vDash \exists x\beta$ aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.

Aufgabe (2 Punkte)

Zeige, dass mit

$\vdash \alpha \rightarrow \beta$

auch

$\vdash \forall x\alpha \rightarrow \forall x\beta$

gilt.

Lösung

Aus der ableitbaren Implikation

$\vdash \alpha \rightarrow \beta$

ergibt sich mittels der Alleinführung im Antezedens

$\vdash \forall x\alpha \rightarrow \alpha$

und dem Kettenschluss

$\vdash \forall x\alpha \rightarrow \beta$

und daraus mit der Alleinführung im Sukzedens, die anwendbar ist, da ${}x$ vorne und in ${}\forall x\beta$ gebunden ist,

$\vdash \forall x\alpha \rightarrow \forall x\beta .$

Aufgabe (2 Punkte)

Zeige

$\vdash \forall x{\left(\alpha \wedge \beta \right)}\rightarrow \forall x\alpha \wedge \forall x\beta .$

Lösung

Es ist

$\vdash \alpha \wedge \beta \rightarrow \alpha$

aufgrund einer aussagenlogischen Tautologie. Nach Aufgabe 11.7 (Einführung in die mathematische Logik (Osnabrück 2021)) ergibt sich

$\vdash \forall x{\left(\alpha \wedge \beta \right)}\rightarrow \forall x\alpha$

und ebenso

$\vdash \forall x{\left(\alpha \wedge \beta \right)}\rightarrow \forall x\beta .$

Dies zusammengenommen ergibt

$\vdash \forall x{\left(\alpha \wedge \beta \right)}\rightarrow \forall x\alpha \wedge \forall x\beta .$

Aufgabe (4 Punkte)

Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.

Lösung

Aufgrund von Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)), angewendet auf ${}N_{1}$ und die Nachfolgerabbildung auf ${}N_{2}$, gibt es genau eine Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2}$

mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung

$\psi \colon N_{2}\longrightarrow N_{1}$

mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung

$\psi \circ \varphi \colon N_{1}\longrightarrow N_{1}.$

Diese erfüllt ebenfalls diese Eigenschaften. Da aber die Identität auf ${}N_{1}$ auch diese Eigenschaften erfüllt, folgt aus der Eindeutigkeitsaussage aus Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)), dass ${}\psi \circ \varphi =\operatorname {Id} _{N_{1}}$ ist. Ebenso ist ${}\varphi \circ \psi =\operatorname {Id} _{N_{2}}$ und somit sind ${}\varphi$ und ${}\psi$ invers zueinander.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (6 (4+2) Punkte)

Es sei

${}S=\{0,1,+,\cdot ,\geq \}\,$

das Symbolalphabet für einen angeordneten Körper und es sei ${}\mathbb {R}$ die ${}S$- Struktur mit der Standardinterpretation.

1. Zeige, dass die Äquivalenzklassen zur elementaren Äquivalenz einelementig sind.
2. Zeige, dass es für die Elemente im Allgemeinen keinen charakterisierenden Ausdruck gibt.

Lösung

1. Es seien ${}r,s\in \mathbb {R}$ verschiedene reelle Zahlen. Für müssen zeigen, dass es einen ${}S$-Ausdruck in einer freien Variablen ${}x$ gibt, der gilt, wenn man ${}x$ durch ${}r$ interpretiert, aber nicht, wenn man ihn durch ${}s$ interpretiert. Ohne Einschränkung sei ${}r<s$. Wegen der Dichtheit der rationalen Zahlen ${}\mathbb {Q}$ in ${}\mathbb {R}$ gibt es eine rationale Zahl ${}q$ mit

   ${}r\leq q<s\,.$

   Sei ${}q={\frac {m}{n}}$. Dann bedeuten diese Ungleichungen ${}nr\leq m$ und ${}ns>m$. Somit ist der Ausdruck ${}nx\leq m$, der durch

   ${}\alpha :=x+\cdots +x\leq 1+\cdots +1\,$

   mit ${}n$ Summanden links und ${}m$ Summanden rechts realisiert wird, ein Ausdruck, der bei Interpretation von ${}x$ durch ${}r$ gilt, bei Interpretation durch ${}s$ aber nicht.

2. Da das Symbolalphabet abzählbar ist, gibt es überhaupt nur abzählbar viele Ausdrücke in der Sprache ${}L^{S}$. Da die reellen Zahlen überabzählbar sind, kann es also aus Anzahlgründen gar nicht für jede reelle Zahl einen charakterisierenden Ausdruck geben.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (5 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische euklidische Axiom genau dann gilt, wenn ${}R$ euklidisch ist.

Lösung

Es sei ${}(M,R)$ gegeben. Es sei zunächst ${}R$ euklidisch und sei

$w\vDash \Diamond \alpha .$

Somit gibt es eine Welt ${}v$ mit ${}wRv$ und mit

$v\vDash \alpha .$

Es sei ${}z$ eine Welt mit ${}wRz$. Nach der euklidischen Eigenschaft ist dann auch ${}zRv$, daher ist

$z\vDash \Diamond \alpha .$

Somit ist

$w\vDash \Box \Diamond \alpha .$

Es sei nun ${}R$ nicht euklidisch und seien ${}w,v,z\in M$ Punkte mit ${}wRv$, ${}wRz$, aber nicht ${}vRz$. Es sei ${}p$ eine Aussagenvariable und sei ${}\mu$ die Belegung, bei der ${}\neg p$ in allen von ${}v$ aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

$z\vDash p$

und somit

$w\vDash \Diamond p.$

In ${}v$ gilt hingegen ${}\Box \neg p$, also

$v\vDash \neg \Diamond p.$

Somit gilt

$w\vDash \neg \Box \Diamond p$

und damit

$w\not \vDash \Diamond p\rightarrow \Box \Diamond p.$