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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.
2. Ein Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.
3. Die Variablensubstitution ${}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ für einen ${}S$-Ausdruck ${}\alpha$, wobei ${}x_{1},\ldots ,x_{k}$ Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme seien.
4. Die Ableitbarkeit eines Ausdrucks ${}\alpha \in L^{S}$ im prädikatenlogischen Kalkül.
5. Die Arithmetische Repräsentierbarkeit einer Abbildung

   $F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}.$

6. Eine (formale) Modallogik.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Endlichkeitssatz für die Prädikatenlogik.
3. Das Unvollständigkeitslemma.

Aufgabe (4 (1+3) Punkte)

In einer Höhle befinden sich im Innern am Ende des Ganges vier Personen. Sie haben eine Taschenlampe bei sich und der Gang kann nur mit der Taschenlampe begangen werden. Dabei können höchstens zwei Leute gemeinsam durch den Gang gehen. Die Personen sind unterschiedlich geschickt, die erste Person benötigt eine Stunde, die zweite Person benötigt zwei Stunden, die dritte Person benötigt vier Stunden und die vierte Person benötigt fünf Stunden, um den Gang zu durchlaufen. Wenn zwei Personen gleichzeitig gehen, entscheidet die langsamere Person über die Geschwindigkeit.

1. Die Batterie für die Taschenlampe reicht für genau ${}13$ Stunden. Können alle vier die Höhle verlassen?
2. Die Batterie für die Taschenlampe reicht für genau ${}12$ Stunden. Können alle vier die Höhle verlassen?

Aufgabe (0 Punkte)

Aufgabe * (22 (1+3+3+4+4+3+4) Punkte)

Es sei ${}V$ eine (nichtleere) Aussagenvariablenmenge und

${}\operatorname {Bel} \,{\left(V\right)}=\operatorname {Abb} \,{\left(V,\{0,1\}\right)}\,$

die Menge aller Wahrheitsbelegungen auf ${}V$. In dieser Aufgabe untersuchen wir ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ und die Abbildung

$\Psi \colon L^{V}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)},\,\alpha \longmapsto {\left(\lambda \mapsto I^{\lambda }(\alpha )\right)}.$

Dabei spielen die beiden folgenden Teilmengen eine Rolle.

Es sei ${}N\subseteq \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ die folgendermaßen festgelegte Teilmenge. Eine Abbildung ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ gehört genau dann zu ${}N$, wenn es eine endliche Teilmenge ${}W\subseteq V$ derart gibt, dass ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ ist (dies ist in Aufgabenteil 2 zu erläutern).

Es sei ${}M\subseteq \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ die durch die folgenden Bedingungen rekursiv festgelegte Teilmenge.

a) Zu ${}p\in V$ gehört

$\operatorname {ev} _{p}\colon \operatorname {Bel} \,{\left(V\right)}\longrightarrow \{0,1\},\,\lambda \longmapsto \lambda (p),$

zu ${}M$.

b) Wenn ${}\varphi \in M$ ist, so gehört auch ${}\tau \circ \varphi$ zu ${}M$, wobei ${}\tau \colon \{0,1\}\rightarrow \{0,1\}$ die Vertauschungsabbildung bezeichnet.

c) Wenn ${}\varphi ,\theta \in M$ sind, so gehören auch ${}{\min {\left(\varphi ,\theta \right)}}$ und ${}{\max {\left(\varphi ,\theta \right)}}$ zu ${}M$.

1. Ist ${}\Psi$ injektiv?
2. Es sei ${}W\subseteq V$ eine Teilmenge. Zeige, dass es eine natürliche surjektive Abbildung

   $\operatorname {Bel} \,{\left(V\right)}\longrightarrow \operatorname {Bel} \,{\left(W\right)}$

   und eine natürliche injektive Abbildung

   $\Phi _{W}\colon \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$

3. Zeige, dass die in (2) beschriebene Abbildung

   $\Phi _{W}\colon \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$

   die Evaluationen ${}\operatorname {ev} _{p}$, die Verknüpfung mit ${}\tau$ und die Minima und Maxima respektiert.

4. Man gebe bei ${}V$ unendlich ein ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ an, das nicht zu ${}N$ gehört.
5. Es sei ${}V$ endlich. Zeige

   ${}M=\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}\,.$

6. Zeige ${}M=N$.
7. Zeige, dass das Bild von ${}\Psi$ mit ${}M$ übereinstimmt.

Aufgabe * (5 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine endliche Menge an Aussagen. Skizziere ein Entscheidungsverfahren, mit dem man feststellen kann, ob ${}\Gamma$ widersprüchlich ist oder nicht.

Aufgabe (3 Punkte)

Es sei ${}A(n)$ eine Aussage(nform), in die man eine natürliche Zahl einsetzen kann. Diskutiere den Unterschied zwischen den beiden Aussagen

${\left(\forall nA(n)\right)}\rightarrow {\left(\forall nA(n+1)\right)}\,\,{\text{ und }}\,\,\forall n{\left(A(n)\rightarrow A(n+1)\right)}.$

Was ist die mathematische Relevanz der beiden Aussagen?

Aufgabe * (3 Punkte)

Wir rechnen mit den Zahlen ${}0,1,2,{\text{viele}}\,\,(v)$ nach den folgenden Verknüpfungstabellen.

${}+$	${}0$	${}1$	${}2$	${}v$
${}0$	${}0$	${}1$	${}2$	${}v$
${}1$	${}1$	${}2$	${}v$	${}v$
${}2$	${}2$	${}v$	${}v$	${}v$
${}v$	${}v$	${}v$	${}v$	${}v$

und

${}\cdot$	${}0$	${}1$	${}2$	${}v$
${}0$	${}0$	${}0$	${}0$	${}0$
${}1$	${}0$	${}1$	${}2$	${}v$
${}2$	${}0$	${}2$	${}v$	${}v$
${}v$	${}0$	${}v$	${}v$	${}v$

Zeige, dass es sich dabei um einen kommutativen Halbring handelt. Gilt für diesen die Abziehregel?

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (3 Punkte)

Erstelle ein Programm für eine Registermaschine, das abwechselnd ${}1$ und ${}0$ ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Sprungbefehl verwendet.

Aufgabe * (10 Punkte)

Beweise den Fixpunktsatz der Prädikatenlogik.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)