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

\setcounter{section}{11}

\zwischenueberschrift{Übungsaufgaben}

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

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

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.

}
{} {}

\inputaufgabe
{}
{

Zeige
\mathdisp {\vDash \exists x (x=y)} { . }

}
{} {}

\inputaufgabe
{}
{

Zeige
\mathdisp {\vdash \exists x (x=y)} { . }

}
{} {}

\inputaufgabegibtloesung
{}
{

Zeige, dass mit
\mathdisp {\vdash \alpha \rightarrow \beta} { }
auch
\mathdisp {\vdash \forall x \alpha \rightarrow \forall x \beta} { }
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.

}
{} {}

\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
{5 (2+2+1)}
{

Es seien
\mavergleichskette
{\vergleichskette
{ \alpha, \beta }
{ \in }{ L^S }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

a) Zeige, dass
\mathdisp {{ \left( \exists x { \left( \alpha \rightarrow \beta \right) } \right) } \rightarrow { \left( \exists x \alpha \rightarrow \exists x \beta \right) }} { }
nicht \definitionsverweis {allgemeingültig}{}{} ist.

b) Zeige, dass
\mathdisp {{ \left( \exists x \alpha \rightarrow \exists x \beta \right) } \rightarrow { \left( \exists x { \left( \alpha \rightarrow \beta \right) } \right) }} { }
allgemeingültig ist.

c) Zeige, dass
\mathdisp {{ \left( \exists x \alpha \rightarrow \exists x \beta \right) } \rightarrow { \left( \exists x { \left( \alpha \rightarrow \beta \right) } \right) }} { }
nicht allgemeingültig wäre, wenn man auch leere Grundmengen zulassen würde.

}
{} {}

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

}
{} {}