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

\setcounter{section}{24}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Überprüfe, um die folgenden Wörter korrekt gebildete \zusatzklammer {einschließlich Klammerung} {} {} modallogische Ausdrücke sind. \aufzaehlungvier{
\mathl{\Box ( (p) \wedge (q))}{,} }{
\mathl{(p) \rightarrow \Box (q)}{,} }{
\mathl{(p) \rightarrow (\Box (q))}{,} }{
\mathl{(\Diamond (p)) \rightarrow ( (\Box (q)) \rightarrow (r))}{.} }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass das $K$-\definitionsverweis {Axiom}{}{} äquivalent zu
\mathdisp {\vdash \Diamond \alpha \rightarrow ( \Diamond \neg \beta \vee \Diamond (\alpha \wedge \beta) )} { }
ist.

}
{} {}

\inputaufgabe
{}
{

Formuliere die in Bemerkung 23.7 aufgeführten Eigenschaften für das \definitionsverweis {Ableitungsprädikat}{}{} in der Sprache der Modallogik.

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass im $K$-\definitionsverweis {System}{}{} der Ausdruck
\mathdisp {\Box ( \alpha \rightarrow \beta ) \rightarrow ( \Diamond \alpha \rightarrow \Diamond \beta )} { }
\definitionsverweis {ableitbar}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Wir betrachten eine formale Modallogik, die durch das Axiomenschema
\mathdisp {\vdash \Box \alpha \leftrightarrow \neg \alpha} { }
gegeben sei. \aufzaehlungdrei{Erfüllt diese Modallogik das \definitionsverweis {Axiomenschema K}{}{?} }{Erfüllt diese Modallogik die \definitionsverweis {Nezessisierungsregel}{}{?} }{Erfüllt diese Modallogik das \definitionsverweis {Ideologieaxiom}{}{?} }

}
{} {}

\inputaufgabe
{}
{

Es sei \mathkor {} {p_i} {} {i \in I} {,} eine Familie von Aussagenvariablen und sei $L$ die zugehörige modallogische Sprache. Es sei $S$ ein prädikatenlogisches Symbolalphabet, das unter anderem Konstanten
\mathbed {c_i} {}
{i \in I} {}
{} {} {} {,} und eine fixierte Variable $x$ enthalte. \aufzaehlungdrei{Definiere eine natürliche injektive Abbildung \maabbdisp {\Psi} {L} {L^S } {,} bei der $p_i$ auf
\mathl{x=c_i}{} und $\Box \alpha$ auf
\mathl{\forall x \Psi( \alpha )}{} abgebildet wird. }{Was ist
\mathl{\Psi( \Diamond \alpha )}{?} }{Zeige, dass zu jeder in der $K$-\definitionsverweis {Modallogik}{}{} ableitbaren modallogischen Aussage $\alpha$ auch
\mathl{\Psi (\alpha )}{} im Prädikatenkalkül ableitbar ist. }

}
{} {}

\inputaufgabe
{}
{

\aufzaehlungzwei {Zeige, dass in einer $K$-\definitionsverweis {Modallogik}{}{} das Axiomenschema
\mathdisp {\Diamond (\alpha \wedge \beta) \rightarrow \Diamond \alpha \wedge \Diamond \beta} { }
gilt. } {Zeige, dass in einer $K$-Modallogik das Axiomenschema
\mathdisp {\Diamond \alpha \wedge \Diamond \beta \rightarrow \Diamond (\alpha \wedge \beta)} { }
nicht gelten muss. }

}
{} {}

\inputaufgabe
{}
{

\aufzaehlungzwei {Zeige, dass in einer $K$-\definitionsverweis {Modallogik}{}{} das Axiomenschema
\mathdisp {\Diamond \alpha \vee \Diamond \beta \rightarrow \Diamond (\alpha \vee \beta)} { }
gilt. } {Zeige, dass in einer $K$-Modallogik das Axiomenschema
\mathdisp {\Diamond (\alpha \vee \beta) \rightarrow \Diamond \alpha \vee \Diamond \beta} { }
nicht gelten muss. }

}
{} {}

Zur folgenden Aufgabe vergleiche auch Aufgabe 11.21.


\inputaufgabe
{}
{

Zeige, dass in einer $K$-\definitionsverweis {Modallogik}{}{} das Axiomenschema
\mathdisp {\Diamond ( \alpha \rightarrow \beta ) \rightarrow ( \Diamond \alpha \rightarrow \Diamond \beta)} { }
nicht gelten muss.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat mit
\mathdisp {\Gamma \vdash \alpha (n)} { }
für alle
\mathl{n \in \N}{.} Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat mit
\mathdisp {\Gamma \vdash \neg \alpha (n)} { }
für alle
\mathl{n \in \N}{.} Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\inputaufgabe
{}
{

Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x) }
{ \defeq} {\exists y { \left( x = y+y \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{} und es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige \zusatzklammer {ohne den Fixpunktsatz zu verwenden} {} {,} dass es einen Satz
\mathl{q \in L^{\rm Ar}_0}{} mit
\mathdisp {PA \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei $k$ eine fixierte positive natürliche Zahl und es sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha (x) }
{ \defeq} {\exists y { \left( x = k y \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{,} wobei $ky$ als die $k$-fache Addition von $y$ mit sich selbst realisiert werde. Es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige \zusatzklammer {ohne den Fixpunktsatz zu verwenden} {} {,} dass es einen Satz
\mathl{q \in L^{\rm Ar}_0}{} mit
\mathdisp {PA \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{2}
{

Überprüfe, um die folgenden Wörter korrekt gebildete \zusatzklammer {einschließlich Klammerung} {} {} modallogische Ausdrücke sind. \aufzaehlungvier{
\mathl{\Box ( (p) \wedge (q)}{,} }{
\mathl{(p) \rightarrow \Diamond ( (q) \vee (r))}{,} }{
\mathl{(\Box (\Box ((p)))) \rightarrow (\Box (q))}{,} }{
\mathl{((\Diamond (p)) \rightarrow ( (\Box (q)) \rightarrow (r)))}{.} }

}
{} {}

\inputaufgabe
{2}
{

Zeige, dass in einer $K$-\definitionsverweis {Modallogik}{}{}
\mathdisp {\vdash \Diamond \neg \neg \alpha \leftrightarrow \neg \neg \Diamond \alpha} { }
ableitbar ist.

}
{} {}

\inputaufgabe
{2}
{

Zeige, dass die $K$-\definitionsverweis {Modallogik}{}{} widerspruchsfrei ist.

}
{} {}

\inputaufgabe
{4 (2+2)}
{

Es sei $\Gamma$ eine arithmetische Ausdrucksmenge und
\mathl{\alpha}{} ein einstelliges Prädikat. \aufzaehlungzwei {Es gelte
\mathdisp {\Gamma \vdash \alpha (n)} { }
für endlich viele
\mathl{n \in \N}{} und für alle übrigen natürlichen Zahlen gelte
\mathdisp {\Gamma \vdash \neg \alpha (n)} { . }
Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt. } {Es gelte
\mathdisp {\Gamma \vdash \neg \alpha (n)} { }
für endlich viele
\mathl{n \in \N}{} und für alle übrigen natürlichen Zahlen gelte
\mathdisp {\Gamma \vdash \alpha (n)} { . }
Zeige, dass es einen Satz $q$ mit
\mathdisp {\Gamma \vdash \alpha(GN(q)) \leftrightarrow q} { }
gibt. }

}
{} {}