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

\setcounter{section}{14}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Zeige durch ein Beispiel, dass Lemma 14.5 ohne die Voraussetzung, dass eine surjektive Terminterpretation vorliegt, nicht gelten muss.

}
{} {}

\inputaufgabe
{}
{

Bestimme den \definitionsverweis {Rang}{}{} der folgenden Ausdrücke. \aufzaehlungvier{ $a = fx$, }{ $\exists x a = fx$, }{${ \left( \neg Rxy \wedge ffx = c \right) } \rightarrow { \left( \exists x a = fx \right) }$, }{ ${ \left( \forall y Rxy \right) } \rightarrow { \left( \exists x a = fx \right) }$. }

}
{} {}

\inputaufgabe
{}
{

Zeige durch Induktion über den Aufbau der Ausdrücke, dass sich bei einer \definitionsverweis {Termsubstitution}{}{} der \definitionsverweis {Rang}{}{} eines Ausdrucks nicht ändert.

}
{} {}

\inputaufgabe
{}
{

Warum führt man im Beweis zum Satz von Henkin nicht Induktion über den Aufbau der Ausdrücke?

}
{} {}

\inputaufgabe
{}
{

Das Symbolalphabet $S$ bestehe aus einer einzigen Variablen $x$ und einem einzigen einstelligen Relationssymbol $P$. Zeige, dass zu einer \definitionsverweis {Interpretation}{}{} $I$ die Gültigkeitsmenge
\mathl{I^\vDash \subseteq L^S}{} keine \definitionsverweis {Beispiele enthalten}{}{} muss.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien $x,z$ verschiedene Variablen,
\mathl{t}{} ein $S$-\definitionsverweis {Term}{}{} und $\alpha$ ein $S$-\definitionsverweis {Ausdruck}{}{,} wobei $z$ weder in $t$ noch in $\alpha$ vorkomme. Gilt dann die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ { \left( \alpha \frac{z}{x} \right) } \frac{t}{z} }
{ =} { \alpha \frac{t}{x} }
{ } { }
{ } { }
{ } { }
} {}{}{?}

}
{} {}

\inputaufgabe
{}
{

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

Bestimme den \definitionsverweis {Rang}{}{} der folgenden Ausdrücke. \aufzaehlungvier{ $gxy = c$, }{ $\forall x gcx = gxx$, }{${ \left( \neg Pz \vee ggxyy = gcc \right) } \rightarrow { \left( \exists x Px \right) }$, }{ ${ \left( \forall y Py \right) } \rightarrow { \left( \neg \exists x gcx = gcgcx \wedge c = c \right) }$. }

}
{} {}