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

\setcounter{section}{9}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Bestimme die freien Variablen in den folgenden Ausdrücken, wobei
\mathl{x,y,z}{} Variablen seien und $f$ ein einstelliges Funktionssymbol und $R$ ein zweistelliges Relationssymbol sei. \aufzaehlungvier{ $\forall x { \left( fx = y \right) }$, }{ $\forall x { \left( fx = y \right) } \wedge \exists z { \left( fx = y \right) }$, }{ $\forall x\exists y Rxfy$, }{ ${ \left( \forall x \exists y Rxfy \right) } \rightarrow x = y$. }

}
{} {}

\inputaufgabe
{}
{

Bestimme die kleinsten Symbolmengen, mit denen die folgenden Ausdrücke formulierbar sind. \aufzaehlungdrei{ $\exists y { \left( fx = y \right) }$, }{ $\forall x { \left( fx = g yc \right) } \wedge \exists z { \left( R z x y \right) }$, }{ $\forall x \exists y S x huy$. }

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\alpha \in L^S_0}{} ein Satz einer \definitionsverweis {erststufigen Sprache}{}{} über einem Symbolalphabet $S$. Es sei eine $S$-\definitionsverweis {Struktur}{}{} mit Trägermenge $M$ gegeben und \mathkor {} {I_1} {und} {I_2} {} zwei auf $M$ definierte $S$-\definitionsverweis {Interpretationen}{}{.} Zeige
\mathl{I_1 \vDash \alpha}{} genau dann, wenn
\mathl{I_2 \vDash \alpha}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Es seien
\mathl{c,d}{} Konstanten einer \definitionsverweis {erststufigen Sprache}{}{,}
\mathl{x,y,z,v}{} Variablen, $f$ ein einstelliges und
\mathl{g,h}{} zweistellige Funktionssymbole. Bestimme die \definitionsverweis {Substitution}{}{}

\mathdisp {ghhxcdfz  { \frac{  fx, \, \, \, \, \,gxz,\, \,  \, \, \, hvfx }{ x,\, \, \,  \, \, \, \, \, \,\, \, \, y, \, \, \, \, \, \, \, \, \, \,\, \, z } }} { . }

}
{} {}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte $S$-\definitionsverweis {Terme}{}{.}

a) Interpretiere die \definitionsverweis {Termsubstitution}{}{}
\mathl{{ \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} als Abbildung.

b) Interpretiere die \definitionsverweis {Substitution von Ausdrücken}{}{}
\mathl{{ \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} als Abbildung.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. \aufzaehlungzwei {Zeige, dass die \definitionsverweis {Substitution}{}{}
\mathl{{ \frac{ x }{ x } }}{} für die Terme die Identität ist. } {Zeige, dass die \definitionsverweis {Substitution}{}{}
\mathl{{ \frac{ x }{ x } }}{} für die Ausdrücke die Identität ist. }

}
{} {}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben, es sei $x$ eine Variable und
\mathl{t}{} ein fixierter $S$-\definitionsverweis {Term}{}{.} Gehört die Symbolkette \zusatzklammer {!} {} {}
\mathl{\alpha { \frac{ t }{ x } }}{} zu $L^S$?

}
{} {}

\inputaufgabe
{}
{

Es sei $c$ eine Konstante einer \definitionsverweis {erststufigen Sprache}{}{,}
\mathl{x,y,z,u}{} Variablen, $f$ ein einstelliges Funktionssymbol,
\mathl{g,h}{} zweistellige Funktionssymbole und $R$ ein zweistelliges Relationssymbol. Bestimme die \definitionsverweis {Substitution}{}{}
\mathdisp {{ \left( \forall y Rxy \wedge \neg R y fz \right) } { \frac{ fx, \, \, \, \, \,gxz,\, \, \, \, \, hcfx }{ x,\, \, \, \, \, \, \, \, \,\, \, \, y, \, \, \, \, \, \, \, \, \, \,\, \, z } }} { . }

}
{} {}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Man gebe ein Beispiel für eine Substitution
\mathl{{ \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} und einen $S$-Ausdruck
\mathl{\alpha}{} derart, dass die sukzessive substituierten Ausdrücke
\mathdisp {\alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }, { \left( \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }, { \left( { \left( \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }, \ldots} { }
immer länger werden.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte $S$-\definitionsverweis {Terme}{}{.} Zeige, dass für jeden $S$-Satz
\mathl{\alpha \in L^S_0}{} die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } }
{ =} { \alpha }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{\alpha \in L^ S}{.} Zeige, dass die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ { \left( \alpha { \frac{ y }{ x } } \right) } { \frac{ z }{ y } } }
{ =} { \alpha { \frac{ y, z }{ x, y } } }
{ } { }
{ } { }
{ } { }
} {}{}{} im Allgemeinen nicht gilt.

}
{} {}

