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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Wohlordnung auf einer Menge ${}M$.
2. Eine ${}n$-stellige Relation auf einer Menge ${}M$.
3. Die Termmenge zu einer Grundtermmenge ${}(V,K,F_{n})$.
4. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
5. Die Befehle für eine Registermaschine.
6. Die modallogische Sprache zu einer Aussagenvariablenmenge ${}V$.

Lösung

1. Eine totale Ordnung ${}\preccurlyeq$ auf einer Menge ${}M$ heißt Wohlordnung, wenn jede nichtleere Teilmenge ${}T\subseteq M$ ein kleinstes Element besitzt.
2. Unter einer ${}n$-stelligen Relation ${}R$ auf ${}M$ versteht man eine Teilmenge der ${}n$-fachen Produktmenge ${}M\times \cdots \times M$.
3. Die Termmenge ist diejenige Teilmenge ${}T=T(G)$ der Wörter ${}A^{*}$ über dem Termalphabet ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$, die durch die folgenden rekursiven Vorschriften festgelegt wird.
   1. Jede Variable ${}v\in V$ ist ein Term.
   2. Jede Konstante ${}c\in K$ ist ein Term.
   3. Für jedes ${}f\in F_{n}$ und ${}n$ Terme ${}t_{1},t_{2},\ldots ,t_{n}$ ist auch ${}ft_{1}t_{2}\ldots t_{n}$ ein Term.
4. Man nennt ${}\alpha$ allgemeingültig, wenn er in jeder ${}S$- Interpretation ${}I$ gilt.
5. Die Befehle für eine Registermaschine sind (dabei bezeichnen ${}R_{i}$ Register und ${}B_{j}$ Befehlszeilen).
   1. ${}i+$ (erhöhe den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. um einen Strich).
   2. ${}i-$ (reduziere den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
   3. ${}C(ij)$ (wenn das ${}i$-te Register leer ist, so gehe zum Befehl ${}B_{j}$, andernfalls zum nächsten Befehl).
   4. Drucke (drucke den Inhalt des ersten Registers).
   5. Halte an.
6. Die modallogische Sprache zu ${}V$ besteht aus den Aussagenvariablen, aus allen rekursiv-konstruierbaren aussagenlogischen Verknüpfungen und aus allen rekursiv-konstruierbaren Ausdrücken der Form ${}\Box (\alpha )$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).
2. Der Vollständigkeitssatz der Prädikatenlogik.
3. /Fakt/Name

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, ${}\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. /Fakt

Aufgabe (1 Punkt)

Bruno liest in der Zeitung: „Im letzen Jahr war bei ${}50\%$ aller Autounfälle Alkohol mit im Spiel“. Bruno überlegt: „ ${}50\%$ mit Alkohol, ${}50\%$ ohne Alkohol. Dann ist es also egal, ob man was trinkt oder nicht. In Zukunft werde ich das auch nicht mehr so streng sehen“. Beurteile diese Überlegung!

Lösung Autounfall/Alkoholanteil/Aufgabe/Lösung

Aufgabe (3 Punkte)

Beweise den Satz, dass es unendlich viele Primzahlen gibt.

Lösung

Angenommen, die Menge aller Primzahlen sei endlich, sagen wir ${}\{p_{1},p_{2},\ldots ,p_{r}\}$. Man betrachtet die Zahl

${}N=p_{1}\cdot p_{2}\cdot p_{3}{\cdots }p_{r}\ +1\,.$

Diese Zahl ist durch keine der Primzahlen ${}p_{i}$ teilbar, da bei Division von ${}N$ durch ${}p_{i}$ immer ein Rest ${}1$ verbleibt. Damit sind die Primfaktoren von ${}N$, die es nach Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024)) geben muss, nicht in der Ausgangsmenge enthalten - Widerspruch.

Aufgabe (3 Punkte)

Definiere zu jeder Aussage ${}\alpha \in L^{V}$ die Menge ${}\operatorname {Var} _{}^{}{\left(\alpha \right)}$ der in ${}\alpha$ vorkommenden Aussagenvariablen.

