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

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

Aufgabe (3 Punkte)

Lösung

1. Eine natürliche Zahl ${}n\geq 2$ heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr ${}1$ und ${}n$ sind.
2. Die Sprache der Aussagenlogik ${}L^{V}$ wird rekursiv durch folgende Regeln definiert.
   1. Jedes ${}p\in V$ gehört zu ${}L^{V}$.
   2. Wenn ${}\alpha \in L^{V}$, so ist auch ${}\neg (\alpha )\in L^{V}$.
   3. Wenn ${}\alpha ,\beta \in L^{V}$, so sind auch ${}(\alpha )\wedge (\beta ),\,(\alpha )\vee (\beta ),\,(\alpha )\rightarrow (\beta ),\,(\alpha )\leftrightarrow (\beta )\in L^{V}$.
3. Unter der Uminterpretation ${}I{\frac {m}{x}}$ versteht man diejenige Interpretation von ${}S$ in ${}M$, die strukturgleich zu ${}I$ ist und für deren Variablenbelegung

   $\left(I{\frac {m}{x}}\right)(y)={\begin{cases}I(y),\,{\text{ falls }}y\neq x\,,\\m,\,{\text{ falls }}y=x\,,\end{cases}}$

   gilt.

4. Der Rang ${}\rho$ von ${}\alpha$ wird rekursiv durch
   1. ${}\rho (\alpha )=0$, falls ${}\alpha$ atomar ist.
   2. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\neg (\beta )$ ist.
   3. ${}\rho (\alpha )=\rho (\beta )+\rho (\gamma )+1$, falls ${}\alpha =(\beta )\circ (\gamma )$ mit ${}\circ =\wedge ,\,\vee ,\,\rightarrow ,\leftrightarrow$ ist.
   4. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\exists x\beta$ oder ${}\alpha =\forall x\beta$ ist.

   definiert.

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. Eine Modallogik heißt eine ${}K$-Modallogik, wenn das Axiomenschema

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

   für beliebige Ausdrücke ${}\alpha ,\beta$ und die Nezessisierungsregel

   aus ${}\vdash \alpha$ folgt ${}\vdash \Box \alpha$

   für alle ${}\alpha$ gilt.

Aufgabe (3 Punkte)

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. Es sei ${}M$ eine Menge mit einem fixierten Element ${}s\in M$ und einer Abbildung ${}F\colon M\rightarrow M$. Dann gibt es genau eine Abbildung

   $\varphi \colon N\longrightarrow M,\,n\longmapsto \varphi (n),$

   die die beiden Eigenschaften

   $\varphi (0)=s{\text{ und }}\varphi (n^{\prime })=F(\varphi (n)){\text{ für alle }}n\in \mathbb {N}$

   erfüllt.
3. Es sei ${}\Gamma$ eine Menge von modallogischen Ausdrücken und ${}\alpha$ ein modallogischer Ausdruck. Dann ist

   $\Gamma \vdash \alpha$

   genau dann, wenn

   $\Gamma \vDash \alpha .$

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

Folgende Aussagen seien bekannt.

1. Der frühe Vogel fängt den Wurm.
2. Doro wird nicht von Lilly gefangen.
3. Lilly ist ein Vogel oder ein Igel.
4. Für Igel ist 5 Uhr am Morgen spät.
5. Doro ist ein Wurm.
6. Für Vögel ist 5 Uhr am Morgen früh.
7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

1. Ist Lilly ein Vogel oder ein Igel?
2. Ist sie ein frühes oder ein spätes Tier?
3. Fängt der späte Igel den Wurm?

Lösung

1. Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um ${}5$ Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2).
2. Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier.
3. Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm.

Aufgabe (8 Punkte)

Es sei ${}\alpha$ eine aussagenlogische Aussage und es seien ${}p_{1},\ldots ,p_{n}$ die darin vorkommenden Aussagenvariablen. Es sei

${}\gamma =\pm p_{1}\wedge \ldots \wedge \pm p_{n}\,$

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Zeige, dass dann

$\vdash \gamma \rightarrow \alpha \,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \neg \alpha$

