Kurs:Einführung in die mathematische Logik/14/Klausur mit Lösungen

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$.

Lösung

1. Die zugehörige Interpretation ${}I=I^{\lambda }$ wird rekursiv über den Aufbau der Sprache wie folgt festgelegt.
   1. ${}I(v)=\lambda (v)$ für jede Aussagenvariable ${}v\in V$.
   2. Bei ${}\alpha =\neg (\beta )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0\,,\\0,{\text{ falls }}I(\beta )=1\,.\end{cases}}\,$

   3. Bei ${}\alpha =(\beta )\wedge (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )=1\,,\\0{\text{ sonst}}\,.\end{cases}}\,$

   4. Bei ${}\alpha =(\beta )\vee (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=1{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=I(\gamma )=0\,.\end{cases}}\,$

   5. Bei ${}\alpha =(\beta )\rightarrow (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=1{\text{ und }}I(\gamma )=0\,.\end{cases}}\,$

   6. Bei ${}\alpha =(\beta )\leftrightarrow (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )\,,\\0,{\text{ falls }}I(\beta )\neq I(\gamma )\,.\end{cases}}\,$

2. Ein Element ${}x\in I$ heißt obere Schranke für ${}J$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in J$ gilt.
3. Unter einer ${}S$-Struktur versteht man eine nichtleere Menge ${}M$ mit den folgenden Festlegungen.
   1. Für jede Konstante ${}c\in K$ ist ein Element ${}c^{M}\in M$ festgelegt.
   2. Zu jedem ${}n$-stelligen Funktionssymbol ${}f$ (aus ${}S$) ist eine ${}n$-stellige Funktion

      $f^{M}\colon M^{n}\longrightarrow M$

      festgelegt.

   3. Zu jedem ${}n$-stelligen Relationssymbol ${}R$ (aus ${}S$) ist eine ${}n$-stellige Relation

      $R^{M}\subseteq M^{n}$

      festgelegt.

4. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, wenn für jede ${}S$- Interpretation ${}I$ mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.
5. Man sagt, dass ${}T$ ${}R$-aufzählbar ist, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei Eingabe von ${}0$ nach und nach genau die Zahlen aus ${}T$ ausdruckt.
6. Man sagt, dass eine Menge ${}\Gamma$ von modallogischen Ausdrücken in einem modallogischen Modell ${}(M,R,\mu )$ gilt, wenn

   $(M,R,\mu )\vDash \alpha$

   für alle ${}\alpha \in \Gamma$ gilt.

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.

Lösung

1. Es seien ${}N_{1}$ und ${}N_{2}$ Dedekind-Peano-Modelle für die natürlichen Zahlen. Dann gibt es eine eindeutig bestimmte bijektive Abbildung

   $\varphi \colon N_{1}\longrightarrow N_{2}$

   mit ${}\varphi (0_{1})=0_{2}$ und

   ${}\varphi (n')=(\varphi (n))'\,$

   für alle ${}n\in N_{1}$.
2. 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. Dann gelten folgende Aussagen.
   1. Es ist ${}I_{1}(t)=I_{2}(t)$.
   2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$.
3. Es sei ${}\Gamma$ eine Menge von modallogischen Ausdrücken und ${}\alpha$ ein modallogischer Ausdruck. Dann ist

   $\Gamma \vdash \alpha$

   genau dann, wenn

   $\Gamma \vDash \alpha .$

Aufgabe (2 Punkte)

Erläutere das Prinzip Beweis durch Widerspruch.

Lösung

Man möchte eine Aussage ${}A$ beweisen. Man nimmt an, dass ${}A$ nicht gilt. Daraus leitet man durch logisch korrektes Schließen einen Widerspruch her. Somit kann ${}\neg A$ nicht gelten und also muss ${}A$ gelten.

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?

Lösung

Die Wahrscheinlichkeit, dass als erstes eine U-Bahn nach Konsau kommt, muss viermal so groß sein wie die Wahrscheinlichkeit, dass zuerst eine U-Bahn nach Heinsheim kommt. Deshalb muss in einem Zehn-Minuten-Intervall acht Minuten lang eine U-Bahn nach Konsau die nächste sein (und zwei Minuten lang eine U-Bahn nach Heinsheim). Die U-Bahnen nach Konsau fahren also ${}:\!09,:\!19,:\!29$ etc. 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$.

Lösung

Aus der Voraussetzung und der Konjunktionsregel (Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)) ergibt sich

$\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}.$

Daraus und aus der Voraussetzung

$\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$

ergibt sich mittels Modus ponens (Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (3))

$\Gamma \vdash \alpha .$

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?

Lösung

