Kurs:Einführung in die mathematische Logik/9/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	1	6	3	2	8	0	4	6	4	3	0	3	0	6	52

Aufgabe (3 Punkte)

Lösung

1. Die Teilmenge ${}\Gamma \subseteq L^{V}$ heißt maximal widerspruchsfrei, wenn ${}\Gamma$ widerspruchsfrei ist und jede echt größere Menge ${}\Gamma \subset \Gamma '$ widersprüchlich ist.
2. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
   1. Wenn ${}t_{1}$ und ${}t_{2}$ Terme sind, so ist

      $t_{1}=t_{2}$

      ein Ausdruck.
   2. Wenn ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist

      $Rt_{1}{\ldots }t_{n}$

      ein Ausdruck.

   3. Wenn ${}\alpha$ und ${}\beta$ Ausdrücke sind, so sind auch

      $\neg {\left(\alpha \right)},\,{\left(\alpha \right)}\wedge {\left(\beta \right)},\,{\left(\alpha \right)}\vee {\left(\beta \right)},\,{\left(\alpha \right)}\rightarrow {\left(\beta \right)},\,{\left(\alpha \right)}\leftrightarrow {\left(\beta \right)}$

      Ausdrücke.

   4. Wenn ${}\alpha$ ein Ausdruck ist und ${}x$ eine Variable, so sind auch

      $\forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}$

      Ausdrücke.

3. Die Terminterpretation ${}I(t)\in M$ wird induktiv über den Aufbau der Terme für jeden ${}S$- Term ${}t$ definiert.
   1. Für jede Konstante ${}c$ und jede Variable ${}x$ ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also ${}I(c)=c^{M}$ und ${}I(x)=x^{M}$.
   2. Wenn ${}t_{1},\ldots ,t_{n}$ Terme mit Interpretationen ${}I(t_{1}),\ldots ,I(t_{n})$ sind und wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist, so wird der Term ${}ft_{1}\ldots t_{n}$ als ${}f^{M}(I(t_{1}),\ldots ,I(t_{n}))$ interpretiert.
4. Unter einem atomaren Ausdruck versteht man Ausdrücke der Form ${}s=t$, wobei ${}s$ und ${}t$ Terme sind, und der Form ${}Rt_{1}\ldots t_{n}$, wobei ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind.
5. Die Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N}$

   heißt ${}R$-berechenbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe ${}(r_{1},\ldots ,r_{k})$ (in den ersten ${}k$ Registern) anhält und ${}F(r_{1},\ldots ,r_{k})$ als (einzige) Ausgabe besitzt.

6. Unter dem Reflexivitätsaxiom versteht man das modallogische Axiomenschema

   $\Box \alpha \rightarrow \alpha .$

Aufgabe (3 Punkte)

Lösung

1. Es sei ${}M$ ein Peano-Halbring und ${}d\geq 1$. Dann gibt es zu jedem ${}m\in M$ eindeutig bestimmte ${}q,r\in M$ mit ${}r$, ${}r<d$, und mit

   ${}m=qd+r\,.$

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 ${}\Gamma \vdash \alpha$ gilt.
3. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube. Dann ist ${}\Gamma ^{\vdash }$ unvollständig.

Aufgabe (1 Punkt)

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

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

Lösung

${}p$.

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

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr ${}2015$ weiß man, dass ${}17$ Tage sockenzerstreut und ${}11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr ${}2013$ weiß man, dass ${}270$ Tage sockenzerstreut und ${}120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.

Lösung

a) Zerstreutheit: Die sockenzerstreuten Tage sind jedenfalls zerstreut. Das Minimum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind ${}17$. Das Maximum ergibt sich, wenn kein Tag gleichzeitig sockenzerstreut und schuhzerstreut war, das ergibt ${}28$ Tage.

Totale Zerstreutheit: Die total zerstreuten Tage sind insbesondere schuhzerstreut. Das Maximum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind ${}11$ Tage. Das Minimum ergibt sich, wenn kein Tag gleichzeitig schuh- und sockenzerstreut war, also ${}0$.

b) Wegen

${}270+120=390\geq 365\,$

können alle Jahre des Tages zerstreut gewesen sein, also ${}365$. Minimal waren ${}25$ Tage total zerstreut.

c) Es sei ${}s$ die Anzahl der sockenzerstreuten Tage, ${}x$ die Anzahl der schuhzerstreuten Tage, ${}z$ die Anzahl der zerstreuten Tage und ${}t$ die Anzahl der total zerstreuten Tage. Dann gilt die Formel

