Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 26/latex
\setcounter{section}{26}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Baby Category 2.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Baby Category 2.svg } {} {Melikamp} {Commons} {CC-by-sa 3.0} {}
Für die Aussagenvariablen
\mathl{p,q,r}{} gelte
\mathdisp {a \vDash \neg p, q, r \text{ und } b \vDash \neg p ,\neg q, r} { . }
Bestimme in beiden Weltpunkten die Wahrheitswerte von
\aufzaehlungvier{
\mathl{p \rightarrow \Box r}{,}
}{
\mathl{\Box q \rightarrow (\Box p \rightarrow \Box (r \wedge p))}{,}
}{
\mathl{( p \vee \Box \Box r ) \rightarrow \Diamond r}{,}
}{
\mathl{\Diamond \Box \neg q \rightarrow ( \Box \Diamond r \vee \neg p )}{.}
}
}
{} {}
\inputaufgabe
{}
{
Definiere die modallogische Verschachtelungstiefe für modallogische Ausdrücke.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass bei einer Belegung der Aussagenvariablen durch die Definition 26.2 der Wahrheitswert für jeden modallogischen Ausdruck in jedem Punkt eines modallogischen Modelles eindeutig festgelegt ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{(M,R)}{} der triviale Graph in dem Sinne, dass $M$ einpunktig ist und dieser Punkt mit sich in Relation steht. Zeige, dass
\mathdisp {(M,R) \vDash \alpha} { }
genau dann bei jeder Belegung gilt, wenn $\alpha$ nicht
\definitionsverweis {paradox}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige durch Angabe eines
\definitionsverweis {modallogischen Modelles}{}{,}
dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {\Box ( p \vee q) \rightarrow \Box p \vee \Box q} { }
nicht
\definitionsverweis {ableitbar}{}{}
ist
\zusatzklammer {dabei seien $p,q$ Aussagenvariablen} {} {.}
}
{} {}
\inputaufgabe
{}
{
Zeige durch Angabe eines
\definitionsverweis {modallogischen Modelles}{}{,}
dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {( \alpha \rightarrow \beta ) \rightarrow ( \Box \alpha \rightarrow \Box \beta )} { }
nicht
\definitionsverweis {ableitbar}{}{}
ist. Insbesondere lässt sich also
Lemma 24.5 (1)
nicht internalisieren.
}
{} {}
\inputaufgabe
{}
{
Zeige durch Angabe eines
\definitionsverweis {modallogischen Modelles}{}{,}
dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {( \Box \alpha \rightarrow \Box \beta ) \rightarrow ( \Diamond \alpha \rightarrow \Diamond \beta )} { }
nicht
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Zeige durch Angabe eines
\definitionsverweis {modallogischen Modelles}{}{,}
dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {( \Box \alpha \rightarrow \Box \beta ) \rightarrow ( \alpha \rightarrow \beta )} { }
nicht
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Zeige durch Angabe eines
\definitionsverweis {modallogischen Modelles}{}{,}
dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {\Box ( \alpha \rightarrow \beta ) \rightarrow ( \alpha \rightarrow \beta )} { }
nicht
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Zeige semantisch, dass eine $K$-\definitionsverweis {Modallogik}{}{,} in der das \definitionsverweis {Möglichkeitsaxiom}{}{} und das \definitionsverweis {Löb-Axiom}{}{} gelten, bereits widersprüchlich ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{r
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Charakterisiere das
\definitionsverweis {modallogische}{}{}
Axiomenschema
\mathdisp {\vdash \alpha \leftrightarrow \Diamond^r \alpha} { }
graphentheoretisch.
}
{} {}
\inputaufgabe
{}
{
Es seien
\mavergleichskette
{\vergleichskette
{r,s
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Charakterisiere das
\definitionsverweis {modallogische}{}{}
Axiomenschema
\mathdisp {\vdash \Diamond^r \alpha \rightarrow \Diamond^s \alpha} { }
graphentheoretisch.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass für eine modallogische Aussage $\alpha$ die folgenden Aussagen äquivalent sind.
\aufzaehlungdrei{Es ist
\mathl{S5 \vdash \alpha}{.}
}{Es ist
\mathl{(M,R) \vDash \alpha}{} für jede
\definitionsverweis {Äquivalenzrelation}{}{}
$R$ auf einer Menge $M$.
}{Es ist
\mathl{(M,R) \vDash \alpha}{} für jede volle Relation $R$ auf einer Menge $M$.
}
}
{} {}
\inputaufgabegibtloesung
{}
{
Zu einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{} und einem modallogischen Ausdruck $\alpha$ setzen wir
\mavergleichskettedisp
{\vergleichskette
{M( \alpha )
}
{ =} { { \left\{ w \in M \mid w \vDash \alpha \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige
\mavergleichskettedisp
{\vergleichskette
{M( \Diamond \alpha )
}
{ =} { \operatorname{Vorg} { \left( M( \alpha ) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{} {}
\inputaufgabe
{}
{
Zu einem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R,\mu)}{} und einem modallogischen Ausdruck $\alpha$ setzen wir
\mavergleichskettedisp
{\vergleichskette
{M( \alpha )
}
{ =} { { \left\{ w \in M \mid w \vDash \alpha \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige, dass
\mathdisp {(M,R,\mu) \vDash \alpha \rightarrow \beta} { }
genau dann gilt, wenn
\mavergleichskettedisp
{\vergleichskette
{M( \alpha)
}
{ \subseteq} { M(\beta)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{}
{
Beweise Satz 26.10 mit Hilfe von Aufgabe 26.14 und Aufgabe 26.15 und mit geeigneten Charakterisierungen von relationstheoretischen Eigenschaften mit Vorgängermengen.
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{6}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Relación binaria 01.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Relación binaria 01.svg } {} {HiTe} {Commons} {gemeinfrei} {}
Für die Aussagenvariablen
\mathl{p,q,r}{} gelte
\mathdisp {a \vDash \neg p, q, \neg r \, , b \vDash \neg p,\neg q, r \, , c \vDash \neg p, \neg q, r \, , d \vDash p, q, r} { . }
Bestimme in den vier Weltpunkten die Wahrheitswerte von
\aufzaehlungdrei{
\mathl{\Diamond q \rightarrow (\Box p \rightarrow \Box (r \wedge p))}{,}
}{
\mathl{( p \vee \Box \Box \neg r ) \rightarrow \Diamond (\neg p \rightarrow r )}{,}
}{
\mathl{\Box \Diamond \Box \neg q \rightarrow ( \Box \Diamond r \vee \neg p )}{.}
}
}
{} {}
\inputaufgabe
{2}
{
Zeige, dass in jedem
\definitionsverweis {modallogischen Modell}{}{}
\mathl{(M,R, \mu)}{} das Schema
\mathdisp {\Box \alpha \wedge \Diamond \beta \rightarrow \Diamond \alpha} { }
gilt.
}
{} {}
\inputaufgabe
{2}
{
Zeige durch Angabe eines
\definitionsverweis {modallogischen Modelles}{}{,}
dass im
$K$-\definitionsverweis {System}{}{}
der Ausdruck
\mathdisp {( \alpha \rightarrow \beta ) \rightarrow ( \Diamond \alpha \rightarrow \Diamond \beta )} { }
nicht
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabe
{2}
{
Zeige durch Angabe eines \definitionsverweis {modallogischen Modelles}{}{,} dass das \definitionsverweis {System S4}{}{} nicht äquivalent zum \definitionsverweis {System S5}{}{} ist.
}
{} {}
\inputaufgabe
{3}
{
Charakterisiere die modallogischen Rahmen, in denen
\zusatzklammer {bei jeder Wahrheitsbelegung} {} {}
das Axiomenschema
\mathdisp {\alpha \rightarrow \Diamond \Box \alpha} { }
gilt.
}
{} {}
\inputaufgabe
{3}
{
Zeige, dass aus dem
$K$-\definitionsverweis {modallogischen}{}{}
Axiomenschema
\mathdisp {\alpha \rightarrow \Diamond \Box \alpha} { }
nicht das Axiomenschema
\mathdisp {\alpha \rightarrow \Box\Diamond \alpha} { }
ableitbar ist.
}
{} {}
\inputaufgabe
{5}
{
Zeige die folgenden modelltheoretischen Charakterisierungen für modallogische Axiomenschemata.
\aufzaehlungfuenf{In einem
\definitionsverweis {gerichteten Graphen}{}{}
\mathl{(M,R)}{} gilt das
\definitionsverweis {Leerheitsaxiom}{}{}
genau dann, wenn die Relation $R$ leer ist
\zusatzklammer {wenn es also gar keine Pfeile gibt} {} {.}
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Autismusaxiom}{}{}
genau dann, wenn $R$ nur aus Schleifen besteht.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Fatalismusaxiom}{}{}
genau dann, wenn $R$ genau aus allen Schleifen besteht.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Phantasiearmutsaxiom}{}{}
genau dann, wenn von jedem Punkt höchstens ein Pfeil ausgeht.
}{In einem gerichteten Graphen
\mathl{(M,R)}{} gilt das
\definitionsverweis {Ideologieaxiom}{}{}
genau dann, wenn von jedem Punkt genau ein Pfeil ausgeht.
}
}
{} {}