Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/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 seien $x,y,z$ Variablen \zusatzklammer {mit der angegebenen Reihenfolge} {} {,} $c$ eine Konstante und $f$ ein einstelliges Funktionssymbol. \aufzaehlungdrei{Bestimme
\mathdisp {(\exists x (x=c)) { \frac{ z }{ x } }} { . }
}{Bestimme
\mathdisp {( \exists x (x=c)) { \frac{ x }{ x } }} { . }
}{Bestimme
\mathdisp {( \exists x (x=c) ) { \frac{ fx }{ x } }} { . }
}

}
{} {}

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien $x_1,x_2$ Variablen, $t_1,t_2$ Terme und $\alpha$ ein Ausdruck in einer \definitionsverweis {prädikatenlogischen Sprache}{}{.} Zeige, dass
\mathdisp {\alpha { \frac{ t_1,t_2 }{ x_1,x_2 } } \rightarrow { \left( \alpha { \frac{ t_1 }{ x_1 } } \right) } { \frac{ t_2 }{ x_2 } }} { }
im Allgemeinen nicht allgemeingültig ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien $x_1,x_2$ Variablen, $t_1,t_2$ Terme und $\alpha$ ein Ausdruck in einer \definitionsverweis {prädikatenlogischen Sprache}{}{.} Zeige, dass
\mathdisp {{ \left( \alpha { \frac{ t_1 }{ x_1 } } \right) } { \frac{ t_2 }{ x_2 } } \rightarrow \alpha { \frac{ t_1,t_2 }{ x_1,x_2 } }} { }
im Allgemeinen nicht allgemeingültig ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es seien $x,y$ Variablen,
\mathl{s,t}{} Terme und $\alpha$ ein Ausdruck in einer \definitionsverweis {prädikatenlogischen Sprache}{}{.} Es seien $u,v$ neue Variablen, die weder in $s$ noch in $t$ noch in $\alpha$ vorkommen. Zeige, dass
\mathdisp {\alpha { \frac{ s,t }{ x,y } } \leftrightarrow \alpha { \frac{ s { \frac{ v }{ y } } }{ x } } { \frac{ t { \frac{ u }{ x } } }{ y } } { \frac{ x }{ u } } { \frac{ y }{ v } }} { }
\definitionsverweis {allgemeingültig}{}{} ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen \zusatzklammer {von links nach rechts} {} {} zu lesen ist.

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei ein \definitionsverweis {Symbolalphabet}{}{} $S$ einer \definitionsverweis {Sprache erster Stufe}{}{} gegeben, $\alpha \in L^S$ und $I$ eine \definitionsverweis {Interpretation}{}{} mit
\mathl{I \vDash \alpha}{.} Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit
\mathl{I \vDash \alpha { \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } }}{} unter einer \definitionsverweis {Substitution}{}{} folgt.

}
{} {}

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

Es seien $c,d$ Konstanten einer \definitionsverweis {erststufigen Sprache}{}{,}
\mathl{x,y,z,u,v,w}{} Variablen \zusatzklammer {in dieser Reihenfolge} {} {,} $f$ ein einstelliges Funktionssymbol,
\mathl{g}{} ein zweistelliges Funktionssymbol und $P,R$ einstellige Relationssymbole. Bestimme die \definitionsverweis {Substitution}{}{}
\mathdisp {{ \left( \forall y ( y = c ) \vee ( \neg R fz \rightarrow \exists x \neg P u \right) } { \frac{ gzz, \, \, \, \, \,c,\, \, \, \, \, fu }{ x,\, \, \, \, \, \, \, \, \, y, \, \, \, \, \, \, \,\, \, z } }} { . }

}
{} {}

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

}
{} {}