${}s+x=z+t\,.$

Beide Seiten der Formel sind additiv in den Tagen, sie muss also nur für einen Tag nachgewiesen werden. Wenn der Tag nicht zerstreut ist, steht beidseitig ${}0$. Wenn der Tag sockenzerstreut ist, aber nicht schuhzerstreut (oder umgekehrt), so ist der Tag zerstreut, aber nicht total zerstreut, und beidseitig steht ${}1$. Wenn der Tag total zerstreut ist, so steht beidseitig ${}2$.

Aufgabe (3 Punkte)

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.

Lösung Wohldefiniertheit/Typisches Beispiel/Aufgabe/Lösung

Aufgabe (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die folgende Regel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha _{1},\ldots ,\Gamma \vdash \alpha _{n}$ und ${}\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$, dann auch ${}\Gamma \vdash \beta$.

Lösung

Aus der Voraussetzung und der Konjunktionsregel (Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)) ergibt sich

$\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}.$

Daraus und aus der Voraussetzung

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

ergibt sich mittels Modus ponens (Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (3))

$\Gamma \vdash \alpha .$

Aufgabe (8 (3+5) Punkte)

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. Beweise die folgenden Aussagen.

1. Es ist ${}I_{1}(t)=I_{2}(t)$.
2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus ${}U$ und auf den in ${}\alpha$ frei vorkommenden Variablen identisch sind).

Lösung

(1). Wir führen Induktion über den Aufbau der ${}U$-Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus ${}U$ betrachten. Für eine Variable ${}x$ (oder eine Konstante) aus ${}U$ ist nach Voraussetzung ${}I_{1}(x)=I_{2}(x)$. Im Induktionsschritt können wir annehmen, dass ein ${}n$-stelliges Funktionssymbol ${}f$ aus ${}U$ gegeben ist sowie ${}U$-Terme ${}t_{1},\ldots ,t_{n}$, für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird ${}f$ in beiden Interpretationen durch die gleiche Funktion ${}f^{M}$ interpretiert. Daher ist

${}{\begin{aligned}I_{1}(ft_{1}\ldots t_{n})&=f^{M}(I_{1}(t_{1}),\ldots ,I_{1}(t_{n}))\\&=f^{M}(I_{2}(t_{1}),\ldots ,I_{2}(t_{n}))\\&=I_{2}(ft_{1}\ldots t_{n}).\end{aligned}}$

(2). Wir führen Induktion über den Aufbau der ${}U$-Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol ${}R$ aus ${}U$ folgt die Aussage unmittelbar aus (1), da ja ${}R$ in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form ${}\neg \alpha ,\,\alpha \wedge \beta ,\,\alpha \rightarrow \beta$ aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein ${}U$-Ausdruck der Form ${}\exists x\alpha$ gegeben, und es gelte ${}I_{1}\vDash \exists x\alpha$. Dies bedeutet aufgrund der Modellbeziehung, dass es ein ${}m\in M$ derart gibt, dass ${}I_{1}{\frac {m}{x}}\vDash \alpha$ gilt. Die beiden umbelegten Interpretationen ${}I_{1}{\frac {m}{x}}$ und ${}I_{2}{\frac {m}{x}}$ stimmen auf den Symbolen aus ${}U$ und den in ${}\alpha$ frei vorkommenden Variablen überein: Die Variable ${}x$ wird so oder so als ${}m$ interpretiert und die anderen freien Variablen aus ${}\alpha$ sind auch in ${}\exists x\alpha$ frei. Nach Induktionsvoraussetzung gilt ${}I_{2}{\frac {m}{x}}\vDash \alpha$ und daher wiederum ${}I_{2}\vDash \exists x\alpha$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Es seien ${}A,B,C$ einstellige Relationssymbole. Zeige, dass der Modus Darii, also die Aussage

$(\forall x(Ax\rightarrow Bx)\wedge \exists x(Ax\wedge Cx))\rightarrow (\exists x(Bx\wedge Cx))$

im Prädikatenkalkül ableitbar ist.

Lösung

Es gilt die aussagenlogische Ableitbarkeit

$\vdash (Ax\rightarrow Bx)\rightarrow {\left(Ax\wedge Cx\rightarrow Bx\wedge Cx\right)}.$

Dies fassen wir als eine Aussage vom Typ

$\vdash p\rightarrow (q\rightarrow r)$

