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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (1 Punkt)Referenznummer erstellen

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

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

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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

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

Aufgabe * (4 Punkte)Referenznummer erstellen

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

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

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

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

Aufgabe * (3 Punkte)Referenznummer erstellen

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

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (6 (4+2) Punkte)Referenznummer erstellen

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.