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

Übungsaufgaben

Aufgabe

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

Aufgabe

Es seien ${}S\subseteq S'$ Symbolalphabete und seien ${}L^{S}\subseteq L^{S^{\prime }}$ die zugehörigen Sprachen Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge.

1. ${}\Gamma$ sei widerspruchsfrei. Ist dann auch ${}\Gamma$, aufgefasst in ${}L^{S^{\prime }}$, widerspruchsfrei?
2. ${}\Gamma$ sei maximal widerspruchsfrei. Ist dann auch ${}\Gamma$, aufgefasst in ${}L^{S^{\prime }}$, maximal widerspruchsfrei?

Aufgabe *

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache und ${}T$ die zugehörige Termmenge. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge.

1. Zeige, dass durch

   $s\cong _{\Gamma }t{\text{ genau dann, wenn }}I(s)=I(t){\text{ für jede Interpretation }}I{\text{ mit }}I\vDash \Gamma$

   eine Äquivalenzrelation auf ${}T$ definiert wird.

2. Wenn man ${}\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?

Aufgabe

Es sei ${}S$ ein Symbolalphabet, ${}T$ die zugehörige Termmenge und ${}L^{S}$ die zugehörige Sprache. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Zeige, dass die Äquivalenzrelation ${}\sim _{\Gamma }$ aus Konstruktion 14.7 die semantische Äquivalenz ${}\cong _{\Gamma }$ aus Aufgabe 14.3 impliziert.

Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Zeige, dass zu

${}\Gamma =\emptyset \,$

die in Konstruktion 14.7 eingeführte Äquivalenzrelation die Identität ist.

Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Die Ausdrucksmenge ${}\Gamma$ bestehe aus ${}x=y$, wobei ${}x,y$ verschiedene Variablen seien. Zeige, dass zwei Terme ${}s,t$ genau dann äquivalent im Sinne von Konstruktion 14.7 sind, wenn es eine Kette von Termen

$t_{0}=s,t_{1},t_{2},\ldots ,t_{k-1},t_{k}=t$

derart gibt, dass beim Übergang von ${}t_{i}$ nach ${}t_{i+1}$ genau ein Vorkommen von ${}x$ (bzw. ${}y$) in ${}t_{i}$ durch ${}y$ (bzw. ${}x$) ersetzt wird.

In der folgenden Aufgabe sollen die Variablen ${}x_{1},\ldots ,x_{n}$ verschieden sein. Dennoch gibt es zwei Interpretationen für Teil (2), die aber inhaltlich äquivalent sind.

Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Zu fixiertem ${}n\in \mathbb {N} _{+}$ sei ${}F_{n}$ die Menge der ${}n$-stelligen Funktionssymbole. Zeige die folgenden Aussagen.

1. Durch

   $f\cong g\,,{\text{ falls }}I(f)=I(g){\text{ für alle Interpretationen }}I{\text{ mit }}I\vDash \Gamma$

   wird eine Äquivalenzrelation auf ${}F_{n}$ definiert.

2. Durch

   $f\sim g\,,{\text{ falls }}\Gamma \vdash \forall x_{1}\forall x_{2}\ldots \forall x_{n}fx_{1}\ldots x_{n}=gx_{1}\ldots x_{n}$

   wird eine Äquivalenzrelation auf ${}F_{n}$ definiert.

3. Die Äquivalenzrelation ${}\sim$ impliziert die Äquivalenzrelation ${}\cong$.
4. Es sei ${}\sim$ die zu ${}\Gamma$ gehörende formale Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme ${}s_{1}\sim t_{1},\ldots ,s_{n}\sim t_{n}$ und Funktionssymbole ${}f,g\in F_{n}$ mit ${}f\sim g$ die Beziehung

   ${}fs_{1}\ldots s_{n}\sim gt_{1}\ldots t_{n}\,.$

Aufgabe

Es sei ${}\alpha \in L^{S}$ ein atomarer Ausdruck, der zugleich eine Tautologie ist, also ${}\vdash \alpha$. Zeige, dass ${}\alpha$ gleich ${}s=s$ mit einem ${}S$- Term ${}s$ ist.

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 ${}\Gamma$ eine Menge an ${}S$- Ausdrücken (über einem Symbolalphabet ${}S$), die folgende Eigenschaften erfüllt.

1. Für jeden Ausdruck ${}\alpha$ ist ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$.
2. Aus ${}\Gamma \vdash \alpha$ folgt ${}\alpha \in \Gamma$, d.h. ${}\Gamma$ ist abgeschlossen unter Ableitungen.
3. ${}\Gamma$ ist widerspruchsfrei.

Zeige, dass ${}\Gamma$ maximal widerspruchsfrei ist.

Aufgabe (4 Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Es seien ${}s,t$ verschiedene Terme. Zeige, dass es eine ${}S$- Interpretation ${}I$ mit

${}I(s)\neq I(t)\,$

gibt.

Aufgabe (8 (1+3+1+3) Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Zu fixiertem ${}n\in \mathbb {N} _{+}$ sei ${}R_{n}$ die Menge der ${}n$-stelligen Relationssymbole in ${}S$. Zeige die folgenden Aussagen.

1. Durch

   $P\cong Q\,,{\text{ falls }}I(P)=I(Q){\text{ für alle Interpretationen }}I{\text{ mit }}I\vDash \Gamma$

   wird eine Äquivalenzrelation auf ${}R_{n}$ definiert.

2. Durch

   $P\simeq Q\,,{\text{ falls }}\Gamma \vdash \forall x_{1}\forall x_{2}\ldots \forall x_{n}{\left(Px_{1}\ldots x_{n}\leftrightarrow Qx_{1}\ldots x_{n}\right)}$

   wird eine Äquivalenzrelation auf ${}R_{n}$ definiert.

3. Die Äquivalenzrelation ${}\simeq$ impliziert die Äquivalenzrelation ${}\cong$.
4. Es sei ${}\sim$ die zu ${}\Gamma$ gehörende Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme mit ${}s_{1}\sim t_{1},\ldots ,s_{n}\sim t_{n}$ und Relationsssymbole ${}P,Q\in R_{n}$ mit ${}P\simeq Q$ die Beziehung

   $\Gamma \vdash Ps_{1}\ldots s_{n}\leftrightarrow Qt_{1}\ldots t_{n}.$

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