auf. Nach Aufgabe 11.7 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt in dieser Situation auch

$\vdash \forall xp\rightarrow \forall x(q\rightarrow r).$

Nach Lemma 11.9 (Einführung in die mathematische Logik (Osnabrück 2021))  (3) ist

$\vdash \forall x(q\rightarrow r)\rightarrow {\left(\exists xq\rightarrow \exists xr\right)}.$

Dies zusammengenommen ergibt mit dem Kettenschluss

$\vdash \forall xp\rightarrow {\left(\exists xq\rightarrow \exists xr\right)},$

was im obigen Spezialfall die gewünschte Ableitbarkeit

$\vdash \forall x(Ax\rightarrow Bx)\rightarrow {\left(\exists xAx\wedge Cx\rightarrow \exists xBx\wedge Cx\right)}$

liefert.

Aufgabe (6 (3+3) Punkte)

Es sei ${}(M,0,N)$ ein Modell für die Peano-Axiome für den Nachfolger.

1. Zeige, dass ${}N$ fixpunktfrei ist, d.h. dass

   ${}N(x)\neq x\,$

   für alle ${}x\in M$.

2. Zeige, dass ${}N$ periodenfrei ist. D.h. für jedes ${}\ell \in \mathbb {N} _{+}$ ist

   ${}N^{\ell }(x)\neq x\,,$

   wobei

   ${}N^{\ell }=N\circ \cdots \circ N\,$

   die ${}\ell$-fache Hintereinanderschaltung von ${}N$ bedeutet.

Lösung

1. Wir zeigen die Aussage

   ${}Nx\neq x\,$

   durch Induktion über ${}x$. Bei

   ${}x=0\,$

   ergibt sich ${}N0\neq 0$ unmittelbar aus dem Axiom, dass ${}0$ kein Nachfolger ist. Es sei die Aussage für ${}x$ richtig, also

   ${}Nx\neq x\,.$

   Die Gleichheit

   ${}NNx=Nx\,$

   wäre in Verbindung mit der Induktionsvoraussetzung ein direkter Widerspruch zur Injektivität der Nachfolgerabbildung. Also ist

   ${}NNx\neq Nx\,$

   und die Aussage ist bewiesen.

2. Es sei nun ${}\ell$ und

   ${}N^{\ell }=N\circ \cdots \circ N\,$

   fixiert. Wir zeigen

   ${}N^{\ell }(x)\neq x\,$

   durch Induktion über ${}x$. Bei ${}x=0$ ergibt sich

   ${}N^{\ell }(0)\neq 0\,,$

   da sonst ${}0$ der Nachfolger von ${}N^{\ell -1}(0)$ wäre. Es sei die Aussage nun für ${}x$ richtig, also

   ${}N^{\ell }(x)\neq x\,.$

   Nehmen wir an, dass die Gleichheit

   ${}N^{\ell }Nx=Nx\,$

   gilt. Wegen

   ${}N^{\ell }(N(x))=N(N^{\ell }(x))\,$

   folgt aus der Injektivität der Nachfolgerabbildung direkt

   ${}N^{\ell }x=x\,$

   im Widerspruch zur Induktionsvoraussetzung. Also ist

   ${}N^{\ell }Nx\neq Nx\,$

   und die Aussage ist bewiesen.

Aufgabe (4 Punkte)

Zeige, dass es einen Peano-Halbring ${}M$ mit der Eigenschaft gibt, dass es darin ein Element ${}x\in M$ gibt, das größer als jede natürliche Zahl in ${}M$ (also Zahlen der Form ${}1+1+\cdots +1$) ist.

Lösung

Es sei ${}\Gamma$ die Menge der aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Wir betrachten die Ausdrücke ${}\alpha _{n}$ mit

${}\alpha _{n}=\neg {\left(x=1+1+\cdots +1\right)}\,,$

wobei rechts die ${}n$-fache formale Summe der ${}1$ mit sich selbst steht. Es sei

${}\Delta ={\left(\Gamma \cup \bigcup _{n\in \mathbb {N} }\{\alpha _{n}\}\right)}^{\vdash }\,.$

