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

\setcounter{section}{4}

\zwischenueberschrift{Übungsaufgaben}

\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.

}
{} {}

\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}{.} }

}
{} {}

\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.

}
{} {}

\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.

}
{} {}

\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
\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.

}
{} {}

\inputaufgabe
{}
{

Bestimme zu jedem Ausdruck
\mathl{\alpha \in L^V}{} mit maximal acht Zeichen zur \definitionsverweis {Aussagenvariablenmenge}{}{}
\mathl{V=\{p,q\}}{,} ob er bei der durch
\mathl{\lambda(p)=1,\, \lambda(q)=0}{} fetgelegten Interpretation wahr oder falsch ist.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

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
{}
{

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
{}
{

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.

}
{} {}