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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
2. Eine induktiv geordnete Menge ${}(I,\preccurlyeq )$.
3. Das Alphabet einer Sprache erster Stufe.
4. Die Eigenschaft einer Ausdrucksmenge ${}\Gamma \subseteq L^{S}$, Beispiele zu enthalten.
5. Die Addition in einem Dedekind-Peano-Modell ${}\mathbb {N}$.
6. Der modallogische Folgerungsbegriff.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Wohlordnungsprinzip für erststufige Aussagen.
2. Das Isomorphielemma.
3. /Fakt/Name

Aufgabe * (3 Punkte)

In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit ${}V$ (vordere Tafel), ${}M$ (mittlere Tafel) und ${}H$ (hintere Tafel) bezeichnet. Aufgrund der Höhe des Gestells sind nur (maximal) zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge (alle Möglichkeiten!) muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll.

Aufgabe * (3 Punkte)

Bei einem Zwei-Personen-Regel-Spiel (wie Schach) spielen zwei Personen (${}A$ und ${}B$) nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für ${}A$ ist, da ist ${}A$ am Zug und kann ${}B$ schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge ${}S$ aller Stellungen eine Gewinnstellung für ${}A$ (mit ${}A$ am Zug) ist.

Aufgabe * (2 Punkte)

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

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

Aufgabe * (4 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Zeige

${}\Gamma ^{\vdash }={\left(\Gamma ^{\vdash }\right)}^{\vdash }\,.$

Aufgabe * (7 Punkte)

Beweise den Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen im abzählbaren Fall.

Aufgabe * (3 Punkte)

Es seien ${}x_{1},x_{2}$ Variablen, ${}t_{1},t_{2}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Zeige, dass

${\left(\alpha {\frac {t_{1}}{x_{1}}}\right)}{\frac {t_{2}}{x_{2}}}\rightarrow \alpha {\frac {t_{1},t_{2}}{x_{1},x_{2}}}$

im Allgemeinen nicht allgemeingültig ist.

Aufgabe (0 Punkte)

Aufgabe * (2 (0.5+0.5+0.5+0.5) Punkte)

Wir zählen

${\text{ ich}},\,{\text{ Mama}},\,{\text{ Oma}},\,{\text{Uroma}},\,{\text{Ururoma}},\ldots .$

1. Was ist die Mama der Urururoma?
2. Was ist die Uroma der Uroma?
3. Was ist die Oma der Oma der Oma?
4. Was ist die Ururoma der Uroma?

Aufgabe * (8 Punkte)

Beweise das Wohlordnungsprinzip für erststufige Aussagen für Peano-Halbringe.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (11 (2+2+4+1+2) Punkte)

Wir betrachten die Identität

$\operatorname {Id} \colon \mathbb {N} \longrightarrow \mathbb {N}$

und den Ausdruck ${}x=y$, den wir mit ${}\psi$ bezeichnen. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ die Ausdrucksmenge, die die Kommutativität und die Assoziativität der Addition besagt sowie, dass ${}0$ das neutrale Element der Addition ist.

1. Zeige, dass der Graph der Identität durch ${}\psi$ schwach repräsentierbar in ${}\Gamma$ ist.
2. Zeige, dass der Graph der Identität nicht repräsentierbar in ${}\Gamma$ ist.
3. Zeige, dass der Graph der Identität repräsentierbar in der Peano-Arithmetik ${}{\rm {PA}}$ ist.
4. Ist die Identität als Abbildung repräsentierbar in der Peano-Arithmetik?
5. Gilt

   $\Gamma \vdash \exists !y\psi (n,y)$

   für jedes ${}n\in \mathbb {N}$ (dabei werde ${}n$ durch eine ${}n$-fache Summe der ${}1$ mit sich in beliebiger Klammerung wiedergegeben)?

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)