Diese Menge ist widerspruchsfrei, da jede endliche Teilmenge davon widerspruchsfrei ist, da sie in ${}\mathbb {N}$ mit einer hinreichend großen Belegung für ${}x$ erfüllbar ist. Nach Korollar 15.10 (Einführung in die mathematische Logik (Osnabrück 2021)) ist also auch ${}\Delta$ erfüllbar, und es sei ${}M$ ein erfüllendes Modell. Es gibt dann in ${}M$ ein Element ${}m\in M$, wodurch ${}x$ belegt wird. Dieses ${}m$ ist dann von allen natürlichen Zahlen, die in ${}M$ natürlicherweise eingebettet sind, verschieden, und somit ist ${}M\neq \mathbb {N}$.

Aufgabe (3 (1+1+1) Punkte)

Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze ${}1,2,3,4$ nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz ${}3$ bestreiten. Von einer solchen Runde seien die Mannschaften ${}A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.

1. Welche Information über die Platzierung kann man stets aus den Daten erschließen?
2. Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
3. unter welcher nicht?

Lösung

1. Es gibt genau eine Mannschaft, die zweimal gewinnt, diese ist Weltmeister, und genau eine Mannschaft, die zweimal verliert, diese ist Vierter. Die beiden anderen Mannschaften gewinnen einmal und verlieren einmal und sind Zweiter oder Dritter.
2. Wenn der Erste gegen den Vierten (die ja beide bekannt sind) spielt, so muss dieses Spiel ein Hauptfinale sein. Das komplementäre Spiel ist ebenfalls ein Halbfinale, das andere Spiel des Ersten muss das Finale und das andere Spiel des Vierten muss das Spiel um Platz drei sein. Somit sind alle Platzierungen bekannt.
3. Wenn der Erste nicht gegen den Vierten spielt, so kann man den Zweiten nicht vom Dritten unterscheiden.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.

Lösung

 Wir nehmen an, dass ${}\Gamma ^{\vdash }$ vollständig ist. Da ${}\Gamma$ aufzählbar ist, ist ${}\Gamma ^{\vdash }$ nach Lemma 21.9 (Einführung in die mathematische Logik (Osnabrück 2021)) aufzählbar und nach Satz 21.10 (Einführung in die mathematische Logik (Osnabrück 2021)) auch entscheidbar. Da ${}\Gamma$ Repräsentierungen erlaubt, ist insbesondere ${}\Gamma ^{\vdash }$ repräsentierbar. Daher sind die Voraussetzungen von Lemma 23.1 (Einführung in die mathematische Logik (Osnabrück 2021)) erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (6 (4+2) Punkte)

1. Skizziere ein modallogisches Modell, bei dem es verschiedene Weltpunkte ${}v,w$ mit

   $v\vDash \neg \Box p$

   und

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

   gibt.

2. Was ist die minimale Anzahl von Welten in einem modallogischen Modell, in dem die Anforderungen aus 1) realisierbar sind.

Lösung

1. Wir betrachten das Modell bestehend aus den vier Welten ${}u,v,w,z$ mit der Erreichbarkeitsrelation

   $Rwz,Rwu,Rvu$

   und der Belegung

   $z\vDash p,\,u\vDash \neg p$

   (die Belegung von ${}p$ auf ${}v,w$ ist irrelevant). Dann gilt

   $z\vDash \Box p,\,u\vDash \Box p,$

   da es für diese beiden Welten keine erreichbaren Welten gibt. In allen von ${}w$ aus erreichbaren Welten gilt somit ${}\Box p$ und daher

   $w\vDash \Box \Box p.$

   Ferner gilt

   $w\vDash \Diamond p$

   wegen der Erreichbarkeit ${}Rwz$ und

   $w\vDash \Diamond \neg p$

   wegen der Erreichbarkeit ${}Rwu$ und auch

   $v\vDash \Diamond \neg p,$

   also

   $v\vDash \neg \Box p,$

   wegen der Erreichbarkeit ${}Rvu$.

2. Wir behaupten, dass die Anforderungen nicht mit weniger als vier Welten realisierbar sind. Nach Voraussetzung müssen ${}v$ und ${}w$ verschieden sein. Wegen

   $w\vDash \Diamond \neg p\,\,{\text{ und }}\,\,v\vDash \Diamond \neg p$

   kann von ${}w$ weder ${}v$ noch ${}w$ selbst erreichbar sein, da dies ein Widerspruch zu ${}w\vDash \Box \Box p$ ergeben würde. Zugleich braucht man, um die Gültigkeit von ${}w\vDash \Diamond p$ und ${}w\vDash \Diamond \neg p$ zu realisieren, zwei von ${}w$ aus erreichbare Welten, also insgesamt mindestens vier Welten.