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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe (4 (1+3) Punkte)Referenznummer erstellen

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

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

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

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

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

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

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

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

Beweise den Fixpunktsatz der Prädikatenlogik.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen