Kurs:Einführung in die mathematische Logik/14/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	2	5	2	4	4	12	0	0	0	0	0	2	43

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die zu einer (aussagenlogischen) Wahrheitsbelegung

   $\lambda \colon V\longrightarrow \{0,1\}$

   auf einer Aussagenvariablenmenge ${}V$ zugehörige Interpretation auf der Sprache ${}L^{V}$.

2. Eine obere Schranke zu einer Teilmenge ${}J\subseteq I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Eine ${}S$-Struktur zu einem Symbolalphabet ${}S$ einer Sprache erster Stufe.
4. Die Folgerungsbeziehung ${}\Gamma \vDash \alpha$, wobei ${}\Gamma$ eine Menge von ${}S$- Ausdrücken und ${}\alpha$ ein ${}S$-Ausdruck ist (und ${}S$ ein Symbolalphabet.)
5. Die ${}R$-Aufzählbarkeit einer Teilmenge ${}T\subseteq \mathbb {N}$.
6. Die Gültigkeit einer modallogischen Ausdrucksmenge ${}\Gamma$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.
2. Das Koinzidenzlemma.
3. Der Vollständigkeitssatz der Modallogik.

Aufgabe * (2 Punkte)

Erläutere das Prinzip Beweis durch Widerspruch.

Aufgabe * (2 Punkte)

Anna kann sich nicht zwischen Heinrich und Konrad entscheiden, deshalb lässt sie sich vom Zufall leiten. Sie wohnt an einer U-Bahn-Station der Linie ${}5$, die von Heinsheim nach Konsau fährt. Heinrich wohnt in Heinsheim und Konrad in Konsau. Wenn Anna Lust auf ein Date hat, geht sie einfach zu ihrer Station und nimmt die erstbeste U-Bahn, die gerade kommt. Die U-Bahnen fahren in beide Richtungen im Zehn-Minuten-Takt und die U-Bahnen nach Heinsheim fahren ${}:\!01,:\!11,:\!21$ etc. Nach einiger Zeit stellt Anna fest, dass sie Konrad viermal so häufig besucht wie Heinrich. Wann fahren die U-Bahnen nach Konsau ab?

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 * (2 Punkte)

Es sei ${}M$ eine endliche Menge. Betrachte die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch

$S\preccurlyeq T,{\text{ falls }}{\#\left(S\right)}\leq {\#\left(T\right)},$

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?

Aufgabe * (5 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Es sei ${}\Gamma$ widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable ${}p\in V$ gelte ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$. Zeige, dass dann ${}\Gamma$ maximal widerspruchsfrei ist.

Aufgabe * (2 (1+1) Punkte)

Wir betrachten den Satz „Nachts sind alle Katzen grau“.

1. Negiere diesen Satz durch eine Existenzausssage, wenn der Satz sich auf eine bestimmte Nacht bezieht.
2. Negiere diesen Satz durch eine Existenzausssage, wenn der Satz sich auf jede Nacht bezieht.

Aufgabe * (4 Punkte)

Es seien ${}x_{1},\ldots ,x_{n}$ Variablen, ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache ${}L^{S}$. Zeige, dass

$s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(\alpha {\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow \alpha {\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}$

allgemeingültig ist.

Aufgabe * (4 Punkte)

Zeige, dass

$\vdash \exists x\exists y\alpha \rightarrow \exists y\exists x\alpha$

im Kalkül der Prädikatenlogik ableitbar ist.

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

Es sei

${}M=\{0\}\cup \mathbb {Q} _{\geq 1}\,.$

1. Zeige, dass ${}M$ ein kommutativer Halbring ist.
2. Zeige, dass in ${}M$ die Relationen

   $a{\text{ teilt }}b{\text{ oder }}a=0$

   und

   $a\leq b{\text{ oder }}b=0$

   zueinander äquivalent sind.

3. Zeige, dass ${}{\frac {6}{5}}$ nicht irreduzibel in ${}M$ ist.
4. Zeige, dass es in ${}M$ keine irreduziblen Elemente gibt.
5. Es sei ${}\alpha$ die Aussage

   $x=0\vee \exists y(x=y+1).$

   Zeige, dass in ${}M$ die Aussage

   $\alpha {\frac {0}{x}}\wedge {\left(\alpha \rightarrow \alpha {\frac {x+1}{x}}\right)}$

   wahr ist.

6. Zeige, dass ${}M$ kein Peano-Halbring ist.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (2 Punkte)

Zeige durch Angabe eines modallogischen Modelles, dass im ${}K$- System der Ausdruck

$\Box (p\vee q)\rightarrow \Box p\vee \Box q$

nicht ableitbar ist (dabei seien ${}p,q$ Aussagenvariablen).