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. $\mathrm{\forall }x(fx=y)$,
2. $\mathrm{\forall }x(fx=y)\wedge \mathrm{\exists }z(fx=y)$,
3. $\mathrm{\forall }x\mathrm{\exists }yRxfy$,
4. $\left(\mathrm{\forall }x\mathrm{\exists }yRxfy\right)\to 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\models \alpha$ genau dann, wenn $I_2\models \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,\dots ,x_k$ paarweise verschiedene Variablen und $t_1,\dots ,t_k$ fixierte $S$-Terme.

a) Interpretiere die Termsubstitution $\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}$ als Abbildung.

b) Interpretiere die Substitution von Ausdrücken $\frac{t_1,\dots ,t_k}{x_1,\dots ,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

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

2. Bestimme

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

3. Bestimme

   $(\mathrm{\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

$(\mathrm{\forall }yRxy\wedge \mathrm{\neg }Ryfz)\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,\dots ,t_k}{x_1,\dots ,x_k}$ und einen $S$-Ausdruck $\alpha$ derart, dass die sukzessive substituierten Ausdrücke

$\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k},\left(\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k},\left(\left(\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k},\dots$

immer länger werden.

Aufgabe *

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Es seien $x_1,\dots ,x_k$ paarweise verschiedene Variablen und $t_1,\dots ,t_k$ fixierte $S$-Terme. Zeige, dass für jeden $S$-Satz $\alpha \in L_0^S$ die Gleichheit

$\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,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}\to \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}\to \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\models \alpha$. Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit $I\models \alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}$ unter einer Substitution folgt.

Aufgabe

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Es seien $x_1,\dots ,x_k$ paarweise verschiedene Variablen und $t_1,\dots ,t_k$ fixierte $S$-Terme. Zeige, dass zu einem allgemeingültigen Ausdruck $\alpha$ auch die Substitution $\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,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

${\mathrm{Frei}}_{}^{}\left(\beta \right)={\mathrm{Var}}_{}^{}\left(\alpha \right)={\mathrm{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

$(\mathrm{\forall }y(y=c)\vee (\mathrm{\neg }Rfz\to \mathrm{\exists }x\mathrm{\neg }Pu)\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,\dots ,t_k}{x_1,\dots ,x_k}$ und einen $S$-Ausdruck $\alpha$ derart, dass die sukzessive substituierten Ausdrücke

$\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k},\left(\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k},\left(\left(\alpha \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{t_1,\dots ,t_k}{x_1,\dots ,x_k},\dots$

eine Periode der Länge $r$ besitzen.

Aufgabe (3 Punkte)

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Es seien $x_1,\dots ,x_k,y_1,\dots ,y_{\ell }$ paarweise verschiedene Variablen und $t_1,\dots ,t_k,s_1,\dots ,s_{\ell }$ fixierte $S$-Terme. Zeige, dass für Terme $\tau$, in denen $y_1,\dots ,y_{\ell }$ nicht vorkommen, die Gleichheit

$\left(\tau \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }}=\tau \frac{t_1\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }},\dots ,t_k\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }}}{x_1,\dots ,x_k}$

gilt.

Aufgabe (2 Punkte)

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Es seien $x_1,\dots ,x_k,y_1,\dots ,y_{\ell }$ paarweise verschiedene Variablen und $t_1,\dots ,t_k,s_1,\dots ,s_{\ell }$ fixierte $S$-Terme. Zeige durch ein Beispiel, dass für Terme $\tau$ die Gleichheit

$\left(\tau \frac{t_1,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }}=\tau \frac{t_1\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }},\dots ,t_k\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }}}{x_1,\dots ,x_k}$

nicht gelten muss.

Aufgabe (4 Punkte)

Es sei ein Symbolalphabet $S$ einer Sprache erster Stufe gegeben. Es seien $x_1,\dots ,x_k,y_1,\dots ,y_{\ell }$ paarweise verschiedene Variablen und $t_1,\dots ,t_k,s_1,\dots ,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,\dots ,t_k}{x_1,\dots ,x_k}\right)\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }}=\alpha \frac{t_1\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }},\dots ,t_k\frac{s_1,\dots ,s_{\ell }}{y_1,\dots ,y_{\ell }}}{x_1,\dots ,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}?$