gilt.

Lösung

Wir führen Induktion über den Aufbau der Sprache ${}L^{\{p_{1},\ldots ,p_{n}\}}$. Bei

${}\alpha =p_{i}\,$

ergibt sich die Aussage aus Lemma 3.12 (Einführung in die mathematische Logik (Osnabrück 2021)). Bei

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

ergibt sich die Aussage aus der Induktionsvoraussetzung und aus Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021))  (3). Es sei nun

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

Bei

$\vdash \gamma \rightarrow \beta _{1}\,\,{\text{ und }}\,\,\vdash \gamma \rightarrow \beta _{2}$

ergibt sich die Ableitung

$\vdash \gamma \rightarrow \beta _{1}\wedge \beta _{2}$

im Wesentlichen aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3). Bei

$\vdash \gamma \rightarrow \neg \beta _{1}$

ergibt sich die Ableitung

$\vdash \gamma \rightarrow \neg {\left(\beta _{1}\wedge \beta _{2}\right)}$

aus Kontraposition auf Lemma 3.12 (Einführung in die mathematische Logik (Osnabrück 2021)). Es sei nun

${}\alpha =\beta _{1}\rightarrow \beta _{2}\,.$

Bei

$\vdash \gamma \rightarrow \neg \beta _{1}\,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \beta _{2}$

ergibt sich die Ableitung

$\vdash \gamma \rightarrow {\left(\beta _{1}\rightarrow \beta _{2}\right)}$

aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) bzw. aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (5). Bei

$\vdash \gamma \rightarrow \beta _{1}\,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \neg \beta _{2}$

hingegen ergibt sich die Ableitung

$\vdash \gamma \rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}$

folgendermaßen. Nach Lemma 3.17 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

$\vdash \beta _{1}\wedge {\left(\beta _{1}\rightarrow \beta _{2}\right)}\rightarrow \beta _{2},$

was wir als

$\vdash \beta _{1}\rightarrow {\left({\left(\beta _{1}\rightarrow \beta _{2}\right)}\rightarrow \beta _{2}\right)}$

schreiben. Kontraposition auf den Nachsatz ergibt

$\vdash \beta _{1}\rightarrow {\left(\neg \beta _{2}\rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}\right)},$

was wir wiederum als

$\vdash \beta _{1}\wedge \neg \beta _{2}\rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}$

schreiben. Aus den beiden Voraussetzungen ergibt sich mit Hilfe von Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3)

$\vdash \gamma \rightarrow \beta _{1}\wedge \neg \beta _{2}$

und somit mit der Kettenschlussregel

$\vdash \gamma \rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}.$

Aufgabe (2 Punkte)

Es sei ${}K=\{E,m,c\}$ eine Konstantenmenge, ${}Q$ ein einstelliges Funktionssymbol und ${}P$ ein zweistelliges Funktionssymbol. Es sei ${}I$ die Interpretation mit ${}M=\mathbb {N}$ als Grundmenge, bei der ${}Q$ als Quadrieren, ${}P$ als Multiplikation und die Konstanten als ${}I(E)=9000000000$ ${}I(m)=1$ und ${}I(c)=300000$ interpretiert wird. Ist der Ausdruck

$E=PmQc$

unter dieser Interpretation gültig?

Lösung

Die Gültigkeit des Ausdrucks bei der Interpretation würde bedeuten, dass

${}I(E)=9000000000\,$

mit

${}I(P)(I(m),I(Q)(I(c)))=1\cdot 300000^{2}=90000000000\,$

übereinstimmt. Da eine ${}0$ fehlt, ist dies nicht richtig und daher ist der Ausdruck bei der Interpretation nicht gültig.

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

1. Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
2. Beschreibe die Bedingung (und zwar so, dass die Bedingung erkennbar ist) aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck (also mit dem Symbolalphabet ${}+,\cdot ,0,1$ und Variablen) in der einen freien Variablen ${}x$.
3. Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen ${}x$.

Lösung

