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

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

1. ${}\exists y{\left(fx=y\right)}$,
2. ${}\forall x{\left(fx=gyc\right)}\wedge \exists z{\left(Rzxy\right)}$,
3. ${}\forall x\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}\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 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 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 (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. ${}\forall x\forall y((fx=fy\rightarrow x=y)\wedge (gx=gy\rightarrow x=y))$,
2. ${}\forall x\forall y(fx=fy\rightarrow x=y)\wedge \forall x\forall y(gx=gy\rightarrow x=y)$,
3. ${}\forall x\forall y\forall u\forall z((fx=fy\rightarrow x=y)\wedge (gu=gz\rightarrow u=z))$.

b)

1. ${}\forall x\exists y(fy=x)\wedge \forall x\exists y(gy=x)$,
2. ${}\forall x\exists y{\left(fy=x\wedge gy=x\right)}$,
3. ${}\forall x\exists y\forall u\exists z(fy=x\wedge gz=u)$,
4. ${}\forall x\forall u\exists y\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

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

gilt.

Aufgabe (3 Punkte)

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

1. ${}\forall x\exists y(fx=y)$,
2. ${}\forall x\exists x(fx=x)$,
3. ${}\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},\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.

Fußnoten