Kurs:Einführung in die mathematische Logik/17/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	2	2	2	2	5	2	3	7	2	8	4	5	3	3	2	2	4	64

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge ${}\Gamma \subseteq L^{S}$.
2. Ein topologischer Filter auf einem topologischen Raum ${}X$.
3. Die Interpretation der Terme zu einem Symbolalphabet ${}S$ in einer gegebenen ${}S$- Interpretation auf einer Grundmenge ${}M$.
4. Eine funktional abgeschlossene Teilmenge ${}T\subseteq M$ einer ${}S$- Struktur ${}M$, wobei ${}S$ ein erststufiges Symbolalphabet bezeichnet.
5. Eine vollständige Theorie ${}T\subseteq L_{0}^{S}$.
6. Ein modallogisches Modell.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Henkin.
2. Der Satz über das Halteproblem.
3. Die Unentscheidbarkeit der Arithmetik.

Aufgabe * (2 Punkte)

${}E$ wurde ermordet. Es gelten folgende Sachverhalte.

1. Der Mörder ist ${}A$ oder ${}B$ oder ${}C$ oder ${}D$.
2. Wenn ${}C$ der Mörder ist, dann ist ${}D$ nicht der Mörder oder ${}A$ ist der Mörder.
3. ${}A,B,C,D$ sind alle verschieden.
4. Es gibt genau einen Mörder.
5. Wenn ${}A$ nicht der Mörder ist, dann ist ${}D$ nicht der Mörder.
6. ${}A$ ist genau dann der Mörder, wenn ${}B$ der Mörder ist.

Wer ist der Mörder?

Aufgabe * (2 Punkte)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}r$ ${}?$ w w w w w w f f w f w w w f f f f w w f f w f w f f w f f f f w

Aufgabe (2 Punkte)

Erläutere die Beziehung zwischen dem Modus ponens und

$\vdash \alpha \wedge {\left(\alpha \rightarrow \beta \right)}\rightarrow \beta .$

Aufgabe * (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die Widerspruchsregel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$, dann ist auch ${}\Gamma \vdash \beta$.

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

Es sei ${}N$ ein einstelliges Funktionssymbol, ${}F$ und ${}G$ seien zweistellige Funktionssymbole und ${}x,y$ seien Variablen.

Wir betrachten die folgenden Modelle (wobei ${}M$ die Grundmenge bezeichnet).

a) ${}M=\mathbb {R}$, ${}N$ ist die Quadrierung, ${}F$ die Addition und ${}G$ die Multiplikation.

b) ${}M=C^{\infty }(\mathbb {R} ,\mathbb {R} )={\left\{f:\mathbb {R} \rightarrow \mathbb {R} \mid f{\text{ unendlich oft differenzierbar}}\right\}}$, ${}N$ ist das Differenzieren von Funktionen, ${}F$ die Multiplikation und ${}G$ die Addition von Funktionen. Bestimme, ob in diesen Modellen die folgenden Aussagen wahr werden.

1. $\forall x\forall y{\left(NFxy=GFxNyFNxy\right)}.$

2. $\forall y\exists x{\left(NFxy=GFxNyFNxy\right)}.$

3. $\exists y\forall x{\left(NFxy=GFxNyFNxy\right)}.$

Aufgabe * (2 Punkte)

Es sei ein Symbolalphabet ${}S$ erster Stufe mit der Variablenmenge

${}V=\{x,y,z,w\}\,$

gegeben und eine ${}S$- Interpretation ${}I$ in der Menge ${}\mathbb {R}$ mit

$I(x)=5,\,I(y)=\pi ,\,I(z)=-{\sqrt {2}},\,I(w)=-3.$

Bestimme die Werte von ${}x,y,z,w$ bei der Interpretation ${}J:=I{\frac {e,-{\sqrt {2}},{\frac {4}{7}},I(x)}{x,z,x,y}}$ auf ${}V$.

Aufgabe * (3 Punkte)

Es seien ${}x,y,z$ Variablen (mit der angegebenen Reihenfolge), ${}c$ eine Konstante und ${}f$ ein einstelliges Funktionssymbol.

1. Bestimme

   $(\exists x(x=c)){\frac {z}{x}}.$

2. Bestimme

   $(\exists x(x=c)){\frac {x}{x}}.$

3. Bestimme

   $(\exists x(x=c)){\frac {fx}{x}}.$

Aufgabe * (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.

Aufgabe * (2 Punkte)

Zeige, dass in einem kommutativen Halbring die Beziehung ${}0\cdot 0=0$ gilt.

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

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe. Es sei ${}I$ eine ${}S$- Interpretation mit der Grundmenge ${}N$ und es sei ${}\Gamma :=I^{\vDash }$ mit der zugehörigen Äquivalenzrelation ${}\sim$ auf der Termmenge ${}T$.

1. Zeige, dass ${}s\sim t$ genau dann gilt, wenn ${}I(s)=I(t)$ gilt.
2. Zeige, dass es eine injektive Abbildung

   $\psi \colon T/\sim \longrightarrow N$

   mit

   ${}\psi ([t])=I(t)\,$

   gibt.

3. Zeige, dass ${}\psi$ ein ${}S$- Homomorphismus ist, wenn die Quotientenmenge ${}T/\sim$ mit der kanonischen ${}S$- Struktur versehen wird.
4. Es sei ${}J$ die kanonische Interpretation auf ${}T/\sim$. Es sei vorausgesetzt, dass die Terminterpretation für ${}N$ surjektiv sei. Zeige, dass ${}I\vDash \alpha$ genau dann gilt, wenn ${}J\vDash \alpha$ gilt.

Aufgabe * (4 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe ${}\mathbb {Z} /(2)\times \mathbb {Z} /(3)$ zum Symbolalphabet ${}S=\{0,+\}$.

Aufgabe (5 Punkte)

Man entwerfe ein Programm für eine Registermaschine, das bei der Eingabe ${}n$ im ersten Register den Rest bei der Division mit Rest von ${}n$ durch ${}5$ ausgibt.

Aufgabe * (3 (2+1) Punkte)

1. Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, arithmetisch repräsentierbar ist.
2. Formuliere in der arithmetischen Sprache, dass die ${}7$ keine Summe von drei Quadraten ist.

Aufgabe * (3 Punkte)

Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.

Aufgabe * (2 Punkte)

Zeige, dass in der ${}K$- Modallogik das Schema

$\Box \alpha \wedge \Box \neg \alpha \rightarrow \Box \beta$

ableitbar ist.

Aufgabe * (2 Punkte)

Wir arbeiten mit den Aussagenvariablen ${}p,q,r$. Im Weltpunkt ${}a$ gelte

$a\vDash p,q,\neg r$

und im Weltpunkt ${}b$ gelte

$b\vDash p,\neg q,r.$

Bestimme die Wahrheitswerte von ${}\Box p\wedge \Diamond (\neg q)\rightarrow \Box r$ in den beiden Weltpunkten.

Aufgabe * (4 Punkte)

Beweise den Vollständigkeitssatz der Modallogik.