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

\setcounter{section}{25}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Zeige, dass in einem $K$-\definitionsverweis {System}{}{,} in dem das Axiomenschema
\mathdisp {\Box \alpha \rightarrow \Box \neg \alpha} { }
gilt, bereits das \definitionsverweis {Leerheitsaxiom}{}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Zeige die Äquivalenz \zusatzklammer {innerhalb der $K$-\definitionsverweis {Modallogik}{}{}} {} {} der folgenden modallogischen Axiomenschemata. \aufzaehlungvier{Das \definitionsverweis {Reflexivitätsaxiom}{}{} ist äquivalent zu
\mathdisp {\alpha \rightarrow \Diamond \alpha} { . }
}{Das \definitionsverweis {Symmetrieaxiom}{}{} ist äquivalent zu
\mathdisp {\Diamond \Box \alpha \rightarrow \alpha} { . }
}{Das \definitionsverweis {Transitivitätsaxiom}{}{} ist äquivalent zu
\mathdisp {\Diamond \Diamond \alpha \rightarrow \Diamond \alpha} { . }
}{Das \definitionsverweis {euklidische Axiom}{}{} ist äquivalent zu
\mathdisp {\Diamond \Box \alpha \rightarrow \Box \alpha} { . }
}

}
{} {}

Zur folgenden Aufgabe vergleiche auch Aufgabe 22.17.


\inputaufgabegibtloesung
{}
{

Es sei $M$ ein $K$-\definitionsverweis {modallogisches System}{}{,} in dem zusätzlich das \definitionsverweis {Transitivitätsaxiom}{}{} gelte. Ferner sei $s$ ein modallogischer Ausdruck, für den
\mathdisp {M \vdash \neg \Box s \leftrightarrow s} { }
gelte. Zeige für einen beliebigen Ausdruck $p$ die Ableitbarkeit
\mathdisp {M \vdash \neg \Box (p \wedge \neg p ) \rightarrow \neg \Box s} { . }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass das \definitionsverweis {Löb-Axiom}{}{} äquivalent zu
\mathdisp {\vdash \Diamond \alpha \rightarrow \Diamond (\alpha \wedge \neg \Diamond \alpha )} { }
ist.

}
{} {}

\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Socrates Louvre.jpg} }
\end{center}
\bildtext {Die Aussage \anfuehrung{ich weiß, dass ich nichts weiß}{} wird Sokrates zugeschrieben. In einer epistemischen $K$-Modallogik folgt daraus, dass Sokrates alles weiß.} }

\bildlizenz { Socrates Louvre.jpg } {} {Sting} {Commons} {CC-by-sa 2.5} {}

\inputaufgabegibtloesung
{}
{

Wir interpretieren den Satz von Sokrates, \anfuehrung{Ich weiß, dass ich nichts weiß}{,} als modallogisches Axiomenschema
\mathdisp {\Box \neg \Box \alpha} { . }
Zeige die folgenden Aussagen. \aufzaehlungdrei{Dieses Axiomenschema ist \definitionsverweis {paradox}{}{.} }{Dieses Axiomenschema ist innerhalb der $K$-\definitionsverweis {Modallogik}{}{} äquivalent zu
\mathdisp {\Box \Diamond \alpha} { . }
}{Dieses Axiomenschema ist innerhalb der $K$-\definitionsverweis {Modallogik}{}{} äquivalent zu
\mathdisp {\Box \alpha} { , }
also zum \definitionsverweis {Leerheitsaxiom}{}{.} }

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $\Gamma$ die durch das \definitionsverweis {Löb-Axiom}{}{} gegebene $K$-\definitionsverweis {Modallogik}{}{,} also die Beweisbarkeitslogik. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \bot }
{ \defeq} { p \wedge \neg p }
{ } { }
{ } { }
{ } { }
} {}{}{} \zusatzklammer {als Abkürzung für einen Widerspruch} {} {.} Zeige, dass
\mathdisp {\Gamma \vdash \neg \Box \neg \Box \bot \leftrightarrow \neg \Box \bot} { }
ableitbar ist.

}
{} {}

