Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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 } }} { . }
}
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ das Symbolalphabet eines angeordneten Körpers und sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha
}
{ =} { x \geq 0 \rightarrow \exists y (x = y \cdot y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Bestimme die
\definitionsverweis {Substitutionen}{}{}
\aufzaehlungzwei {
\mathdisp {\alpha { \frac{ x }{ y } }} { . }
} {
\mathdisp {\alpha { \frac{ y }{ 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
{}
{
Gehört in einem Ausdruck der Form
\mathl{{ \left( x=y \right) } { \frac{ t }{ x } }}{} die Symbolfolge
\mathl{{ \frac{ t }{ x } }}{} zur prädikatenlogischen Sprache? Gehört
\mathl{{ \left( x=y \right) } { \frac{ t }{ x } }}{} dazu?
}
{} {}
\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}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{?}
}
{} {}