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

\setcounter{section}{4}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$ und
\mathl{\alpha \in L^V}{.} Es gelte
\mathl{\Gamma \vdash \alpha}{.} Zeige, dass es dann auch eine endliche Teilmenge
\mavergleichskette
{\vergleichskette
{\Delta }
{ \subseteq }{\Gamma }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mathl{\Delta \vdash \alpha}{} gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^V}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer Aussagenvariablenmenge $V$. Es gelte
\mathl{p \rightarrow q \in \Gamma}{} und
\mathl{q \rightarrow r \in \Gamma}{.} Folgt daraus
\mathl{p \rightarrow r \in \Gamma}{?}

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ = }{ \{ p, \neg q, r \rightarrow s \} }
{ \subseteq }{ L^V }
{ }{ }
{ }{ }
} {}{}{} \zusatzklammer {\mathlk{p,q,r,s}{} seien \definitionsverweis {Aussagenvariablen}{}{}} {} {.} Welche der folgenden Aussagen lassen sich aus $\Gamma$ \definitionsverweis {ableiten}{}{?}
\mathdisp {p \rightarrow q,\, \neg p \rightarrow q,\, p \rightarrow \neg q,\, \neg p \rightarrow \neg q,\, r \rightarrow q,\, { \left( r \rightarrow q \right) } \rightarrow \neg p, \, { \left( s \rightarrow p \right) } \rightarrow { \left( r \rightarrow \neg q \right) } , \, { \left( \neg q \rightarrow \neg p \right) } \rightarrow s} { . }

}
{} {}

\inputaufgabe
{}
{

Zeige, dass man aus
\mathl{\Gamma=\{p\}}{} unendlich viele Aussagen ableiten kann, die keine \definitionsverweis {Tautologien}{}{} sind.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$. Zeige
\mavergleichskettedisp
{\vergleichskette
{ \Gamma^\vdash }
{ =} { { \left( \Gamma^\vdash \right) }^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer Aussagenvariablenmenge $V$. Zeige die folgenden Regeln für die \definitionsverweis {Ableitungsbeziehung}{}{} \zusatzklammer {dabei seien \mathlk{\alpha, \beta, \gamma, \alpha_i}{} Aussagen} {} {.} \aufzaehlungsieben{Konjunktionsregel:
\mathl{\Gamma \vdash \alpha \wedge \beta}{} genau dann, wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \beta}{.} }{Kettenschlussregel: Wenn
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{} und
\mathl{\Gamma \vdash \beta \rightarrow \gamma}{,} dann auch
\mathl{\Gamma \vdash \alpha \rightarrow \gamma}{.} }{Modus ponens: Wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{,} dann ist auch
\mathl{\Gamma \vdash \beta}{.} }{Wenn
\mathl{\Gamma \vdash \alpha}{,} so auch
\mathl{\Gamma \vdash \beta \rightarrow \alpha}{.} }{Wenn
\mathl{\Gamma \vdash \alpha_1 , \ldots , \Gamma \vdash \alpha_n}{} und
\mathl{\Gamma \vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \beta}{,} dann auch
\mathl{\Gamma \vdash \beta}{.} }{Widerspruchsregel: Wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \neg \alpha}{,} dann auch
\mathl{\Gamma \vdash \beta}{.} }{Fallunterscheidungsregel: Wenn
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{} und
\mathl{\Gamma \vdash \neg \alpha \rightarrow \beta}{,} dann auch
\mathl{\Gamma \vdash \beta}{.} }

}
{} {}

