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

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

Aufgabe (3 Punkte)

Lösung

1. Eine Primzahl der Form ${}2^{n}-1$ heißt Mersennesche Primzahl.
2. Die ${}S$- Ausdrücke werden folgendermaßen als gültig charakterisiert (dabei seien ${}s,t,t_{1},\ldots ,t_{n}$ Terme und ${}\alpha ,\beta$ Ausdrücke).
   1. ${}I\vDash s=t$, wenn ${}I(s)=I(t)$.
   2. ${}I\vDash Rt_{1}\ldots t_{n}$, wenn ${}(I(t_{1}),\ldots ,I(t_{n}))\in R^{M}$.
   3. ${}I\vDash \neg {\left(\alpha \right)}$, wenn nicht ${}I\vDash \alpha$ gilt.
   4. ${}I\vDash {\left(\alpha \right)}\wedge {\left(\beta \right)}$, wenn ${}I\vDash \alpha$ und ${}I\vDash \beta$ gilt.
   5. ${}I\vDash {\left(\alpha \right)}\rightarrow {\left(\beta \right)}$, wenn die Gültigkeit ${}I\vDash \alpha$ die Gültigkeit ${}I\vDash \beta$ impliziert.
   6. ${}I\vDash \exists x\alpha$, wenn es ein ${}m\in M$ gibt mit ${}I{\frac {m}{x}}\vDash \alpha$.
   7. ${}I\vDash \forall x\alpha$, wenn für alle ${}m\in M$ die Beziehung ${}I{\frac {m}{x}}\vDash \alpha$ gilt.

3. $\varphi \colon M\longrightarrow N$

   heißt ${}S$-Isomorphismus, wenn ${}\varphi$ bijektiv ist und sowohl ${}\varphi$ als auch die Umkehrabbildung ${}\varphi ^{-1}$ ein ${}S$- Homomorphismus ist.

4. Man sagt, dass ${}T$ ${}R$-aufzählbar ist, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei Eingabe von ${}0$ nach und nach genau die Zahlen aus ${}T$ ausdruckt.
5. Das modallogische Axiomenschema

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

   nennt man Transitivitätsaxiom.

6. Die Gültigkeit wird rekursiv wie folgt definiert: Es sei der modallogische Ausdruck ${}\alpha$ schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt ${}w\in M$

   $w\vDash \Box \alpha$

   genau dann, wenn in jeder von ${}w$ aus erreichbaren Welt ${}v$ die Beziehung

   $v\vDash \alpha$

   gilt.

Aufgabe (3 Punkte)

Lösung

1. Es sei ${}V$ eine abzählbare Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Dann kann man ${}\Gamma$ durch sukzessive Hinzunahme von entweder ${}p_{n}$ oder ${}\neg p_{n}$ und durch Abschluss unter der Ableitungsbeziehung zu einer maximal widerspruchsfreien Teilmenge ${}\Gamma '\supseteq \Gamma$ ergänzen.
2. Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$- Term und ${}\alpha$ ein ${}U$- Ausdruck. Es seien zwei ${}S$- Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Dann gelten folgende Aussagen.
   1. Es ist ${}I_{1}(t)=I_{2}(t)$.
   2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$.
3. Es sei ${}\Gamma$ eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge ${}\Gamma ^{\vdash }$ (also die Menge der zugehörigen Gödelnummern) sei schwach repräsentierbar in ${}\Gamma$. Dann gibt es einen arithmetischen Satz ${}q\in L_{0}^{\rm {Ar}}$ derart, dass weder ${}q$ noch seine Negation ${}\neg q$ aus ${}\Gamma$ ableitbar ist.

Aufgabe (2 Punkte)

Ein Mann steht mit einem Wolf, einer Ziege und einem Kohl am Ufer eines Flusses und möchte diesen überqueren. Es steht ein Boot zur Verfügung, in dem neben ihm nur ein weiterer Passagier Platz hat. Wie kann er den Fluss überqueren, ohne dass dabei der Wolf die Ziege oder die Ziege den Kohl frisst?