1. Da ${}0$ eine natürliche Zahl ist, sind die ersten Quadratzahlen ${}0,1,4$ und somit ist ${}5$ die erste natürliche Zahl, die größer als drei Quadratzahlen ist.

2. $\exists y\exists z\exists w{\left(y\neq w\wedge y\neq z\wedge z\neq w\wedge \exists r{\left(x\geq y\cdot y+r+1\right)}\wedge \exists r{\left(x\geq z\cdot z+r+1\right)}\wedge \exists r{\left(x\geq w\cdot w+r+1\right)}\right)}\wedge$

   $\forall u{\left(\exists y\exists z\exists w{\left(y\neq w\wedge y\neq z\wedge z\neq w\wedge \exists r{\left(u\geq y\cdot y+r+1\right)}\wedge \exists r{\left(u\geq z\cdot z+r+1\right)}\wedge \exists r{\left(u\geq w\cdot w+r+1\right)}\right)}\rightarrow \exists s{\left(u=x+s\right)}\right)}.$

3. $x=1+1+1+1+1.$

Aufgabe (3 Punkte)

Formuliere die Injektivität für eine Abbildung

$f\colon D\longrightarrow Z$

prädikatenlogisch mit Hilfe der Verwendung von Sorten.

Lösung

Die Symbolmenge ${}S$ bestehe aus einem einstelligen Funktionssymbol ${}f$ und zwei einstelligen Relationssymbolen ${}D$ und ${}Z$. Wir betrachten den Ausdruck

$\forall x(Dx\rightarrow Zfx)\wedge \forall x\forall y{\left(Dx\wedge Dy\wedge \neg {\left(x=y\right)}\rightarrow \neg {\left(fx=fy\right)}\right)}.$

Bei einer Interpretation in einer Gesamtmenge ${}M$ besagt der linke Ausdruck, dass wenn ein Element ${}m$ zu ${}D^{M}$ gehört, dass dann der Funktionswert ${}f^{M}(m)$ zu ${}Z^{M}$ gehört. Das bedeutet also, dass eine Abbildung

$f^{M}\colon D^{M}\longrightarrow Z^{M}$

vorliegt. Der rechte Ausdruck besagt somit, dass für verschiedene Elemente aus ${}D^{M}$ die Bilder verschieden sind, was die Injektivität dieser Abbildung bedeutet.

Aufgabe (5 (3+2) Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache und ${}T$ die zugehörige Termmenge. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge.

1. Zeige, dass durch

   $s\cong _{\Gamma }t{\text{ genau dann, wenn }}I(s)=I(t){\text{ für jede Interpretation }}I{\text{ mit }}I\vDash \Gamma$

   eine Äquivalenzrelation auf ${}T$ definiert wird.

2. Wenn man ${}\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?

Lösung

1. Wegen ${}\vdash s=s$ und der Korrektheit des Ableitungskalküls ist ${}I(s)=I(t)$ überhaupt für jede Interpretation. Es liegt also eine reflexive Relation vor. Es sei nun ${}s\cong _{\Gamma }t$. Dann gilt für jede Interpretation ${}I$ mit ${}I\vDash \Gamma$ die Gleichheit ${}I(s)=I(t)$ und somit auch ${}I(t)=I(s)$, also ist auch ${}t\cong _{\Gamma }s$, was die Symmetrie beweist. Es gelte nun ${}r\cong _{\Gamma }s$ und ${}s\cong _{\Gamma }t$, und es sei ${}I$ eine Interpretation mit ${}I\vDash \Gamma$. Dann ist ${}I(r)=I(s)$ und ${}I(s)=I(t)$ und somit auch ${}I(r)=I(t)$ wegen der Transitivität der Gleichheit. Also gilt ${}r\cong _{\Gamma }t$, was die Transitivität beweist.
2. Es sei ${}\Gamma \subseteq \Gamma '$. Wir behaupten, dass die Äquivalenz ${}s\cong _{\Gamma }t$ die Äquivalenz ${}s\cong _{\Gamma '}t$ impliziert. Es sei dazu ${}s\cong _{\Gamma }t$ und eine Interpretation ${}I$ mit ${}I\vDash \Gamma '$ gegeben. Dann gilt erst recht ${}I\vDash \Gamma$ und somit ist ${}I(s)=I(t)$. Somit umfassen die Äquivalenzklassen zu ${}\cong _{\Gamma '}$ die Äquivalenzklassen zu ${}\cong _{\Gamma }$, die Äquivalenzklassen werden also größer.