Das ist keine Ordnungsrelation, da die Antisymmetrie nicht erfüllt ist. Wenn man zwei verschiedene Teilmengen aus ${}M$ nimmt, sagen wir ${}S$ und ${}T$, die beide die gleiche Anzahl besitzen (was es gibt, sobald ${}M$ zumindest zwei Elemente besitzt), so gilt ${}{\#\left(S\right)}={\#\left(T\right)}$ und damit

${}S\preccurlyeq T\,$

und

${}T\preccurlyeq S\,,$

aber daraus kann nicht auf ${}S=T$ geschlossen werden.

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.

Lösung

Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes ${}\alpha \in L^{V}$ die Alternative ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für ${}\alpha =p$ eine Aussagenvariable ist dies Teil der Voraussetzung. Bei ${}\alpha =\neg \beta$ folgt wegen ${}\vdash \neg {\left(\neg \beta \right)}\leftrightarrow \beta$ die Aussage aus der Induktionsvoraussetzung, da ${}\Gamma$ abgeschlossen unter Ableitungen ist. Es sei nun ${}\alpha =\beta \wedge \gamma$. Bei ${}\beta \in \Gamma$ und ${}\gamma \in \Gamma$ ist wegen der Ableitungsabgeschlossenheit auch ${}\beta \wedge \gamma \in \Gamma$. Wenn hingegen ${}\beta \notin \Gamma$ ist, so folgt nach der Induktionsvoraussetzung ${}\neg \beta \in \Gamma$. Aufgrund der Tautologie ${}\vdash \neg \beta \rightarrow \neg {\left(\beta \wedge \gamma \right)}$ ergibt sich ${}\neg \alpha =\neg {\left(\beta \wedge \gamma \right)}\in \Gamma$. Der Beweis für die Implikation verläuft ähnlich, siehe Aufgabe 4.16 (Einführung in die mathematische Logik (Osnabrück 2021)).

Zum Nachweis, dass ${}\Gamma$ maximal widerspruchsfrei ist, sei ${}\alpha \notin \Gamma$ angenommen. Nach dem, was wir eben bewiesen haben, gilt dann ${}\neg \alpha \in \Gamma$. Dann ist aber ${}\alpha ,\neg \alpha \in \Gamma \cup \{\alpha \}$ und somit ist diese erweiterte Menge widersprüchlich.

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.

Lösung

1. In dieser Nacht gibt es eine Katze, die nicht grau ist.
2. Es gibt eine Nacht und eine Katze, die in dieser besagten Nacht nicht grau ist.

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.

Lösung

Es sei ${}I$ eine Interpretation mit

$I\vDash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n},$

also

$I(s_{1})=I(t_{1}),\ldots ,I(s_{n})=I(t_{n}),$

und

$I\vDash \alpha {\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}.$

Nach dem Substitutionslemma bedeutet dies

$I{\frac {I(s_{1}),\ldots ,I(s_{n})}{x_{1},\ldots ,x_{n}}}\vDash \alpha .$

Wegen der Gleichheiten ${}I(s_{j})=I(t_{j})$ kann man dies genauso gut als

$I{\frac {I(t_{1}),\ldots ,I(t_{n})}{x_{1},\ldots ,x_{n}}}\vDash \alpha$

schreiben. Mit dem Substitutionslemma ergibt sich hieraus wiederum

$I\vDash \alpha {\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}.$

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.

Lösung

Durch Existenzeinführung im Sukzedenz haben wir

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

und

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

und daraus

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

Dabei ist ${}y$ hinten gebunden und somit kann man mit der Existenzeinführung im Antezedens auf

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

schließen. Da auch ${}x$ hinten gebunden ist, ergibt sich

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

Aufgabe weiter

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.

Lösung

1. Es ist lediglich zu zeigen, dass ${}M$ unter der Addition und der Multiplikation abgeschlossen sind. Dies ist für die Addition mit ${}0$ und der Multiplikation mit ${}0$ klar. Ferner ist die Summe (bzw. das Produkt) von zwei rationalen Zahlen, die beide ${}\geq 1$ sind, selbst wieder ${}\geq 1$.
2. Wenn ${}a=0$ ist, so ist wegen ${}0\leq b$ automatisch auch die rechte Seite erfüllt, und wenn ${}b=0$ ist, so ist wegen

   ${}a0=0\,$

   auch die linke Seite erfüllt. Wir können also und auf den Fall ${}a,b\neq 0$ beschränken. Wenn ${}a$ das Element ${}b$ teilt, so bedeutet dies, dass es ein ${}x\in M$ mit

   ${}ax=b\,$

   gibt. Dies bedeutet einfach, dass der in ${}\mathbb {Q}$ genommene Quoient ${}{\frac {b}{a}}$ zu ${}M$ gehört, also ${}\geq 1$ ist. Doch dies ist äquivalent zu ${}b\geq a$.

3. Es ist

   ${}{\frac {6}{5}}={\frac {12}{10}}={\frac {12}{11}}\cdot {\frac {11}{10}}\,$

   eine Darstellung in Faktoren, die beide keine Einheit sind.

4. Die ${}0$ und die (einzige) Einheit ${}1$ sind nach Definition nicht irreduzibel. Für ${}a,b\in \mathbb {N} _{+}$ mit ${}{\frac {b}{a}}>1$ ist

   ${}{\frac {b}{a}}={\frac {2b}{2a}}={\frac {2b-1}{2a}}\cdot {\frac {2b}{2b-1}}\,$

   und wegen ${}b>a$ ist auch

   ${}2b-1>2a\,,$

   also gehören die beiden Faktoren zu ${}M$.

5. Der erste Teil der Konjunktion, also ${}\alpha {\frac {0}{x}}$, ist unmittelbar wegen des ersten Teils der Disjunktion wahr. Es sei also ${}\alpha$ wahr für ein bestimmtes ${}x$. Der Nachfolger davon, also ${}x+1$, steht bereits in der Form des zweiten Teils der Disjunktion da.
6. Wir betrachten das Induktionsaxiom für die Aussage aus Teil (5). Die Voraussetzungen, also Induktionsanfang und Induktionsschritt, gelten wie in Teil (5) gezeigt. Hingegen gilt die Aussage ${}\alpha$ nicht für alle ${}x\in M$, beispielsweise gilt sie für ${}x={\frac {3}{2}}$ nicht.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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).

Lösung

Es bestehe ${}M$ aus zwei Welten ${}v$ und ${}w$ mit der vollen Relation. Es gelte

$v\vDash p,\,v\vDash \neg q,\,w\vDash \neg p,\,w\vDash q.$

Damit gilt

$v\vDash p\vee q{\text{ und }}w\vDash p\vee q$

und somit

$v\vDash \Box (p\vee q).$

Dagegen gilt in ${}v$ weder ${}\Box p$ noch ${}\Box q$.