Lösung

1. Er fährt mit der Ziege ans andere Ufer.
2. Er fährt allein zurück.
3. Er fährt mit dem Wolf ans andere Ufer.
4. Er fährt mit der Ziege zurück.
5. Er fährt mit dem Kohl ans andere Ufer.
6. Er fährt allein zurück.
7. Er fährt mit der Ziege ans andere Ufer.

Aufgabe (1 Punkt)

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

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

Lösung

${}q$.

Aufgabe (2 Punkte)

Beweise die aussagenlogische Tautologie

$\vdash \alpha \rightarrow (\beta \rightarrow \alpha \wedge \beta )$

aus den aussagenlogischen Axiomen.

Lösung

Es ist

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

nach Lemma 3.11 (Einführung in die mathematische Logik (Osnabrück 2021)) und

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

nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (4). Modus ponens liefert

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

Aufgabe (5 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Es sei ${}\Gamma$ widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable ${}p\in V$ gelte ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$. Zeige, dass dann ${}\Gamma$ maximal widerspruchsfrei ist.

Lösung

Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes ${}\alpha \in L^{V}$ die Alternative ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für ${}\alpha =p$ eine Aussagenvariable ist dies Teil der Voraussetzung. Bei ${}\alpha =\neg \beta$ folgt wegen ${}\vdash \neg {\left(\neg \beta \right)}\leftrightarrow \beta$ die Aussage aus der Induktionsvoraussetzung, da ${}\Gamma$ abgeschlossen unter Ableitungen ist. Es sei nun ${}\alpha =\beta \wedge \gamma$. Bei ${}\beta \in \Gamma$ und ${}\gamma \in \Gamma$ ist wegen der Ableitungsabgeschlossenheit auch ${}\beta \wedge \gamma \in \Gamma$. Wenn hingegen ${}\beta \notin \Gamma$ ist, so folgt nach der Induktionsvoraussetzung ${}\neg \beta \in \Gamma$. Aufgrund der Tautologie ${}\vdash \neg \beta \rightarrow \neg {\left(\beta \wedge \gamma \right)}$ ergibt sich ${}\neg \alpha =\neg {\left(\beta \wedge \gamma \right)}\in \Gamma$. Der Beweis für die Implikation verläuft ähnlich, siehe Aufgabe 4.16 (Einführung in die mathematische Logik (Osnabrück 2021)).

Zum Nachweis, dass ${}\Gamma$ maximal widerspruchsfrei ist, sei ${}\alpha \notin \Gamma$ angenommen. Nach dem, was wir eben bewiesen haben, gilt dann ${}\neg \alpha \in \Gamma$. Dann ist aber ${}\alpha ,\neg \alpha \in \Gamma \cup \{\alpha \}$ und somit ist diese erweiterte Menge widersprüchlich.

Aufgabe (1 Punkt)

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.

Lösung

Es gibt eine Hochzeit, auf der Lucy Sonnenschein nicht tanzt.

Aufgabe (2 Punkte)

Es seien ${}x,y,z,w$ Variablen und ${}V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

1. ${}VxyzVVw$,
2. ${}VVxyVzw$,
3. ${}VVxyzVw$,
4. ${}VxVyVzw$,
5. ${}xVyVzVw$,
6. ${}VVVxyzw$,
7. ${}VxyVVzw$,
8. ${}VVxVyzw$,
9. ${}VxyVzw$,
10. ${}VxVyzVw$,
11. ${}VxVVyzw$,
12. ${}VxyVzVw$.

Lösung

Terme sind ${}2,4,6,8,11$, die anderen sind keine Terme.

Aufgabe (2 Punkte)

Man erläutere für einen Ableitungskalkül den Unterschied zwischen einer syntaktischen Grundtautologie und einer Ableitungsregel.

Lösung Ableitungskalkül/Tautologie und Regel/Aufgabe/Lösung

Aufgabe (8 Punkte)

Es seien ${}x,y$ Variablen, ${}s,t$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Es seien ${}u,v$ neue Variablen, die weder in ${}s$ noch in ${}t$ noch in ${}\alpha$ vorkommen. Zeige, dass

$\alpha {\frac {s,t}{x,y}}\leftrightarrow \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}{\frac {y}{v}}$