Aufgabe (5 (1+1+1+1+1) Punkte)

In einer Wohngemeinschaft leben die Personen ${}A,B,C,D,E$. Wir betrachten die folgenden Relationen:

1. ${}Txy$ bedeutet, dass ${}x$ und ${}y$ manchmal miteinander Tennis spielen,
2. ${}Sxyz$ bedeutet, dass ${}x,y$ und ${}z$ manchmal miteinander Skat spielen,
3. ${}Kxyzw$ bedeutet, dass ${}x,y,z$ und ${}w$ manchmal miteinander Doppelkopf spielen.

In der WG gilt

$TDE,SABC,SABE,KACED.$

1. Charakterisiere umgangssprachlich die Person ${}D$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
2. Charakterisiere umgangssprachlich die Person ${}C$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}T,S,K$ die Person ${}A$.
4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}T,S,K$ die Person ${}B$.
5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}T,S,K$ die Person ${}E$.

Lösung

1. ${}D$ ist diejenige Person, die manchmal Tennis spielt und kein Skat spielt.
2. ${}C$ ist diejenige Person, die manchmal Skat spielt, und zwar nur bei einer Skatrunde beteiligt ist, und die nicht Tennis spielt.
3. ${}\exists y{\left(\exists z\wedge \exists w{\left(z\neq w\wedge Sxyz\wedge Sxyw\right)}\right)}\wedge \exists y\exists z\exists wKxyzw$.
4. ${}\neg {\left(\exists y\exists z\exists wKxyzw\right)}$.
5. ${}\exists yTxy\wedge \exists y\exists zSxyz$.

Aufgabe (4 Punkte)

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

Lösung Registermaschine/Alle Quadratzahlen/Druckt/Aufgabe/Lösung

Aufgabe (4 Punkte)

Es seien ${}T,S\subseteq \mathbb {N}$ entscheidbare Mengen. Zeige, dass dann auch die Vereinigung ${}T\cup S$, der Durchschnitt ${}T\cap S$ und auch das Komplement ${}\mathbb {N} \setminus T$ entscheidbar sind.

Lösung N/Teilmengen/Entscheidbar/Durchschnitt und Vereinigung/Komplement/Aufgabe/Lösung

Aufgabe (4 Punkte)

Zeige, dass die Abbildung

$f\colon \mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(x,y,z)\longmapsto xy^{2}-z^{2}+2z^{3},$

(wohldefiniert und) arithmetisch repräsentierbar ist.

Lösung

Die Abbildung ist wohldefiniert, da der Ausdruck

${}-z^{2}+2z^{3}=z^{2}(2z-1)\,$

für ${}z\in \mathbb {N}$ nie negativ wird. Es sei

${}\psi (x,y,z,w):=x\cdot y\cdot y+z\cdot z\cdot z+z\cdot z\cdot z=w+z\cdot z\,.$

Für beliebige natürliche Zahlen ${}(n_{1},n_{2},n_{3},n_{4})\in \mathbb {N} ^{4}$ gilt dann

$\mathbb {N} \vDash \psi (n_{1},n_{2},n_{3},n_{4})$

genau dann, wenn in ${}\mathbb {N}$ die Gleichheit

${}n_{1}\cdot n_{2}\cdot n_{2}+n_{3}\cdot n_{3}\cdot n_{3}+n_{3}\cdot n_{3}\cdot n_{3}=n_{4}+n_{3}\cdot n_{3}\,$

gilt, was genau dann der Fall ist, wenn in ${}\mathbb {N}$ die Gleichheit

${}n_{4}=n_{1}\cdot n_{2}\cdot n_{2}-n_{3}\cdot n_{3}+n_{3}\cdot n_{3}\cdot n_{3}+n_{3}\cdot n_{3}\cdot n_{3}\,$

