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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

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

gilt, bereits das Leerheitsaxiom gilt.

Aufgabe Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

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 Referenznummer erstellen

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

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

ist.

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

Aufgabe * Referenznummer erstellen

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 * Aufgabe 25.6 ändern

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 Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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?

Aufgaben zum Abgeben

Aufgabe (4 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe (2 Punkte)Referenznummer erstellen

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

Aufgabe (4 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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.