\inputaufgabe
{}
{

Es sei ein \definitionsverweis {Symbolalphabet}{}{} $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien
\mathl{x_1 , \ldots , x_k}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k}{} fixierte $S$-\definitionsverweis {Terme}{}{.} Zeige, dass zu einem \definitionsverweis {allgemeingültigen}{}{} Ausdruck $\alpha$ auch die Substitution
\mathl{\alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} allgemeingültig ist. Gilt hiervon auch die Umkehrung?

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

Es seien $u, x,y,z$ Variablen und
\mathl{f,g}{} einstellige Funktionssymbole. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

a) \aufzaehlungdrei{ $\forall x \forall y ( ( fx =fy \rightarrow x=y ) \wedge (gx =gy \rightarrow x=y))$, }{ $\forall x \forall y ( fx =fy \rightarrow x=y ) \wedge \forall x \forall y ( gx =gy \rightarrow x=y )$, }{ $\forall x \forall y \forall u \forall z ( ( fx =fy \rightarrow x=y ) \wedge (gu =gz \rightarrow u=z ))$. }

b) \aufzaehlungvier{ $\forall x \exists y (fy=x) \wedge\forall x \exists y (gy=x)$, }{ $\forall x \exists y { \left( fy = x \wedge gy = x \right) }$, }{ $\forall x \exists y \forall u \exists z ( fy =x \wedge gz = u )$, }{ $\forall x \forall u \exists y \exists z ( fy =x \wedge gz =u )$. }

}
{} {}

\inputaufgabe
{}
{

Es sei $\alpha$ ein $S$-Ausdruck. Zeige, dass es einen $S$-Ausdruck $\beta$ der Form $\beta= \alpha \wedge \gamma$ derart gibt, dass
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ Frei}_{ } ^{ } { \left( \beta \right) } }
{ =} {\operatorname{ Var}_{ } ^{ } { \left( \alpha \right) } }
{ =} {\operatorname{ Var}_{ } ^{ } { \left( \beta \right) } }
{ } { }
{ } { }
} {}{}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Es sei $f$ ein einstelliges Funktionssymbol. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent\zusatzfussnote {Zwei Ausdrücke \mathkor {} {\alpha} {und} {\beta} {} heißen äquivalent, wenn
\mathl{\alpha \leftrightarrow \beta}{} \definitionsverweis {allgemeingültig}{}{} ist} {.} {} sind. \aufzaehlungdrei{ $\forall x \exists y (fx=y)$, }{ $\forall x \exists x (fx=x)$, }{ $\exists x (fx=x)$. }

}
{} {}

\inputaufgabe
{}
{

Man gebe für jedes
\mathl{r \in \N_+}{} ein Beispiel für eine Substitution
\mathl{{ \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} und einen $S$-Ausdruck
\mathl{\alpha}{} derart, dass die sukzessive substituierten Ausdrücke
\mathdisp {\alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }, { \left( \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }, { \left( { \left( \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }, \ldots} { }
eine Periode der Länge $r$ besitzen.

}
{} {}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien
\mathl{x_1 , \ldots , x_k,y_1 , \ldots , y_\ell}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k,s_1, \ldots , s_\ell}{} fixierte $S$-\definitionsverweis {Terme}{}{.} Zeige, dass für Terme $\tau$, in denen
\mathl{y_1 , \ldots , y_\ell}{} nicht vorkommen, die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ { \left( \tau { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } }
{ =} {\tau { \frac{ t_1 { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } , \ldots , t_k { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } }{ x_1 , \ldots , x_k } } }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}
{} {}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien
\mathl{x_1 , \ldots , x_k,y_1 , \ldots , y_\ell}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k,s_1, \ldots , s_\ell}{} fixierte $S$-\definitionsverweis {Terme}{}{.} Zeige durch ein Beispiel, dass für Terme $\tau$ die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ { \left( \tau { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } }
{ =} {\tau { \frac{ t_1 { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } , \ldots , t_k { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } }{ x_1 , \ldots , x_k } } }
{ } { }
{ } { }
{ } { }
} {}{}{} nicht gelten muss.

}
{} {}

\inputaufgabe
{}
{

Es sei ein Symbolalphabet $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben. Es seien
\mathl{x_1 , \ldots , x_k,y_1 , \ldots , y_\ell}{} paarweise verschiedene Variablen und
\mathl{t_1 , \ldots , t_k,s_1, \ldots , s_\ell}{} fixierte $S$-\definitionsverweis {Terme}{}{.} Zeige durch ein Beispiel, dass für Ausdrücke $\alpha$ die Gleichheit \zusatzklammer {von Ausdrücken} {} {}
\mavergleichskettedisp
{\vergleichskette
{ { \left( \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } } \right) } { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } }
{ =} { \alpha { \frac{ t_1 { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } , \ldots , t_k { \frac{ s_1 , \ldots , s_\ell }{ y_1 , \ldots , y_\ell } } }{ x_1 , \ldots , x_k } } }
{ } { }
{ } { }
{ } { }
} {}{}{} nicht gelten muss.

}
{} {}