bzw.

${}n_{4}=n_{1}\cdot n_{2}^{2}-n_{3}^{2}+2n_{3}^{3}\,,$

also

${}n_{4}=f(n_{1},n_{2},n_{3})\,$

gilt. Der Ausdruck ${}\psi$ repräsentiert also arithmetisch die Funktion ${}f$.

Aufgabe (4 Punkte)

Beweise das Unvollständigkeitslemma.

Lösung

Aus der Repräsentierbarkeit von ${}\Gamma ^{\vdash }$ folgt, dass es einen arithmetischen Ausdruck in einer freien Variablen gibt, sagen wir ${}a(x)$, mit der Eigenschaft, dass

$\Gamma \vdash s$

genau dann gilt, wenn

$\Gamma \vdash a(GN(s))$

gilt. Wir betrachten die Negation ${}\beta =\neg a$. Nach Satz 22.8 (Einführung in die mathematische Logik (Osnabrück 2021)) gibt es für ${}\beta$ einen Fixpunkt, also einen Satz ${}q$ mit

$\Gamma \vdash q\longleftrightarrow \beta (GN(q))$

bzw.

$\Gamma \vdash q\longleftrightarrow \neg a(GN(q)).$

Sowohl aus ${}\Gamma \vdash q$ als auch aus ${}\Gamma \vdash \neg q$ ergibt sich dann direkt ein ableitbarer Widerspruch, was der Widerspruchsfreiheit des Systems widerspricht.

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

Wir interpretieren den Satz von Sokrates, „Ich weiß, dass ich nichts weiß“, als modallogisches Axiomenschema

$\Box \neg \Box \alpha .$

Zeige die folgenden Aussagen.

1. Dieses Axiomenschema ist paradox.
2. Dieses Axiomenschema ist innerhalb der ${}K$- Modallogik äquivalent zu

   $\Box \Diamond \alpha .$

3. Dieses Axiomenschema ist innerhalb der ${}K$- Modallogik äquivalent zu

   $\Box \alpha ,$

   also zum Leerheitsaxiom.

Lösung

1. Für die Tauotologie

   ${}\alpha =p\vee \neg p\,$

   ergibt sich, wenn man die Boxen vergisst, der Widerspruch ${}\neg \alpha$, also ist das Axiomenschema paradox.

2. Es ist

   $\Box \neg \Box \alpha \leftrightarrow \Box \Diamond \neg \alpha .$

   Somit gilt die linke Seite für alle ${}\alpha$ genau dann, wenn die rechte Seite für alle ${}\alpha$ gilt, und dies ist in einer ${}K$-Modallogik äquivalent dazu, dass es für alle ${}\neg \alpha$ gilt.

3. Das Leerheitsaxiom ist offenbar stärker. Wegen der Widerspruchstautologie gilt

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

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

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

   und nach Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) gilt

   $\vdash \Box \Box \beta \wedge \Box \neg \Box \beta \rightarrow \Box (\Box \beta \wedge \neg \Box \beta ).$

   Mit dem Kettenschluss ergibt sich

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

   Wir setzen nun für ${}\beta$ eine Tautologie ein, etwa ${}\beta =p\rightarrow p$. Eine doppelte Anwendung der Nezessisierungsregel liefert

   $\vdash \Box \Box \beta .$

   Das Sokratesaxiom liefert

   $S\vdash \Box \neg \Box \beta .$

   Damit sind die beiden Voraussetzungen von oben erfüllt und somit gilt

   $S\vdash \Box \alpha .$

Aufgabe (5 Punkte)

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

Lösung

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

$w\vDash \Box \alpha .$

Es sei ${}wRv$ und ${}vRz$ und somit

$z\vDash \alpha .$

Also ist

$v\vDash \Box \alpha .$

und damit

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

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

$w\vDash \Box p$

und

$v\not \vDash \Box p,$

da ja ${}z\not \vDash p$, und somit ist

$w\not \vDash \Box \Box p,$

also

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