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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)}$.