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

Übungsaufgaben

Aufgabe

Bestimme die freien Variablen in den folgenden Ausdrücken, wobei ${}x,y,z$ Variablen seien und ${}f$ ein einstelliges Funktionssymbol und ${}R$ ein zweistelliges Relationssymbol sei.

1. ${}\forall x{\left(fx=y\right)}$,
2. ${}\forall x{\left(fx=y\right)}\wedge \exists z{\left(fx=y\right)}$,
3. ${}\forall x\exists yRxfy$,
4. ${}{\left(\forall x\exists yRxfy\right)}\rightarrow x=y$.

Aufgabe

Es sei ${}\alpha \in L_{0}^{S}$ ein Satz einer erststufigen Sprache über einem Symbolalphabet ${}S$. Es sei eine ${}S$-Struktur mit Trägermenge ${}M$ gegeben und ${}I_{1}$ und ${}I_{2}$ zwei auf ${}M$ definierte ${}S$-Interpretationen. Zeige ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ gilt.

Aufgabe

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

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

Aufgabe

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$-Terme.

a) Interpretiere die Termsubstitution ${}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ als Abbildung.

b) Interpretiere die Substitution von Ausdrücken ${}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ als Abbildung.

Aufgabe *

Es seien ${}x,y,z$ Variablen (mit der angegebenen Reihenfolge), ${}c$ eine Konstante und ${}f$ ein einstelliges Funktionssymbol.

1. Bestimme

   $(\exists x(x=c)){\frac {z}{x}}.$

2. Bestimme

   $(\exists x(x=c)){\frac {x}{x}}.$

3. Bestimme

   $(\exists x(x=c)){\frac {fx}{x}}.$

Aufgabe *

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben.

1. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Terme die Identität ist.
2. Zeige, dass die Substitution ${}{\frac {x}{x}}$ für die Ausdrücke die Identität ist.

Aufgabe

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

Aufgabe

Es sei ${}c$ eine Konstante einer erststufigen Sprache, ${}x,y,z,u$ Variablen, ${}f$ ein einstelliges Funktionssymbol, ${}g,h$ zweistellige Funktionssymbole und ${}R$ ein zweistelliges Relationssymbol. Bestimme die Substitution

${\left(\forall yRxy\wedge \neg Ryfz\right)}{\frac {fx,\,\,\,\,\,gxz,\,\,\,\,\,hcfx}{x,\,\,\,\,\,\,\,\,\,\,\,\,y,\,\,\,\,\,\,\,\,\,\,\,\,z}}.$

Aufgabe

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Man gebe ein Beispiel für eine Substitution ${}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ und einen ${}S$-Ausdruck ${}\alpha$ derart, dass die sukzessive substituierten Ausdrücke

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

Aufgabe *

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$-Terme. Zeige, dass für jeden ${}S$-Satz ${}\alpha \in L_{0}^{S}$ die Gleichheit

${}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=\alpha \,$

gilt.

Aufgabe

Es sei ${}\alpha \in L^{S}$. Zeige, dass die Gleichheit

${}{\left(\alpha {\frac {y}{x}}\right)}{\frac {z}{y}}=\alpha {\frac {y,z}{x,y}}\,$

im Allgemeinen nicht gilt.

Aufgabe *

Es seien ${}x_{1},x_{2}$ Variablen, ${}t_{1},t_{2}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Zeige, dass

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

Aufgabe *

Es seien ${}x_{1},x_{2}$ Variablen, ${}t_{1},t_{2}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Zeige, dass

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

Aufgabe *

Es seien ${}x,y$ Variablen, ${}s,t$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Es seien ${}u,v$ neue Variablen, die weder in ${}s$ noch in ${}t$ noch in ${}\alpha$ vorkommen. Zeige, dass

$\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}}$

allgemeingültig ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen (von links nach rechts) zu lesen ist.

Aufgabe *

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

Aufgabe

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

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es sei ${}\alpha$ ein ${}S$-Ausdruck. Zeige, dass es einen ${}S$-Ausdruck ${}\beta$ der Form ${}\beta =\alpha \wedge \gamma$ derart gibt, dass

${}\operatorname {Frei} _{}^{}{\left(\beta \right)}=\operatorname {Var} _{}^{}{\left(\alpha \right)}=\operatorname {Var} _{}^{}{\left(\beta \right)}\,$

gilt.

Aufgabe (2 Punkte)

Es seien ${}c,d$ Konstanten einer erststufigen Sprache, ${}x,y,z,u,v,w$ Variablen (in dieser Reihenfolge), ${}f$ ein einstelliges Funktionssymbol, ${}g$ ein zweistelliges Funktionssymbol und ${}P,R$ einstellige Relationssymbole. Bestimme die Substitution

${\left(\forall y(y=c)\vee (\neg Rfz\rightarrow \exists x\neg Pu\right)}{\frac {gzz,\,\,\,\,\,c,\,\,\,\,\,fu}{x,\,\,\,\,\,\,\,\,\,y,\,\,\,\,\,\,\,\,\,z}}.$

Aufgabe (3 Punkte)

Man gebe für jedes ${}r\in \mathbb {N} _{+}$ ein Beispiel für eine Substitution ${}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ und einen ${}S$-Ausdruck ${}\alpha$ derart, dass die sukzessive substituierten Ausdrücke

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

Aufgabe (3 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k},y_{1},\ldots ,y_{\ell }$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k},s_{1},\ldots ,s_{\ell }$ fixierte ${}S$-Terme. Zeige, dass für Terme ${}\tau$, in denen ${}y_{1},\ldots ,y_{\ell }$ nicht vorkommen, die Gleichheit

${}{\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.

Aufgabe (2 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k},y_{1},\ldots ,y_{\ell }$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k},s_{1},\ldots ,s_{\ell }$ fixierte ${}S$-Terme. Zeige durch ein Beispiel, dass für Terme ${}\tau$ die Gleichheit

${}{\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.

Aufgabe (4 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k},y_{1},\ldots ,y_{\ell }$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k},s_{1},\ldots ,s_{\ell }$ fixierte ${}S$-Terme. Zeige durch ein Beispiel, dass für Ausdrücke ${}\alpha$ die Gleichheit (von Ausdrücken)

${}{\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.

Aufgabe (3 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x,z$ verschiedene Variablen, ${}t$ ein ${}S$-Term und ${}\alpha$ ein ${}S$-Ausdruck, wobei ${}z$ weder in ${}t$ noch in ${}\alpha$ vorkomme. Gilt dann die Gleichheit

${}{\left(\alpha {\frac {z}{x}}\right)}{\frac {t}{z}}=\alpha {\frac {t}{x}}\,?$