Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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.
}
{} {}