Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 25

Übungsaufgaben

Aufgabe

Zeige, dass in einem ${}K$- System, in dem das Axiomenschema

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

gilt, bereits das Leerheitsaxiom gilt.

Aufgabe

Zeige die Äquivalenz (innerhalb der ${}K$- Modallogik) der folgenden modallogischen Axiomenschemata.

1. Das Reflexivitätsaxiom ist äquivalent zu

   $\alpha \rightarrow \Diamond \alpha .$

2. Das Symmetrieaxiom ist äquivalent zu

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

3. Das Transitivitätsaxiom ist äquivalent zu

   $\Diamond \Diamond \alpha \rightarrow \Diamond \alpha .$

4. Das euklidische Axiom ist äquivalent zu

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

Zur folgenden Aufgabe vergleiche auch Aufgabe 23.17.

Aufgabe *

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.$

Aufgabe

Zeige, dass das Löb-Axiom äquivalent zu

$\vdash \Diamond \alpha \rightarrow \Diamond (\alpha \wedge \neg \Diamond \alpha )$

ist.

Aufgabe

Zeige, dass eine ${}K$- Modallogik, in der das Möglichkeitsaxiom und das Löb-Axiom gelten, bereits widersprüchlich ist.

Die Aussage „ich weiß, dass ich nichts weiß“ wird Sokrates zugeschrieben. In einer epistemischen ${}K$-Modallogik folgt daraus, dass Sokrates alles weiß.

Aufgabe *

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.

Aufgabe *

Es sei ${}\Gamma$ die durch das Löb-Axiom gegebene ${}K$- Modallogik, also die Beweisbarkeitslogik. Wir setzen

${}\bot :=p\wedge \neg p\,$

(als Abkürzung für einen Widerspruch). Zeige, dass

$\Gamma \vdash \neg \Box \neg \Box \bot \leftrightarrow \neg \Box \bot$

ableitbar ist.

Aufgabe

Es sei ${}\Gamma$ eine Menge von modallogischen Ausdrücken, die allesamt nicht paradox seien und es sei

$\Gamma \vdash \alpha$

eine Ableitung. Zeige, dass ${}\alpha$ ebenfalls nicht paradox ist.

Aufgabe

Welche modallogischen Axiomenschemata gelten in der Prädikatenlogik, wenn man den Notwendigkeitsoperator ${}\Box$ als ${}\forall x$ mit einer fixierten Variablen ${}x$ interpretiert?

Aufgabe

Zeige, dass ein gerichteter Graph, der sowohl euklidisch als auch symmetrisch ist, auch transitiv ist.

Aufgabe

Zeige, dass ein gerichteter Graph ${}(M,R)$ genau dann reflexiv ist, wenn für die Nachfolgermengen zu jeder Teilmenge ${}T\subseteq M$ die Beziehung

${}T\subseteq \operatorname {Nachf} {\left(T\right)}\,$

gilt.

Auf einer Menge ${}M$ nennt man eine Abbildung

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,T\longmapsto {\overline {T}},$

einen Hüllenoperator, wenn die folgende Eigenschaften für alles Teilmengen ${}S,T\subseteq M$ gelten.

1. ${}T\subseteq {\overline {T}}\,.$

2. Mit

   ${}S\subseteq T\,$

   ist auch

   ${}{\overline {S}}\subseteq {\overline {T}}\,.$

3. ${}{\overline {\overline {T}}}={\overline {T}}\,.$

Aufgabe

Es sei ${}(M,R)$ ein gerichteter Graph. Welche der Eigenschaften eines Hüllenoperators erfüllt die Abbildung

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,T\longmapsto \operatorname {Nachf} {\left(T\right)},$

welche nicht?

Auf einer Menge ${}M$ nennt man eine Abbildung

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,T\longmapsto {\overline {T}},$

einen topologischen Hüllenoperator, wenn die folgenden Eigenschaften für alle Teilmengen ${}S,T\subseteq M$ gelten.

1. ${}T\subseteq {\overline {T}}\,.$

2. ${}{\overline {S\cup T}}={\overline {S}}\cup {\overline {T}}\,.$

3. ${}{\overline {\emptyset }}=\emptyset \,.$

4. ${}{\overline {\overline {T}}}={\overline {T}}\,.$

Aufgabe

Zeige die folgenden Aussagen.

1. Es sei ${}M$ ein topologischer Raum. Dann ist die Zuordnung

   ${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,T\longmapsto {\overline {T}}:=\bigcap _{T\subseteq A,\,A{\text{ abgeschlossen }}}A,$

   die also einer Teilmenge ihren Abschluss (oder ihre abgeschlossene Hülle) zuordnet, ein topologischer Hüllenoperator.

2. Auf ${}M$ sei ein topologischer Hüllenoperator gegeben. Dann erhält man eine Topologie auf ${}M$, indem man die Teilmengen mit ${}A={\overline {A}}$ als abgeschlossen erklärt.

Aufgabe

Es sei ${}(M,R)$ ein gerichteter Graph. Wie kann man graphentheoretisch charakterisieren, dass die Abbildung

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,T\longmapsto \operatorname {Nachf} {\left(T\right)},$

ein topologischer Hüllenoperator ist?

Aufgabe *

Zeige, dass ein gerichteter Graph genau dann symmetrisch ist, wenn für jede Teilmenge ${}T\subseteq M$ die Beziehung

${}T\subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,$

gilt.

Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Zeige, dass das modallogische Leerheitsaxiom das Autismusaxiom und dass das Autismusaxiom das Phantasiearmutsaxiom impliziert. Zeige ferner, dass diese Implikationen nicht umkehrbar sind.

Aufgabe (2 Punkte)

Zeige, dass eine fatalistische ${}K$- Modallogik, die einen paradoxen Ausdruck enthält, bereits widersprüchlich ist.

Aufgabe (2 Punkte)

Zeige, dass das Löb-Axiom paradox ist.

Aufgabe (4 Punkte)

Zeige, dass für einen gerichteten Graphen ${}(M,R)$ die folgenden Eigenschaften äquivalent sind.

1. ${}(M,R)$ ist reflexiv und euklidisch.
2. ${}(M,R)$ ist symmetrisch, transitiv und sackgassenfrei.
3. ${}(M,R)$ ist eine Äquivalenzrelation.

Aufgabe (2 Punkte)

Zeige, dass ein gerichteter Graph ${}(M,R)$ genau dann transitiv ist, wenn für die Nachfolgermengen zu jeder Teilmenge ${}T\subseteq M$ die Beziehung

${}\operatorname {Nachf} {\left(\operatorname {Nachf} {\left(T\right)}\right)}\subseteq \operatorname {Nachf} {\left(T\right)}\,$

gilt.