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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Wort über einem Alphabet ${}A$.
2. Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Die (rekursiv definierte) Gültigkeit eines prädikatenlogischen ${}S$-Ausdruckes ${}\alpha$ bei einer ${}S$- Interpretation auf einer Menge ${}M$.
4. Ein ${}S$-Homomorphismus

   $\varphi \colon M\longrightarrow N$

   zwischen zwei ${}S$- Strukturen ${}M$ und ${}N$.

5. Die Multiplikation mit ${}n\in \mathbb {N}$ in einem Dedekind-Peano-Modell ${}\mathbb {N}$.
6. Die Ableitbarkeit eines modallogischen Ausdrucks ${}\alpha$ im ${}K$-System.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Wiles (Großer Fermat).
2. Der Vollständigkeitssatz für Tautologien (Prädikatenlogik).
3. Der erste Gödelsche Unvollständigkeitssatz.

Aufgabe * (2 Punkte)

Professor Knopfloch und Dr. Eisenbeis stehen am Ufer des Rubbenbruchsees und können sich nicht einigen, ob sie mit dem oder gegen den Uhrzeigersinn drumrum laufen sollen. Deshalb läuft Professor Knopfloch gegen den Uhrzeigersinn und Dr. Eisenbeis mit dem Uhrzeigersinn. Das Verhältnis ihrer Geschwindigkeiten ist ${}5:4$, und daher läuft Knopfloch fünfmal um den See und Eisenbeis viermal um den See. Wie oft begegnen sie sich (Begegnung ganz am Anfang und am Ende mitzählen)?

Aufgabe * (2 Punkte)

Wenn Karl an Susanne denkt, bekommt er feuchte Hände, einen Kloß im Hals und einen roten Kopf. Einen roten Kopf bekommt er genau dann, wenn er an Susanne denkt oder wenn er das leere Tor nicht trifft. Wenn Karl das leere Tor trifft, bekommt er feuchte Hände. Karl bekommt den Ball vor dem leeren Tor. Kurz darauf bekommt er feuchte Hände, einen roten Kopf, aber keinen Kloß im Hals. Hat er an Susanne gedacht? Hat er das leere Tor getroffen?

Aufgabe * (2 Punkte)

Erläutere das Beweisprinzip der vollständigen Induktion.

Aufgabe * (3 Punkte)

Es sei ${}A$ ein Alphabet mit ${}3$ Symbolen. Wie viele Wörter über ${}A$ der Länge ${}5$ gibt es, wenn man nicht zwischen den Leserichtungen unterscheiden kann?

Aufgabe * (5 Punkte)

Es sei ${}n\in \mathbb {N} _{+}$. Man gebe ein Beispiel für eine aussagenlogische widersprüchliche Ausdrucksmenge

${}\Gamma =\{\alpha _{1},\alpha _{2},\ldots ,\alpha _{n}\}\,$

derart, dass jede echte Teilmenge davon widerspruchsfrei ist.

Aufgabe * (4 Punkte)

Es sei ${}V$ eine Menge an Aussagenvariablen und  ${}\Gamma \subseteq L^{V}$  eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Zeige, dass für jedes  ${}\alpha \in L^{V}$  entweder  ${}\alpha \in \Gamma$  oder  ${}\neg \alpha \in \Gamma$  gilt.

Aufgabe (3 Punkte)

Man erläutere durch Beispiele, dass der Aufbau der Prädikatenlogik nicht immer der mathematischen Intuition entspricht.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (2 (1+1) Punkte)

Wir betrachten das Symbolalphabet ${}S$, das neben Variablen aus einem einzigen zweistelligen Relationssymbol ${}R$ besteht, wobei in der abgebildeten Punktemenge das Relationssymbol ${}R$ als „(echt) rechts von“ interpretiert wird. Für zwei Punkte ${}P,Q$ bedeutet also ${}RPQ$, dass sich ${}P$ rechts von ${}Q$ befindet.

1. Welche(r) Punkt(e) erfüllt(en)

   $\exists y(Ryx\wedge \forall z(Rzx\rightarrow y=z)?$

2. Charakterisiere den Punkt ${}p_{0}$ mit einem ${}S$- Ausdruck in der einen freien Variablen ${}x$.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Zeige, dass ein gerichteter Graph genau dann symmetrisch ist, wenn für jede Teilmenge  ${}T\subseteq M$  die Beziehung

${}T\subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,$

gilt.