Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 11/latex
\setcounter{section}{11}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
Beweise allein aus
der Existenzeinführung im Sukzedens
und aussagenlogischen Gesetzen die \stichwort {All\-einführung im Antezedens} {,} also dass für eine Variable $x$, einen Term $t$ und einen Ausdruck $\alpha$
\mathdisp {\vdash \forall x \neg \alpha \rightarrow \neg \alpha { \frac{ t }{ x } }} { }
eine
\definitionsverweis {Tautologie}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Zeige
\mathdisp {\vDash \exists x (x=y)} { . }
}
{} {}
\inputaufgabe
{}
{
Zeige
\mathdisp {\vdash \exists x (x=y)} { . }
}
{} {}
\inputaufgabe
{}
{
Beweise aus
der Existenzeinführung im Antezedens
die \stichwort {All\-einführung im Sukzedens} {.} Sie besagt, dass man aus
\mathdisp {\vdash \beta \rightarrow \alpha \frac{y}{x}} { }
unter der Bedingung, dass $y$ weder in $\forall x \alpha$ noch in $\beta$ frei vorkommt, auf
\mathdisp {\vdash \beta \rightarrow \forall x \alpha} { }
schließen kann.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass der Ausdruck
\mathdisp {{ \left( \alpha { \frac{ y }{ x } } \rightarrow \beta \right) } \rightarrow { \left( \exists x \alpha \rightarrow \beta \right) }} { }
keine
\definitionsverweis {Tautologie}{}{}
ist
\zusatzklammer {auch nicht, wenn $y$ weder in $\exists x \alpha$ noch in $\beta$ frei vorkommt} {} {.}
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{\alpha}{} ein Ausdruck in einer Sprache
\mathl{L^S}{} erster Stufe. Zeige, dass
\mathdisp {\alpha \leftrightarrow \forall x \alpha} { }
keine
\definitionsverweis {Tautologie}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige, dass mit
\mathdisp {\vdash \alpha \rightarrow \beta} { }
auch
\mathdisp {\vdash \forall x \alpha \rightarrow \forall x \beta} { }
gilt.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass in der Prädikatenlogik die \stichwort {All\-einführung im Antezedens} {} ableitbar ist, also dass für eine Variable $x$, einen Term $t$ und einen Ausdruck $\alpha$
\mathdisp {\vdash \forall x \alpha \rightarrow \alpha { \frac{ t }{ x } }} { }
gilt.
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige
\mathdisp {\vdash \forall x \alpha \wedge \forall x \beta \rightarrow \forall x { \left( \alpha \wedge \beta \right) }} { . }
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige
\mathdisp {\vdash \forall x { \left( \alpha \wedge \beta \right) } \rightarrow \forall x \alpha \wedge \forall x \beta} { . }
}
{} {}
\inputaufgabe
{}
{
a) Zeige
\mathdisp {\vdash \exists x (\alpha \wedge \beta) \rightarrow \exists x \alpha \wedge \exists x \beta} { . }
b) Zeige, dass
\mathdisp {\exists x \alpha \wedge \exists x \beta \rightarrow \exists x (\alpha \wedge \beta)} { }
keine
\definitionsverweis {Tautologie}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und
\mathl{f \in S}{} ein $n$-stelliges Funktionssymbol. Erstelle eine Ableitung für den Ausdruck
\mathdisp {\exists y { \left( { \left( fx_1 { \ldots } x_n = y \right) } \wedge \forall z { \left( { \left( fx_1 { \ldots } x_n = z \right) } \rightarrow y = z \right) } \right) }} { . }
}
{} {}
\inputaufgabegibtloesung
{}
{
Es seien
\mathl{A,B,C}{} einstellige Relationssymbole. Zeige, dass der \stichwort {Modus Barbara} {,} also die Aussage
\mathdisp {( \forall x (Ax \rightarrow Bx) \wedge \forall x (Bx \rightarrow Cx) ) \rightarrow ( \forall x (Ax \rightarrow Cx) )} { }
im Prädikatenkalkül
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es seien
\mathl{A,B,C}{} einstellige Relationssymbole. Zeige, dass der \stichwort {Modus Darii} {,} also die Aussage
\mathdisp {( \forall x (Ax \rightarrow Bx) \wedge \exists x (Ax \wedge Cx) ) \rightarrow ( \exists x (Bx \wedge Cx) )} { }
im Prädikatenkalkül
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Im Kalkül der Prädikatenlogik sei
\mathl{\vdash \alpha \rightarrow \beta}{}
\definitionsverweis {ableitbar}{}{.}
Zeige, dass dann auch
\mathdisp {\vdash \exists x \alpha \rightarrow \exists x \beta} { }
ableitbar ist.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass in der Prädikatenlogik
\mathdisp {\vdash \exists x \alpha \leftrightarrow \exists x \neg \neg \alpha} { }
\definitionsverweis {ableitbar}{}{}
ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es seien
\mathl{x,y,u,v}{} Variablen und
\mathl{\Gamma =\{ \forall x \forall y { \left( x = y \right) } \}}{} und
\mathl{\Delta = \{ x = y \}}{.}
\aufzaehlungdrei{Zeige
\zusatzklammer {ohne Bezug auf den Vollständigkeitssatz} {} {}
\mathl{\Gamma \vdash u= v}{.}
}{Charakterisiere die
\definitionsverweis {Modelle}{}{}
$M$ mit
\mathl{M \vDash \Gamma}{.}
}{Zeige
\mathl{\Delta \not\vdash u= v}{.}
}
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $G$ ein dreistelliges Relationssymbol und $L$ die zugehörige prädikatenlogische Sprache. Es sei $I$ die
\definitionsverweis {Interpretation}{}{,}
bei der die Grundmenge die euklidische Ebene ist und $G$ durch die dreistellige Relation interpretiert wird, bei der
\mathl{G(A,B,C)}{} zutrifft, wenn die Punkte
\mathl{A,B,C}{} auf einer Geraden liegen.
\aufzaehlungfuenf{Zeige
\mathl{I \vDash Gxyz \leftrightarrow Gyxz}{.}
}{Zeige, dass im Allgemeinen nicht
\mathl{I \vDash \forall x \forall y \forall z { \left( Gxyz \rightarrow Gxyu \right) }}{} gelten muss.
}{Es sei
\mathl{\Gamma=\{ \forall x \forall y \forall z { \left( Gxyz \leftrightarrow Gyxz \right) } , \, \forall x \forall y \forall z { \left( Gxyz \leftrightarrow Gxzy \right) } \}}{.} Erstelle eine Ableitung für
\mathl{\Gamma \vdash Gxyz \leftrightarrow Gyzx}{.}
}{Zeige, dass der Ausdruck
\mathl{Gxyz \wedge Gxyu}{} bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen
\mathl{x,y,z,u}{} belegenden Punkte auf einer Geraden liegen.
}{Formuliere einen Ausdruck aus $L$ in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.
}
}
{} {}
Die beiden folgenden Aufgaben sind vermutlich mühselig.
\inputaufgabe
{}
{
Man gebe einen \definitionsverweis {formalen Beweis}{}{} für die Aussage, dass die \definitionsverweis {Hintereinanderschaltung}{}{} von zwei \definitionsverweis {surjektiven Abbildungen}{}{} auf einer Menge wieder surjektiv ist.
}
{} {}
\inputaufgabe
{}
{
Man gebe einen \definitionsverweis {formalen Beweis}{}{} für die Aussage, dass die \definitionsverweis {Hintereinanderschaltung}{}{} von zwei \definitionsverweis {injektiven Abbildungen}{}{} auf einer Menge wieder injektiv ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $\Gamma$ eine Ausdrucksmenge aus einer
\definitionsverweis {Sprache erster Stufe}{}{}
und $\alpha$ ein weiterer Ausdruck. Es sei $\alpha$ nicht aus $\Gamma$
\definitionsverweis {ableitbar}{}{.}
Zeige, dass man aus
\mathl{\Gamma \cup \{\neg \alpha \}}{} keinen Widerspruch
\zusatzklammer {also keinen Ausdruck der Form
\mathl{\beta \wedge \neg \beta}{}} {} {}
ableiten kann.
}
{} {}
\inputaufgabe
{}
{
Begründe die folgenden Ableitungsregeln \zusatzklammer {es seien $s,t$ Terme, $\alpha, \beta$ Ausdrücke und $\Gamma$ eine Ausdrucksmenge} {} {.} \aufzaehlungdrei{Wenn $\Gamma \vdash s= t$, dann ist auch $\Gamma \vdash \alpha { \frac{ s }{ x } } \rightarrow \alpha { \frac{ t }{ x } }$, }{Wenn $\Gamma \vdash \alpha { \frac{ t }{ x } }$, dann ist auch $\Gamma \vdash \exists x \alpha$, }{Wenn $\Gamma \vdash \alpha \frac{y}{x} \rightarrow \beta$, dann ist auch $\Gamma \vdash \exists x \alpha \rightarrow \beta$, unter der Bedingung, dass $y$ nicht frei in $\Gamma, \exists x \alpha, \beta$ vorkommt. }
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{2}
{
Es sei
\mathl{\alpha \in L^S}{.} Zeige die
\definitionsverweis {Ableitbarkeit}{}{}
\mathdisp {\vdash \exists x \exists x \alpha \leftrightarrow \exists x \alpha} { . }
}
{} {}
\inputaufgabe
{4}
{
Es sei
\mathl{\alpha \in L^S}{.} Zeige die
\definitionsverweis {Ableitbarkeit}{}{}
\mathdisp {\vdash \exists x \forall y \alpha \rightarrow \forall y \exists x \alpha} { . }
Zeige, dass
\mathdisp {\forall y \exists x \alpha \rightarrow \exists x \forall y \alpha} { }
nicht ableitbar ist.
}
{} {}
\inputaufgabe
{4}
{
Formuliere mit dem zweistelligen Funktionssymbol $\cdot$ die Aussage, dass wenn eine Zahl $a$ die Zahl $b$ teilt und $b$ die Zahl $c$ teilt, dass dann $a$ auch $c$ teilt.
Erstelle eine \definitionsverweis {Ableitung}{}{} für diese Aussage.
}
{} {}
\inputaufgabe
{3}
{
Zeige, dass es eine
\definitionsverweis {Ausdrucksmenge}{}{}
$\Gamma$ mit der Eigenschaft gibt, dass für jede
\definitionsverweis {Interpretation}{}{}
$I$ genau dann
\mathl{I \vDash \Gamma}{} gilt, wenn die Grundmenge der Interpretation unendlich ist.
}
{} {}