Lösung

Wir legen die Abbildung

$\operatorname {Var} \colon L^{V}\longrightarrow {\mathfrak {P}}\,(V),\,\alpha \longmapsto \operatorname {Var} _{}^{}{\left(\alpha \right)}$

rekursiv über den Aufbau von ${}L^{V}$ fest. Wegen dem eindeutigen rekursiven Aufbau von ${}L^{V}$ ist dadurch eine wohldefinierte Abbildung gegeben. Für

${}\alpha =p\in V\,$

setzt man

${}\operatorname {Var} _{}^{}{\left(p\right)}=\{p\}\,.$

Für

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

setzt man

${}\operatorname {Var} _{}^{}{\left(\alpha \right)}=\operatorname {Var} _{}^{}{\left(\beta \right)}\,.$

Für

${}\alpha =(\beta )*(\gamma )\,$

mit

${}*=\wedge ,\vee ,\rightarrow ,\leftrightarrow \,$

setzt man

${}\operatorname {Var} _{}^{}{\left((\beta )*(\gamma )\right)}=\operatorname {Var} _{}^{}{\left(\beta \right)}\cup \operatorname {Var} _{}^{}{\left(\gamma \right)}\,.$

Aufgabe (2 Punkte)

Zeige

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

unter Verwendung von

$\vdash \gamma \wedge \delta \rightarrow \delta \wedge \gamma$

(Lemma 3.14 (Einführung in die mathematische Logik (Osnabrück 2021))).

Lösung

Aufgrund von Lemma 3.14 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

$\vdash \alpha \wedge \neg \alpha \rightarrow \neg \alpha \wedge \alpha .$

Das Widerspruchsaxiom besagt

$\vdash \neg \alpha \wedge \alpha \rightarrow \beta .$

Das Kettenschlussaxiom liefert

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

Da die beiden Teile des Vordersatzes ableitbar sind, ist auch der Nachsatz ableitbar.

Aufgabe (3 Punkte)

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

Lösung

Die Voraussetzung bedeutet, dass es Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{m},\beta _{1},\ldots ,\beta _{n}\in \Gamma$ mit

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

und mit

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

gibt. Daraus ergibt sich mit Hilfe (der Regelversion) von Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021))  (2)

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

Dies bedeutet ${}\Gamma \vdash \alpha \wedge \beta$.

Aufgabe (5 (4+1) Punkte)

Es sei ${}X$ ein topologischer Raum und ${}F$ ein topologischer Filter auf ${}X$, ${}T\subseteq X$ eine offene Teilmenge und ${}T\notin F$.

1. Zeige, dass das Mengensystem

   ${\left\{U\mid U\subseteq X{\text{ offen}},\,{\text{es gibt }}V\in F{\text{ mit }}V\cap {\left(X\setminus T\right)}\subseteq U\right\}}$

   ein Filter auf ${}X$ ist, der ${}X\setminus T$ enthält und ${}T$ nicht enthält.

2. Zeige mit Hilfe des Lemmas von Zorn, dass es einen Ultrafilter ${}G$ mit ${}F\subseteq G$ und mit ${}T\notin G$ gibt.

Lösung