\inputaufgabe
{}
{

Es sei $V=\{ p,q,r\}$ eine \definitionsverweis {Aussagenvariablenmenge}{}{.} Welche der folgenden Aussagen aus $L^V$ lassen sich aus
\mavergleichskette
{\vergleichskette
{\Gamma }
{ = }{V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \definitionsverweis {ableiten}{}{?} \aufzaehlungsieben{
\mathdisp {p} { , }
}{
\mathdisp {p \wedge q \rightarrow r} { , }
}{
\mathdisp {\neg p \wedge q \rightarrow r} { , }
}{
\mathdisp {\neg p \wedge \neg q \rightarrow \neg r} { , }
}{
\mathdisp {p \rightarrow ( q \rightarrow r)} { , }
}{
\mathdisp {p \rightarrow ( q \rightarrow \neg r)} { , }
}{
\mathdisp {\neg q} { . }
}

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma_1 }
{ = }{ \{ p \wedge q \rightarrow r \} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{\Gamma_2 }
{ = }{ \{ p \rightarrow ( q\rightarrow r )\} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Zeige
\mavergleichskettedisp
{\vergleichskette
{\Gamma_1^\vdash }
{ =} {\Gamma_2^\vdash }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{\Gamma \subseteq L^V}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} über einer Aussagenvariablenmenge $V$ und es seien
\mathl{\alpha, \beta \in L^V}{.} Zeige, dass
\mathdisp {\Gamma \cup \{ \alpha \} \vdash \beta} { }
zu
\mathdisp {\Gamma \vdash \alpha \rightarrow \beta} { }
äquivalent ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{\Gamma \subseteq L^V}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} über einer Aussagenvariablenmenge $V$ und es sei
\mathl{\alpha \in L^V}{.} Es gelte
\mathdisp {\Gamma \not \vdash \alpha} { . }
Zeige, dass dann
\mathdisp {\Gamma \cup \{ \neg \alpha \}} { }
\definitionsverweis {widerspruchsfrei}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es seien
\mavergleichskette
{\vergleichskette
{\Gamma_1, \Gamma_2 }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} Ausdrucksmengen in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$ und seien
\mathl{\alpha, \beta \in L^V}{.} \aufzaehlungzwei {Es gelte
\mathl{\Gamma_1 \vdash \alpha}{} und
\mathl{\Gamma_2 \vdash \beta}{.} Zeige
\mathl{\Gamma_1 \cup \Gamma_2 \vdash \alpha \wedge \beta}{.} } {Es gelte
\mathl{\Gamma_1 \vdash \alpha}{} und
\mathl{\Gamma_2 \vdash \alpha}{.} Folgt daraus
\mathl{\Gamma_1 \cap \Gamma_2 \vdash \alpha}{?} }

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{n\in \N_+}{.} Man gebe ein Beispiel für eine aussagenlogische \definitionsverweis {widersprüchliche}{}{} Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma }
{ =} {\{ \alpha_1,\alpha_2 , \ldots , \alpha_n \} }
{ } { }
{ } { }
{ } { }
} {}{}{} derart, dass jede echte Teilmenge davon \definitionsverweis {widerspruchsfrei}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$. Zeige, dass die \definitionsverweis {Ableitungsbeziehung}{}{}
\mathl{\Gamma \vdash \alpha}{} die \definitionsverweis {Folgerungsbeziehung}{}{}
\mathl{\Gamma \vDash \alpha}{} impliziert.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Gamma }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$ und es sei
\mathl{\alpha \in L^V}{.} Es gebe eine Interpretation $I$ mit
\mathl{I \vDash \Gamma}{} und
\mathl{I \vDash \neg \alpha}{.} Zeige
\mathl{\Gamma \not\vdash \alpha}{.}

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mathl{L^V}{} die \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$ und es sei $\lambda$ eine \definitionsverweis {Wahrheitsbelegung}{}{} der Variablen mit zugehöriger \definitionsverweis {Interpretation}{}{} $I$. Zeige, dass $I^\vDash$ \definitionsverweis {maximal widerspruchsfrei}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Führe die Einzelheiten im Beweis zu Lemma 4.7 für die Implikation durch.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{\Delta }
{ \subseteq }{L^V }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$, die zu jeder Aussagenvariablen
\mathl{p \in V}{} entweder $p$ oder $\neg p$ enthalte. Zeige, dass $\Delta^\vdash$ \definitionsverweis {maximal widerspruchsfrei}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\Gamma \subseteq L^V}{} eine widerspruchsfreie, aber nicht maximal widerspruchsfreie Aussagenmenge, die unter Ableitungen abgeschlossen sei. Zeige, dass $\Gamma$ nicht durch die Hinzunahme von endlich vielen Aussagen zu einer maximal widerspruchsfreien Aussagenmenge aufgefüllt werden kann.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{3}
{

Es sei
\mathl{\Gamma =\{ p, \neg q \rightarrow r \} \subseteq L^V}{} \zusatzklammer {\mathlk{p,q,r}{} seien \definitionsverweis {Aussagenvariablen}{}{}} {} {.} Welche der folgenden Aussagen lassen sich aus $\Gamma$ \definitionsverweis {ableiten}{}{?}
\mathdisp {p \rightarrow q,\, \neg q \rightarrow p ,\, \neg p \rightarrow r,\, \neg q \rightarrow r \wedge p ,\, \neg r \rightarrow q,\, r \rightarrow { \left( q \rightarrow \neg p \right) }} { . }

}
{} {}

\inputaufgabe
{3}
{

Es sei $\Gamma \subseteq L^V$ eine Ausdrucksmenge in der \definitionsverweis {Sprache der Aussagenlogik}{}{} zu einer \definitionsverweis {Aussagenvariablenmenge}{}{} $V$. Zeige, dass folgende Aussagen äquivalent sind. \aufzaehlungdrei{ $\Gamma$ ist \definitionsverweis {widersprüchlich}{}{.} }{Für jedes
\mathl{\beta \in L^V}{} ist \mathkor {} {\Gamma \vdash \beta} {und} {\Gamma \vdash \neg \beta} {.} }{Es ist
\mathl{\Gamma^\vdash= L^V}{.} }

}
{} {}

\inputaufgabe
{4}
{

Es sei $p$ eine \definitionsverweis {Aussagenvariable}{}{} und $\alpha \in L^V$ eine Aussage, in der die Variable $p$ nicht vorkommt. Es gelte
\mathdisp {\{p\} \vdash \alpha} { . }
Zeige, dass bereits
\mathdisp {\vdash \alpha} { }
gilt.

}
{} {}

\inputaufgabe
{3}
{

Es sei $V$ eine \definitionsverweis {Aussagenvariablenmenge}{}{.} Konstruiere eine Ausdrucksmenge
\mathl{\Gamma \subseteq L^V}{,} die abgeschlossen unter Ableitungen und nicht \definitionsverweis {maximal widerspruchsfrei}{}{} ist, die aber die Eigenschaft besitzt, dass für jede Aussagenvariable $p$ sowohl $(\Gamma \cup \{p\})^\vdash$ als auch $(\Gamma \cup \{\neg p\})^\vdash$ maximal widerspruchsfrei ist.

}
{} {}