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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Wohlordnung auf einer Menge ${}M$.
2. Eine ${}n$-stellige Relation auf einer Menge ${}M$.
3. Die Termmenge zu einer Grundtermmenge ${}(V,K,F_{n})$.
4. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
5. Die Befehle für eine Registermaschine.
6. Die modallogische Sprache zu einer Aussagenvariablenmenge ${}V$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).
2. Der Vollständigkeitssatz der Prädikatenlogik.
3. /Fakt/Name

Aufgabe (1 Punkt)

Bruno liest in der Zeitung: „Im letzen Jahr war bei ${}50\%$ aller Autounfälle Alkohol mit im Spiel“. Bruno überlegt: „ ${}50\%$ mit Alkohol, ${}50\%$ ohne Alkohol. Dann ist es also egal, ob man was trinkt oder nicht. In Zukunft werde ich das auch nicht mehr so streng sehen“. Beurteile diese Überlegung!

Aufgabe * (3 Punkte)

Beweise den Satz, dass es unendlich viele Primzahlen gibt.

Aufgabe * (3 Punkte)

Definiere zu jeder Aussage ${}\alpha \in L^{V}$ die Menge ${}\operatorname {Var} _{}^{}{\left(\alpha \right)}$ der in ${}\alpha$ vorkommenden Aussagenvariablen.

Aufgabe * (2 Punkte)

Zeige

$\vdash \alpha \wedge \neg \alpha \rightarrow \beta$

unter Verwendung von

$\vdash \gamma \wedge \delta \rightarrow \delta \wedge \gamma$

(Lemma 3.14 (Einführung in die mathematische Logik (Osnabrück 2021))).

Aufgabe * (3 Punkte)

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

Aufgabe * (5 (4+1) Punkte)

Es sei ${}X$ ein topologischer Raum und ${}F$ ein topologischer Filter auf ${}X$, ${}T\subseteq X$ eine offene Teilmenge und ${}T\notin F$.

1. Zeige, dass das Mengensystem

   ${\left\{U\mid U\subseteq X{\text{ offen}},\,{\text{es gibt }}V\in F{\text{ mit }}V\cap {\left(X\setminus T\right)}\subseteq U\right\}}$

   ein Filter auf ${}X$ ist, der ${}X\setminus T$ enthält und ${}T$ nicht enthält.

2. Zeige mit Hilfe des Lemmas von Zorn, dass es einen Ultrafilter ${}G$ mit ${}F\subseteq G$ und mit ${}T\notin G$ gibt.

Aufgabe * (1 Punkt)

Man finde eine äquivalente Formulierung für die Aussage „Frau Maier-Sengupta hat nicht alle Tassen im Schrank“ mit Hilfe einer Existenzaussage.

Aufgabe * (5 Punkte)

Es seien ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}f$ ein ${}n$-stelliges Funktionssymbol. Zeige, dass die Ableitbarkeit

$\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}$

gilt.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Reflexivitätsaxiom genau dann gilt, wenn ${}R$ reflexiv ist.