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

Bestimme die kleinsten Symbolmengen, mit denen die folgenden Ausdrücke formulierbar sind.

1. $\mathrm{\exists }y(fx=y)$,
2. $\mathrm{\forall }x(fx=gyc)\wedge \mathrm{\exists }z\left(Rzxy\right)$,
3. $\mathrm{\forall }x\mathrm{\exists }ySxhuy$.

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 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 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 (5 Punkte)

Es seien $u,x,y,z$ Variablen und $f,g$ einstellige Funktionssymbole. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

a)

1. $\mathrm{\forall }x\mathrm{\forall }y((fx=fy\to x=y)\wedge (gx=gy\to x=y))$,
2. $\mathrm{\forall }x\mathrm{\forall }y(fx=fy\to x=y)\wedge \mathrm{\forall }x\mathrm{\forall }y(gx=gy\to x=y)$,
3. $\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }u\mathrm{\forall }z((fx=fy\to x=y)\wedge (gu=gz\to u=z))$.

b)

1. $\mathrm{\forall }x\mathrm{\exists }y(fy=x)\wedge \mathrm{\forall }x\mathrm{\exists }y(gy=x)$,
2. $\mathrm{\forall }x\mathrm{\exists }y(fy=x\wedge gy=x)$,
3. $\mathrm{\forall }x\mathrm{\exists }y\mathrm{\forall }u\mathrm{\exists }z(fy=x\wedge gz=u)$,
4. $\mathrm{\forall }x\mathrm{\forall }u\mathrm{\exists }y\mathrm{\exists }z(fy=x\wedge gz=u)$.

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 (3 Punkte)

Es sei $f$ ein einstelliges Funktionssymbol. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

1. $\mathrm{\forall }x\mathrm{\exists }y(fx=y)$,
2. $\mathrm{\forall }x\mathrm{\exists }x(fx=x)$,
3. $\mathrm{\exists }x(fx=x)$.

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.

Fußnoten