Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 14

Übungsaufgaben

Aufgabe

Zeige durch ein Beispiel, dass Lemma 14.5 ohne die Voraussetzung, dass eine surjektive Terminterpretation vorliegt, nicht gelten muss.

Aufgabe

Bestimme den Rang der folgenden Ausdrücke.

1. ${}a=fx$,
2. ${}\exists xa=fx$,
3. ${}{\left(\neg Rxy\wedge ffx=c\right)}\rightarrow {\left(\exists xa=fx\right)}$,
4. ${}{\left(\forall yRxy\right)}\rightarrow {\left(\exists xa=fx\right)}$.

Aufgabe

Zeige durch Induktion über den Aufbau der Ausdrücke, dass sich bei einer Termsubstitution der Rang eines Ausdrucks nicht ändert.

Aufgabe

Warum führt man im Beweis zum Satz von Henkin nicht Induktion über den Aufbau der Ausdrücke?

Aufgabe

Das Symbolalphabet ${}S$ bestehe aus einer einzigen Variablen ${}x$ und einem einzigen einstelligen Relationssymbol ${}P$. Zeige, dass zu einer Interpretation ${}I$ die Gültigkeitsmenge ${}I^{\vDash }\subseteq L^{S}$ keine Beispiele enthalten muss.

Aufgaben zum Abgeben

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

Aufgabe (5 (2+2+1) Punkte)

Es seien ${}\alpha ,\beta \in L^{S}$.

a) Zeige, dass

${\left(\exists x{\left(\alpha \rightarrow \beta \right)}\right)}\rightarrow {\left(\exists x\alpha \rightarrow \exists x\beta \right)}$

nicht allgemeingültig ist.

b) Zeige, dass

${\left(\exists x\alpha \rightarrow \exists x\beta \right)}\rightarrow {\left(\exists x{\left(\alpha \rightarrow \beta \right)}\right)}$

allgemeingültig ist.

c) Zeige, dass

${\left(\exists x\alpha \rightarrow \exists x\beta \right)}\rightarrow {\left(\exists x{\left(\alpha \rightarrow \beta \right)}\right)}$

nicht allgemeingültig wäre, wenn man auch leere Grundmengen zulassen würde.

Aufgabe (2 Punkte)

Bestimme den Rang der folgenden Ausdrücke.

1. ${}gxy=c$,
2. ${}\forall xgcx=gxx$,
3. ${}{\left(\neg Pz\vee ggxyy=gcc\right)}\rightarrow {\left(\exists xPx\right)}$,
4. ${}{\left(\forall yPy\right)}\rightarrow {\left(\neg \exists xgcx=gcgcx\wedge c=c\right)}$.