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

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

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

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

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

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

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.

}
{} {}

\inputaufgabe
{3}
{

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

}
{} {}