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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine maximal widerspruchsfreie Teilmenge ${}\Gamma \subseteq L^{V}$ zu einer Menge ${}V$ an Aussagenvariablen.
2. Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.
3. Die Interpretation der Terme zu einem Symbolalphabet ${}S$ in einer gegebenen ${}S$- Interpretation auf einer Grundmenge ${}M$.
4. Ein atomarer Ausdruck in der Prädikatenlogik.
5. Eine ${}R$-berechenbare Funktion

   $F\colon \mathbb {N} ^{k}\longrightarrow \mathbb {N} .$

6. Das modallogische Reflexivitätsaxiom.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Division mit Rest in einem Peano-Halbring.
2. Der Vollständigkeitssatz der Prädikatenlogik.
3. Der erste Gödelsche Unvollständigkeitssatz.

Aufgabe * (1 Punkt)

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

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

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

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr ${}2015$ weiß man, dass ${}17$ Tage sockenzerstreut und ${}11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr ${}2013$ weiß man, dass ${}270$ Tage sockenzerstreut und ${}120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.

Aufgabe (3 Punkte)

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.

Aufgabe * (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die folgende Regel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha _{1},\ldots ,\Gamma \vdash \alpha _{n}$ und ${}\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$, dann auch ${}\Gamma \vdash \beta$.

Aufgabe * (8 (3+5) Punkte)

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$- Term und ${}\alpha$ ein ${}U$- Ausdruck. Es seien zwei ${}S$- Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Beweise die folgenden Aussagen.

1. Es ist ${}I_{1}(t)=I_{2}(t)$.
2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus ${}U$ und auf den in ${}\alpha$ frei vorkommenden Variablen identisch sind).

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Es seien ${}A,B,C$ einstellige Relationssymbole. Zeige, dass der Modus Darii, also die Aussage

$(\forall x(Ax\rightarrow Bx)\wedge \exists x(Ax\wedge Cx))\rightarrow (\exists x(Bx\wedge Cx))$

im Prädikatenkalkül ableitbar ist.

Aufgabe * (6 (3+3) Punkte)

Es sei ${}(M,0,N)$ ein Modell für die Peano-Axiome für den Nachfolger.

1. Zeige, dass ${}N$ fixpunktfrei ist, d.h. dass

   ${}N(x)\neq x\,$

   für alle ${}x\in M$.

2. Zeige, dass ${}N$ periodenfrei ist. D.h. für jedes ${}\ell \in \mathbb {N} _{+}$ ist

   ${}N^{\ell }(x)\neq x\,,$

   wobei

   ${}N^{\ell }=N\circ \cdots \circ N\,$

   die ${}\ell$-fache Hintereinanderschaltung von ${}N$ bedeutet.

Aufgabe * (4 Punkte)

Zeige, dass es einen Peano-Halbring ${}M$ mit der Eigenschaft gibt, dass es darin ein Element ${}x\in M$ gibt, das größer als jede natürliche Zahl in ${}M$ (also Zahlen der Form ${}1+1+\cdots +1$) ist.

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

Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze ${}1,2,3,4$ nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz ${}3$ bestreiten. Von einer solchen Runde seien die Mannschaften ${}A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.

1. Welche Information über die Platzierung kann man stets aus den Daten erschließen?
2. Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
3. unter welcher nicht?

Aufgabe (0 Punkte)

Aufgabe * (3 Punkte)

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

Aufgabe (0 Punkte)

Aufgabe * (6 (4+2) Punkte)

1. Skizziere ein modallogisches Modell, bei dem es verschiedene Weltpunkte ${}v,w$ mit

   $v\vDash \neg \Box p$

   und

   $w\vDash \Box \Box p\wedge \Diamond p\wedge \Diamond \neg p$

   gibt.

2. Was ist die minimale Anzahl von Welten in einem modallogischen Modell, in dem die Anforderungen aus 1) realisierbar sind.