1. Sei

   ${}H={\left\{U\mid U\subseteq X{\text{ offen }},\,{\text{es gibt }}V\in F{\text{ mit }}V\cap X\setminus T\subseteq U\right\}}\,.$

   Zu ${}V\in F$ ist

   ${}V\cap {\left(X\setminus T\right)}\subseteq V\,$

   und daher ist

   ${}F\subseteq H\,$

   und insbesondere ist ${}X\in H$. Zu ${}U\in H$ gibt es ${}V\in F$ mit

   ${}V\cap {\left(X\setminus T\right)}\subseteq U\,,$

   und diese Bedingung wird auch von jedem ${}U'\supseteq U$ erfüllt, also ist auch ${}U'\in H$. Zu ${}U_{1},U_{2}\in H$ gibt es ${}V_{1},V_{2}\in F$ mit

   ${}V_{1}\cap {\left(X\setminus T\right)}\subseteq U_{1}\,$

   und

   ${}V_{2}\cap {\left(X\setminus T\right)}\subseteq U_{2}\,.$

   Daraus ergibt sich

   ${}V_{1}\cap V_{2}\cap {\left(X\setminus T\right)}\subseteq U_{1}\cap U_{2}\,$

   und wegen ${}V_{1}\cap V_{2}\in F$ ist ${}U_{1}\cap U_{2}\in H$. Somit ist ${}H$ ein Filter. Wegen ${}X\in F$ und

   ${}X\cap {\left(X\setminus T\right)}=X\setminus T\,$

   ist ${}X\setminus T\in H$. Angenommen ${}T\in H$. Dann gibt es ${}V\in F$ mit

   ${}V\cap {\left(X\setminus T\right)}\subseteq T\,$

   und dann ist insbesondere ${}V\subseteq T$, also ${}T\in V$ im Widerspruch zur Voraussetzung.

2. Zu dem in Teil (1) gegebenen Filter ${}H$ gibt es nach Lemma 5.13 (Einführung in die mathematische Logik (Osnabrück 2021)) einen Ultrafilter ${}G$ mit ${}F\subseteq G$. Wegen ${}X\setminus T\in F$ ist ${}T\notin G$, da sonst auch

   ${}\emptyset ={\left(X\setminus T\right)}\cap T\in G\,$

   wäre.

Aufgabe (1 Punkt)

Man finde eine äquivalente Formulierung für die Aussage „Frau Maier-Sengupta hat nicht alle Tassen im Schrank“ mit Hilfe einer Existenzaussage.

Lösung

Es gibt eine Tasse, die Frau Maier-Sengupta nicht im Schrank hat.

Aufgabe (5 Punkte)

Es seien ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}f$ ein ${}n$-stelliges Funktionssymbol. Zeige, dass die Ableitbarkeit

$\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}$

gilt.

Lösung

Es sei ${}u$ eine Variable, die weder in einem der ${}s_{i}$ noch in einem der ${}t_{i}$ vorkommt. Für jedes ${}i=1,\ldots ,n$ setzen wir ${}\alpha _{i}:=ft_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}=ft_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}$. Nach Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))   (2) ergibt sich daraus

$\vdash s_{i}=t_{i}\rightarrow {\left(\alpha _{i}{\frac {s_{i}}{u}}\rightarrow \alpha _{i}{\frac {t_{i}}{u}}\right)},$

also

$\vdash s_{i}=t_{i}\rightarrow {\left({\left(ft_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}=ft_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}\right)}\rightarrow {\left(ft_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}=ft_{1}\ldots t_{i-1}t_{i}s_{i+1}\ldots s_{n}\right)}\right)}.$

Da der Vordersatz in der Implikation rechts nach Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) ableitbar ist, ergibt eine aussagenlogische Umformulierung

$\vdash s_{i}=t_{i}\rightarrow {\left(ft_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}=ft_{1}\ldots t_{i-1}t_{i}s_{i+1}\ldots s_{n}\right)}.$

Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion

$(s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})$

ersetzt. Durch die Transitivität der Implikation ergibt sich daher

$\vdash (s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})\rightarrow {\left(fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}\right)}.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Reflexivitätsaxiom genau dann gilt, wenn ${}R$ reflexiv ist.

Lösung

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

$w\vDash \Box \alpha .$

Wegen ${}wRw$ ist insbesondere

$w\vDash \alpha$

und damit

$w\vDash \Box \alpha \rightarrow \alpha .$

Wenn ${}R$ nicht reflexiv ist, so sei ${}w\in M$ und ${}wRw$ gelte nicht. Es sei ${}\mu$ die Belegung, bei der

$w\vDash p$

gelte, aber in allen anderen Welten ${}v\vDash \neg p$. Dann ist

$w\vDash \neg \Diamond p,$

und somit ist

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