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

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

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

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

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

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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

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

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

Wir zählen

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

Was ist die Mama der Urururoma?
Was ist die Uroma der Uroma?
Was ist die Oma der Oma der Oma?
Was ist die Ururoma der Uroma?

Aufgabe * (8 Punkte)Referenznummer erstellen

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

Aufgabe (0 Punkte)Referenznummer erstellen

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

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.

Zeige, dass der Graph der Identität durch ${}\psi$ schwach repräsentierbar in ${}\Gamma$ ist.
Zeige, dass der Graph der Identität nicht repräsentierbar in ${}\Gamma$ ist.
Zeige, dass der Graph der Identität repräsentierbar in der Peano-Arithmetik ${}{\rm {PA}}$ ist.
Ist die Identität als Abbildung repräsentierbar in der Peano-Arithmetik?
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)Referenznummer erstellen