allgemeingültig ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen (von links nach rechts) zu lesen ist.

Lösung

Es sei ${}I$ eine Interpretation mit

$I\vDash \alpha {\frac {s,t}{x,y}}.$

Nach dem Substitutionslemma bedeutet dies

$I{\frac {I(s),I(t)}{x,y}}\vDash \alpha .$

Von der anderen Seite her ist

$I\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}{\frac {y}{v}}$

mit dem Substitutionslemma äquivalent zu

$I{\frac {I(y)}{v}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}.$

Dies ist äquivalent zu

$I{\frac {I(y)}{v}}{\frac {I{\frac {I(y)}{v}}(x)}{u}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}},$

und wegen ${}I{\frac {I(y)}{v}}(x)=I(x)$ kann man dies als

$I{\frac {I(y),I(x)}{v,u}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}$

schreiben. Wir nennen die Interpretation links ${}J$. Mit dem Substitutionslemma ist dies äquivalent zu

$J{\frac {J(t{\frac {u}{x}})}{y}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}.$

Nach dem Substitutionslemma für Terme ist

${}J{\left(t{\frac {u}{x}}\right)}=J{\frac {J(u)}{x}}(t)\,.$

Dabei ist

${}J(u)={\left(I{\frac {I(y),I(x)}{v,u}}\right)}(u)=I(x)\,$

und somit ist

${}J{\frac {J(u)}{x}}(t)={\left(I{\frac {I(y),I(x)}{v,u}}\right)}{\frac {I(x)}{x}}(t)={\left(I{\frac {I(y),I(x)}{v,u}}\right)}(t)=I(t)\,.$

Zusammengefasst ist also

$I{\frac {I(y),I(x),I(t)}{v,u,y}}\vDash \alpha {\frac {s{\frac {v}{y}}}{x}}.$

Die Interpretation links nennen wir wieder ${}J$. Nach dem Substitutionslemma ist

$J{\frac {J{\left(s{\frac {v}{y}}\right)}}{x}}\vDash \alpha .$

Dabei ist

${}J{\left(s{\frac {v}{y}}\right)}={\left(J{\frac {J(v)}{y}}\right)}(s)\,$

und wir haben

${}J(v)={\left(I{\frac {I(y),I(x),I(t)}{v,u,y}}\right)}(v)=I(y)\,.$

Daher ist

${}J{\left(s{\frac {v}{y}}\right)}=J{\frac {I(y)}{y}}(s)=I{\frac {I(y),I(x),I(t)}{v,u,y}}{\frac {I(y)}{y}}(s)=I{\frac {I(y),I(x),I(t)}{v,u,y}}(s)=I(s)\,.$

Also ist insgesamt

${}J{\frac {J{\left(s{\frac {v}{y}}\right)}}{x}}=J{\frac {I(s)}{x}}=I{\frac {I(y),I(x),I(t)}{v,u,y}}{\frac {I(s)}{x}}=I{\frac {I(y),I(x),I(s),I(t)}{v,u,x,y}}\,$

und

$I{\frac {I(y),I(x),I(s),I(t)}{v,u,x,y}}\vDash \alpha .$

Nach dem Koinzidenzlemma ist dies äquivalent zu

$I{\frac {I(s),I(t)}{x,y}}\vDash \alpha ,$

da ${}u$ und ${}v$ in ${}\alpha$ nicht vorkommen. Dies stimmt mit der eingangs erzielten Formulierung überein.

