Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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 23.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.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass eine $K$-\definitionsverweis {Modallogik}{}{,} in der das \definitionsverweis {Möglichkeitsaxiom}{}{} und das \definitionsverweis {Löb-Axiom}{}{} gelten, bereits widersprüchlich 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?
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige, dass ein
\definitionsverweis {gerichteter Graph}{}{}
genau dann
\definitionsverweis {symmetrisch}{}{}
ist, wenn für jede Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Beziehung
\mavergleichskettedisp
{\vergleichskette
{T
}
{ \subseteq} { M \setminus \operatorname{Vorg} { \left( M \setminus \operatorname{Vorg} { \left( T \right) } \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\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.
}
{} {}