\inputaufgabe
{}
{

Es sei $\Gamma$ eine Menge von \definitionsverweis {modallogischen Ausdrücken}{}{,} die allesamt nicht \definitionsverweis {paradox}{}{} seien und es sei
\mathdisp {\Gamma \vdash \alpha} { }
eine \definitionsverweis {Ableitung}{}{.} Zeige, dass $\alpha$ ebenfalls nicht paradox ist.

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Zeige, dass ein \definitionsverweis {gerichteter Graph}{}{,} der sowohl \definitionsverweis {euklidisch}{}{} als auch \definitionsverweis {symmetrisch}{}{} ist, auch \definitionsverweis {transitiv}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass ein \definitionsverweis {gerichteter Graph}{}{} $(M,R)$ genau dann \definitionsverweis {reflexiv}{}{} ist, wenn für die \definitionsverweis {Nachfolgermengen}{}{} zu jeder Teilmenge
\mavergleichskette
{\vergleichskette
{T }
{ \subseteq }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ T }
{ \subseteq} { \operatorname{Nachf} { \left( T \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}
{} {}

Auf einer Menge $M$ nennt man eine Abbildung \maabbeledisp {} { \mathfrak {P} \, (M ) } { \mathfrak {P} \, (M ) } {T} { \overline{T} } {,} einen \definitionswort {Hüllenoperator}{,} wenn die folgende Eigenschaften für alles Teilmengen
\mathl{S,T \subseteq M}{} gelten. \aufzaehlungdrei{
\mavergleichskettedisp
{\vergleichskette
{T }
{ \subseteq} { \overline{T} }
{ } { }
{ } { }
{ } { }
} {}{}{.} }{Mit
\mavergleichskettedisp
{\vergleichskette
{S }
{ \subseteq} {T }
{ } { }
{ } { }
{ } { }
} {}{}{} ist auch
\mavergleichskettedisp
{\vergleichskette
{\overline{S} }
{ \subseteq} { \overline{T} }
{ } { }
{ } { }
{ } { }
} {}{}{.} }{
\mavergleichskettedisp
{\vergleichskette
{\overline{\overline{T} } }
{ =} { \overline{T} }
{ } { }
{ } { }
{ } { }
} {}{}{.} }

\inputaufgabe
{}
{

Es sei
\mathl{(M,R)}{} ein \definitionsverweis {gerichteter Graph}{}{.} Welche der Eigenschaften eines \definitionsverweis {Hüllenoperators}{}{} erfüllt die Abbildung \maabbeledisp {} { \mathfrak {P} \, (M ) } { \mathfrak {P} \, (M ) } {T} { \operatorname{Nachf} { \left( T \right) } } {,} welche nicht?

}
{} {}

Auf einer Menge $M$ nennt man eine Abbildung \maabbeledisp {} { \mathfrak {P} \, (M ) } { \mathfrak {P} \, (M ) } {T} { \overline{T} } {,} einen \definitionswort {topologischen Hüllenoperator}{,} wenn die folgenden Eigenschaften für alle Teilmengen
\mathl{S,T \subseteq M}{} gelten. \aufzaehlungvier{
\mavergleichskettedisp
{\vergleichskette
{T }
{ \subseteq} { \overline{T} }
{ } { }
{ } { }
{ } { }
} {}{}{.} }{
\mavergleichskettedisp
{\vergleichskette
{\overline{S \cup T} }
{ =} { \overline{S} \cup \overline{T} }
{ } { }
{ } { }
{ } { }
} {}{}{.} }{
\mavergleichskettedisp
{\vergleichskette
{\overline{\emptyset} }
{ =} {\emptyset }
{ } { }
{ } { }
{ } { }
} {}{}{.} }{
\mavergleichskettedisp
{\vergleichskette
{\overline{\overline{T} } }
{ =} { \overline{T} }
{ } { }
{ } { }
{ } { }
} {}{}{.} }

\inputaufgabe
{}
{

Zeige die folgenden Aussagen. \aufzaehlungzwei {Es sei $M$ ein \definitionsverweis {topologischer Raum}{}{.} Dann ist die Zuordnung \maabbeledisp {} { \mathfrak {P} \, (M ) } { \mathfrak {P} \, (M ) } {T} { \overline{T} \defeq \bigcap_{T \subseteq A, \, A \text{ abgeschlossen } } A } {,} die also einer Teilmenge ihren \definitionsverweis {Abschluss}{}{} \zusatzklammer {oder ihre abgeschlossene Hülle} {} {} zuordnet, ein \definitionsverweis {topologischer Hüllenoperator}{}{.} } {Auf $M$ sei ein topologischer Hüllenoperator gegeben. Dann erhält man eine Topologie auf $M$, indem man die Teilmengen mit
\mavergleichskette
{\vergleichskette
{A }
{ = }{ \overline{A} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} als abgeschlossen erklärt. }

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{(M,R)}{} ein \definitionsverweis {gerichteter Graph}{}{.} Wie kann man graphentheoretisch charakterisieren, dass die Abbildung \maabbeledisp {} { \mathfrak {P} \, (M ) } { \mathfrak {P} \, (M ) } {T} { \operatorname{Nachf} { \left( T \right) } } {,} ein \definitionsverweis {topologischer Hüllenoperator}{}{} ist?

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{4}
{

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

}
{} {}

\inputaufgabe
{2}
{

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

}
{} {}

\inputaufgabe
{2}
{

Zeige, dass das \definitionsverweis {Löb-Axiom}{}{} \definitionsverweis {paradox}{}{} ist.

}
{} {}

\inputaufgabe
{4}
{

Zeige, dass für einen \definitionsverweis {gerichteten Graphen}{}{} $(M,R)$ die folgenden Eigenschaften äquivalent sind. \aufzaehlungdrei{$(M,R)$ ist \definitionsverweis {reflexiv}{}{} und \definitionsverweis {euklidisch}{}{.} }{$(M,R)$ ist \definitionsverweis {symmetrisch}{}{,} \definitionsverweis {transitiv}{}{} und sackgassenfrei. }{$(M,R)$ ist eine \definitionsverweis {Äquivalenzrelation}{}{.} }

}
{} {}

\inputaufgabe
{2}
{

Zeige, dass ein \definitionsverweis {gerichteter Graph}{}{} $(M,R)$ genau dann \definitionsverweis {transitiv}{}{} ist, wenn für die \definitionsverweis {Nachfolgermengen}{}{} zu jeder Teilmenge
\mavergleichskette
{\vergleichskette
{T }
{ \subseteq }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Nachf} { \left( \operatorname{Nachf} { \left( T \right) } \right) } }
{ \subseteq} { \operatorname{Nachf} { \left( T \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}
{} {}