Aufgabe (3 Punkte)

Zeige

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

Lösung

Die Alleinführung im Antezedens ergibt

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

und

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

und daraus zusammen mit Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021))  (2)

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

Die Variable ${}x$ ist sowohl vorne als auch in ${}\forall x{\left(\alpha \wedge \beta \right)}$ gebunden. Daher ergibt die Alleinführung im Sukzedens

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

Aufgabe (4 Punkte)

Zeige, dass die Vorgängereigenschaft

$\forall x{\left(x\neq 0\rightarrow \exists y(x=Ny)\right)}$

aus der Menge der Peano-Axiome für den Nachfolger folgt.

Lösung

Es sei ${}M$ eine Menge mit ${}0$ und einer Abbildung ${}N\colon M\rightarrow M$, die die erststufigen Peano-Axiome für die Nachfolgerabbildung erfüllt, und es sei

${}\alpha :=x\neq 0\rightarrow \exists y(x=Ny)\,.$

Wir möchten ${}\forall x\alpha$ zeigen. Dabei handelt es sich um einen erststufig mit der Symbolmenge ${}\{0,N\}$ formulierten Ausdruck, sodass wir ihn durch Induktion beweisen können. Für ${}x=0$ aus ${}M$ ist der Vordersatz falsch und die Gesamtaussage richtig. Es sei nun ${}x\neq 0$ und die Aussage für ${}x$ richtig, d.h. es gelte ${}\exists y(x=Ny)$. Dann gilt direkt

${}N(x)=N(Ny))\,$

und somit wiederum ${}\exists z(Nx=Nz)$. Die Gesamtaussage ist also auch für ${}N(x)$ richtig und es ergibt sich die Gültigkeit für alle ${}x$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (10 Punkte)

Beweise den Fixpunktsatz der Prädikatenlogik.

Lösung

Wir betrachten die Abbildung

$F\colon \mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(m,n)\longmapsto F(m,n),$

die durch

$F(m,n):={\begin{cases}GN(\alpha (n)),\,{\text{ falls }}m{\text{ die }}GN{\text{ eines }}\alpha \in L_{1}^{\rm {Ar}}{\text{ ist}}\,,\\0{\text{ sonst}}\,,\end{cases}}\,$

festgelegt ist. Bei der Berechnung von ${}F$ wird also zuerst geschaut, ob das erste Argument, also ${}m$, die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist ${}F(m,n)=0$, unabhängig von ${}n$. Falls ja, so ist also ${}m=GN(\alpha )$ mit ${}\alpha \in L_{1}^{\rm {Ar}}$. In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also ${}n$, ersetzt, wobei man einen Satz ${}\alpha (n)$ erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung ${}F(m,n)$. In diesem Fall ist also ${}F(m,n)=GN(\alpha (n))$. Diese Erläuterungen zeigen zugleich, dass ${}F$ berechenbar ist.
Da ${}\Gamma$ nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck ${}\varphi (x,y,z)$ mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen ${}m,n,k$ die Beziehungen (wir können annehmen, dass ${}\Gamma$ widerspruchsfrei ist, da andernfalls das Resultat trivial ist)

$F(m,n)=k{\text{ genau dann, wenn }}\Gamma \vdash \varphi (m,n,k),$

$F(m,n)\not =k{\text{ genau dann, wenn }}\Gamma \vdash \neg \varphi (m,n,k)$

und (für jede Belegung ${}m,n$ für ${}x$ und ${}y$)

$\Gamma \vdash \exists !z\varphi (m,n,z).$

Den Fixpunkt zu einem vorgegebenen ${}\alpha \in L_{1}^{\rm {Ar}}$ erhalten wir nun durch eine trickreiche Anwendung von ${}\varphi$. Wir setzen

${}s:=\forall z{\left(\varphi (x,x,z)\rightarrow \alpha (z)\right)}\,.$

Der Ausdruck ${}s$ besitzt die Gödelnummer ${}GN(s)$. Wir behaupten nun, dass der Satz

${}q:=s{\frac {GN(s)}{x}}=\forall z{\left(\varphi (GN(s),GN(s),z)\rightarrow \alpha (z)\right)}\,$

die zu beweisende Ableitungsbeziehung ${}\Gamma \vdash q\leftrightarrow \alpha (GN(q))$ erfüllt.
Der Ausdruck ${}s$ besitzt die einzige freie Variable ${}x$, daher gilt

${}F(GN(s),GN(s))=GN{\left(s{\frac {GN(s)}{x}}\right)}=GN(q)\,.$

Aufgrund der Repräsentierungseigenschaft ist daher

$\Gamma \vdash \varphi (GN(s),GN(s),GN(q)).$

Aus der Allaussage ${}q$ erhält man durch Spezialisierung (man ersetzt die Variable ${}z$ durch den Term $GN(q)$)

$\vdash q\rightarrow {\left(\varphi (GN(s),GN(s),GN(q))\rightarrow \alpha (GN(q))\right)}.$

Da das Antezedens der rechten Implikation aus ${}\Gamma$ ableitbar ist, folgt

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

 Dies besagt also die Ableitbarkeit der Hinrichtung.

Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu

$\Gamma \vdash \forall z{\left(\varphi (GN(s),GN(s),z)\rightarrow (z=GN(q))\right)}.$

Durch Substitution ergibt sich

$\vdash (z=GN(q))\rightarrow (\alpha (GN(q))\rightarrow \alpha (z))$

und somit nach einer prädikatenlogischen Umformulierung

$\Gamma \vdash \forall z{\left(\varphi (GN(s),GN(s),z)\wedge \alpha (GN(q))\rightarrow \alpha (z)\right)}.$

Da hierbei ${}\alpha (GN(q))$ keine freie Variablen besitzt, ist auch

$\Gamma \vdash \alpha (GN(q))\rightarrow {\left(\forall z(\varphi (GN(s),GN(s),z)\rightarrow \alpha (z))\right)},$

und das Sukzedens ist gerade ${}q$, sodass auch die Rückrichtung ableitbar ist.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Es sei ${}M$ ein ${}K$- modallogisches System, in dem zusätzlich das Transitivitätsaxiom gelte. Ferner sei ${}s$ ein modallogischer Ausdruck, für den

$M\vdash \neg \Box s\leftrightarrow s$

gelte. Zeige für einen beliebigen Ausdruck ${}p$ die Ableitbarkeit

$M\vdash \neg \Box (p\wedge \neg p)\rightarrow \neg \Box s.$

Lösung

Aus der Fixpunkteigenschaft

$M\vdash \neg \Box s\leftrightarrow s$

ergibt sich insbesondere

$M\vdash \Box s\rightarrow \neg s.$

Mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1) folgt

$M\vdash \Box \Box s\rightarrow \Box \neg s.$

Mit dem Transitivitätsaxiom und dem Kettenschluss folgt

$M\vdash \Box s\rightarrow \Box \neg s.$

Dies zusammen mit der Tautologie

$\vdash \Box s\rightarrow \Box s$

ergibt

$\vdash \Box s\rightarrow \Box s\wedge \Box \neg s.$

Mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) haben wir

$M\vdash \Box s\wedge \Box \neg s\rightarrow \Box (s\wedge \neg s)$

und somit

$M\vdash \Box s\rightarrow \Box (s\wedge \neg s).$

Für ein beliebiges ${}p$ ist nun

$\vdash s\wedge \neg s\rightarrow p\wedge \neg p$

und somit durch Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)

$M\vdash \Box (s\wedge \neg s)\rightarrow \Box (p\wedge \neg p)$

und insgesamt

$M\vdash \Box s\rightarrow \Box (p\wedge \neg p),$

was durch Kontraposition die Behauptung ergibt.