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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Ableitbarkeit ${}\Gamma \vdash \alpha$ eines ${}S$-Ausdrucks ${}\alpha$ aus einer Menge ${}\Gamma$ an ${}S$- Ausdrücken.
2. Eine Abbildung ${}F$ von einer Menge ${}L$ in eine Menge ${}M$.
3. Die endliche Axiomatisierbarkeit einer Theorie ${}T\subseteq L_{0}^{S}$.
4. Ein reell-abgeschlossener Körper.
5. Die Eigenschaft einer Menge ${}\Gamma$ von arithmetischen Ausdrücken, Repräsentierungen zu erlauben.
6. Das modallogische Symmetrieaxiom.

Lösung

1. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ ableitbar ist, wenn es endlich viele Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma$ derart gibt, dass

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

   gilt.

2. Eine Abbildung ${}F$ von ${}L$ nach ${}M$ ist dadurch gegeben, dass jedem Element der Menge ${}L$ genau ein Element der Menge ${}M$ zugeordnet wird.
3. Die endliche Axiomatisierbarkeit von ${}T$ liegt vor, wenn es endlich viele Sätze ${}\alpha _{1},\ldots ,\alpha _{n}\in L_{0}^{S}$ mit ${}T=\{\alpha _{1},\ldots ,\alpha _{n}\}^{\vdash }$ gibt.
4. Ein angeordneter Körper ${}K$ heißt reell-abgeschlossen, wenn folgende Eigenschaften gelten.
   1. Jedes nichtnegative Element aus ${}K$ besitzt eine Quadratwurzel in ${}K$.
   2. Jedes Polynom ${}P\in K[X]$ mit ungeradem Grad besitzt in ${}K$ eine Nullstelle.
5. Man sagt, dass ${}\Gamma$ Repräsentierungen erlaubt, wenn ${}\Gamma$ jede ${}R$- berechenbare Relation und jede ${}R$- berechenbare Funktion repräsentiert.
6. Das modallogische Axiomenschema

   $\alpha \rightarrow \Box \Diamond \alpha$

   nennt man Symmetrieaxiom.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Wiles (Großer Fermat).
2. Der Satz von Henkin.
3. Der Fixpunktsatz für arithmetische Ausdrücke.

Lösung

1. Die diophantische Gleichung

   ${}x^{n}+y^{n}=z^{n}\,$

   besitzt für kein ${}n\geq 3$

   eine ganzzahlige nichttriviale Lösung.
2. Es sei ${}\Gamma$ eine Menge an ${}S$- Ausdrücken (über einem Symbolalphabet ${}S$), die maximal widerspruchsfrei ist und Beispiele enthält. Dann ist die durch die kanonische Termidentifizierung gegebene Interpretation ein Modell für ${}\Gamma$.
3. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem ${}\alpha \in L_{1}^{\rm {Ar}}$ einen Satz ${}q\in L_{0}^{\rm {Ar}}$ mit

   $\Gamma \vdash q\longleftrightarrow \alpha (GN(q)).$

Aufgabe (1 Punkt)

Petra fliegt zu ihrer ersten internationalen Konferenz. Als sie auf dem Weg zum Flughafen ihre Wohnung (sie wohnt allein) verlässt und gerade die Wohnungstür zugemacht hat, merkt sie (eine der drei Möglichkeiten)

1. Sie hat ihr Flugticket auf dem Schreibtisch vergessen.
2. Sie hat ihre Schlüssel auf dem Schreibtisch vergessen.
3. Sie hat ihren Reisepass auf dem Schreibtisch vergessen.

Was ist am schlimmsten?

Lösung

(1) und (3) sind jedenfalls nicht schlimm, da Petra die Schlüssel hat und daher direkt die vergessenen Sachen holen kann. Bei (2) hat sie dagegen ein Problem, wenn sie zurückkommt.

Aufgabe (2 Punkte)

Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?

Lösung

1. Leere Mulde auf dem Straßenplatz ${}A$ abladen.
2. Volle Mulde auf Fahrzeug hochladen.
3. Volle Mulde auf dem Straßenplatz ${}B$ abladen.
4. Leere Mulde auf Fahrzeug hochladen.
5. Leere Mulde auf den Garagenvorplatz abladen.
6. Volle Mulde auf Fahrzeug hochladen.

Es sind also sechs Ladevorgänge nötig.

Aufgabe (3 Punkte)

Beweise den Satz, dass es unendlich viele Primzahlen gibt.

Lösung

Angenommen, die Menge aller Primzahlen sei endlich, sagen wir ${}\{p_{1},p_{2},\ldots ,p_{r}\}$. Man betrachtet die Zahl

${}N=p_{1}\cdot p_{2}\cdot p_{3}{\cdots }p_{r}\ +1\,.$

Diese Zahl ist durch keine der Primzahlen ${}p_{i}$ teilbar, da bei Division von ${}N$ durch ${}p_{i}$ immer ein Rest ${}1$ verbleibt. Damit sind die Primfaktoren von ${}N$, die es nach Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024)) geben muss, nicht in der Ausgangsmenge enthalten - Widerspruch.

Aufgabe (3 Punkte)

Zeige, dass der aussagenlogische Ausdruck

${\left(r\rightarrow {\left(p\wedge \neg q\right)}\right)}\rightarrow {\left(\neg p\rightarrow {\left(\neg r\vee q\right)}\right)}$

allgemeingültig ist

Lösung

Wir müssen zeigen, dass für jede Wahrheitsbelegung ${}\lambda$ der Variablen ${}r,p,q$ der Wahrheitswert der Gesamtaussage gleich ${}1$ ist. Bei ${}\lambda (p)=1$ ist ${}\lambda (\neg p)=0$ und damit ist der Nachsatz und die Gesamtaussage wahr. Es sei also im Folgenden ${}\lambda (p)=0$. Dann ist ${}\lambda (p\wedge \neg q)=0$. Bei ${}\lambda (r)=1$ ist der Vordersatz falsch und somit die Gesamtaussage wahr. Es sei also ${}\lambda (r)=0$. Dann ist der Vordersatz wahr und wir müssen zeigen, dass auch der Nachsatz wahr ist. Es ist dann ${}\lambda (\neg r)=1$ und ${}\lambda (\neg r\vee q)=1$, also ist auch in diesem Fall der Nachsatz und die Gesamtaussage wahr.

Aufgabe (6 (2+4) Punkte)

Es seien ${}\alpha$ und ${}\beta$ Aussagen.

1. Zeige

   $\vdash {\left(\alpha \rightarrow \beta \right)}\rightarrow \neg {\left(\alpha \wedge \neg \beta \right)}.$

2. Zeige

   $\vdash \neg {\left(\alpha \wedge \neg \beta \right)}\rightarrow {\left(\alpha \rightarrow \beta \right)}.$

Lösung

1. Mit (einer Variante von) Lemma 3.17 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

   $\vdash \alpha \rightarrow {\left({\left(\alpha \rightarrow \beta \right)}\rightarrow \beta \right)}.$

   Mit Kontraposition des Nachsatzes ergibt sich daraus

   $\vdash \alpha \rightarrow {\left(\neg \beta \rightarrow \neg {\left(\alpha \rightarrow \beta \right)}\right)}.$

   Mit Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (4) folgt

   $\vdash \alpha \wedge \neg \beta \rightarrow \neg {\left(\alpha \rightarrow \beta \right)}$

   und mit Kontraposition

   $\vdash {\left(\alpha \rightarrow \beta \right)}\rightarrow \neg {\left(\alpha \wedge \ \neg \beta \right)}.$

2. Es ist

   $\vdash \beta \rightarrow {\left(\alpha \rightarrow \beta \right)}$

   und

   $\vdash \neg \alpha \rightarrow {\left(\neg \beta \rightarrow \neg \alpha \right)}$

   nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1). Mit Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021))  (6) (Kontraposition) ergibt sich

   $\vdash {\left(\neg \beta \rightarrow \neg \alpha \right)}\rightarrow {\left(\alpha \rightarrow \beta \right)}$

   und daraus und der zweiten Zeile mit der Kettenschlussregel

   $\vdash \neg \alpha \rightarrow {\left(\alpha \rightarrow \beta \right)}.$

   Mit Kontraposition (als Regel) ergibt sich aus der ersten und der letzten Zeile unter Verwendung von Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021)) wiederum

   $\vdash \neg {\left(\alpha \rightarrow \beta \right)}\rightarrow \neg \beta$

   und

   $\vdash \neg {\left(\alpha \rightarrow \beta \right)}\rightarrow \alpha .$

   Daraus ergibt sich wegen Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3)

   $\vdash \neg {\left(\alpha \rightarrow \beta \right)}\rightarrow \alpha \wedge \neg \beta$

   und somit

   $\vdash \neg {\left(\alpha \wedge \neg \beta \right)}\rightarrow {\left(\alpha \rightarrow \beta \right)}.$

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.

Lösung

Wegen der Widerspruchsfreiheit können nicht sowohl ${}\alpha$ als auch ${}\neg \alpha$ zu ${}\Gamma$ gehören. Wenn weder ${}\alpha$ noch ${}\neg \alpha$ zu ${}\Gamma$ gehören, so ist entweder ${}\Gamma \cup \{\alpha \}$ oder ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei, was der maximalen Widerspruchsfreiheit von ${}\Gamma$ widerspricht. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck ${}\beta$ sowohl

$\Gamma \cup \{\alpha \}\vdash \beta$

als auch

$\Gamma \cup \{\neg \alpha \}\vdash \beta$

gelten. Dies bedeutet nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))

$\Gamma \vdash \alpha \rightarrow \beta$

und

$\Gamma \vdash \neg \alpha \rightarrow \beta ,$

woraus aufgrund der Fallunterscheidungsregel

$\Gamma \vdash \beta$

folgt. Dies würde aber bedeuten, dass ${}\Gamma$ widersprüchlich wäre.

Aufgabe (3 (2+1) Punkte)

Es sei ${}G$ eine Menge und ${}M\subseteq {\mathfrak {P}}\,(G)$ eine Teilmenge der Potenzmenge, die unter beliebigen Vereinigungen abgeschlossen ist.

1. Zeige, dass ${}(M,\subseteq )$ induktiv geordnet ist.
2. Zeige, dass ${}M$ ein größtes Element besitzt.

Lösung

1. Es sei ${}N\subseteq M$ eine Kette in ${}M$. Nach Voraussetzung gehört ${}\bigcup _{S\in N}S$ zu ${}M$ und offenbar gilt

   ${}T\subseteq \bigcup _{S\in N}S\,$

   für jedes ${}T$ aus ${}N$. Für die Kette gibt es also eine obere Schranke in ${}M$, sodass die Menge induktiv geordnet ist.

2. Die Menge

   $\bigcup _{S\in M}S$

   enthält jede Menge von ${}M$ und gehört zu ${}M$, sie ist somit das größte Element von ${}M$.

Aufgabe (1 Punkt)

Wir betrachten den Satz „Diese Vorlesung versteht keine Sau“. Negiere diesen Satz durch eine Existenzaussage.

Lösung

Es gibt eine Sau, die diese Vorlesung versteht.

Aufgabe (2 Punkte)

Zeige, dass der prädikatenlogische Ausdruck

$\exists x\exists y(\neg (x=y)\wedge \forall z((z=x)\vee (z=y)))$

erfüllbar ist.

Lösung

Es sei ${}M=\{m,n\}$ eine zweielementige Menge. Bei der Interpretation ${}I$ mit ${}I(x)=m$ und ${}I(y)=n$ ist ${}I(x)\neq I(y)$ und für alle ${}r\in M$ muss ${}r=m$ oder ${}r=n$ sein. Also gilt

$I\vDash \neg (x=y)$

und

$I\vDash \forall z((z=x)\vee (z=y))$

und damit

$I\vDash \neg (x=y)\wedge \forall z((z=x)\vee (z=y)).$

Also ist die Existenzaussage erfüllbar.

Aufgabe (4 Punkte)

Beweise den Satz über die Vorgängereigenschaft in einem Peano-Halbring.

Lösung

Beide Teilaussagen können wegen des ersten Peano-Axioms nicht zugleich wahr sein. Es geht also um die Aussage

$\forall x{\left({\left(x=0\right)}\vee {\left(\exists u{\left(x=u+1\right)}\right)}\right)},$

die wir durch Induktion beweisen. Der Induktionsanfang für ${}x=0$ ist durch den linken Bestandteil gesichert. Es sei also die Aussage für ein gewisses ${}x$ schon bewiesen, und sie ist für ${}x+1$ zu beweisen. Bei ${}x=0$ ist ${}x+1=0+1$, sodass man ${}u=0$ nehmen kann. Bei ${}x=u+1$ ist

${}x+1=(u+1)+1\,$

und somit kann man ${}u+1$ nehmen.

Aufgabe (3 Punkte)

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung ${}n+k=m+k$ die Gleichheit ${}n=m$ folgt (dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden).

Lösung

Wir führen Induktion über ${}k$ (für die Aussage für beliebige ${}n,m$). Für

${}k=0\,$

folgt die Aussage daraus, dass ${}0$ das neutrale Element der Addition ist. Die Aussage gelte nun für ein bestimmtes ${}k$. Wir müssen zeigen, dass sie auch für den Nachfolger ${}k'$ gilt. Es sei also

${}n+k'=m+k'\,.$

Aufgrund von Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (2) bedeutet dies

${}n'+k=m'+k\,,$

woraus nach Induktionsvoraussetzung

${}n'=m'\,$

folgt. Aufgrund der Injektivität der Nachfolgerabbildung ergibt sich

${}n=m\,.$

Aufgabe (3 (1+1+1) Punkte)

In einem Zugabteil sitzen die sechs Personen ${}A,B,C,D,E,F$. Wir betrachten die folgenden Relationen:

1. ${}Mx$ bedeutet, dass ${}x$ über die deutsche Bahn motzt.
2. ${}Px$ bedeutet, dass ${}x$ einen Fensterplatz hat.
3. ${}Sxy$ bedeutet, dass ${}x$ der Person ${}y$ die Fahrkarte klaut.

Es gelten ausschließlich die Beziehungen

$MA,MB,MC,MD,ME,MF,PA,PD,SAD,SBE,SFB.$

1. Charakterisiere umgangssprachlich die Person ${}A$ allein unter Bezugnahme auf die gegebenen Relationen.
2. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}M,P,S$ die Person ${}B$.
3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}M,P,S$ die Person ${}E$.

Lösung Zugabteil/Relationen/Elementare Äquivalenz/2/Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Zeige, dass die erststufige Peano-Arithmetik ${}PA$ eine vollständige widerspruchsfreie erststufige Erweiterung ${}M$, also ${}PA\subseteq M\subseteq L_{0}^{\rm {Ar}}$, besitzt, die von ${}\mathbb {N} _{0}^{\vDash }$ verschieden ist.

Lösung

Nach Korollar 21.13 (Einführung in die mathematische Logik (Osnabrück 2021)) liegt eine echte Erweiterung ${}PA\subset \mathbb {N} _{0}^{\vDash }$ vor. Es gibt somit Sätze ${}\alpha \in \mathbb {N} _{0}^{\vDash }$ mit ${}\alpha \notin PA$. Es ist ferner ${}\neg \alpha \notin PA$, da andernfalls ${}\mathbb {N} _{0}^{\vDash }$ widersprüchlich wäre. Es ist ${}PA\cup \{\neg \alpha \}$ widerspruchsfrei, da man sonst aus ${}PA$ den Satz ${}\alpha$ ableiten könnte, was wegen der Abgeschlossenheit unter Ableitungen und wegen ${}\alpha \notin PA$ nicht der Fall ist. Nach dem Vollständigkeitssatz gibt es somit ein Modell ${}M$ mit

${}PA\cup \{\neg \alpha \}\subseteq M_{0}^{\vDash }\,.$

Dabei ist ${}M_{0}^{\vDash }$ vollständig. Wegen ${}\neg \alpha \in M_{0}^{\vDash }$ und ${}\neg \alpha \notin \mathbb {N} _{0}^{\vDash }$ ist ${}M_{0}^{\vDash }\neq \mathbb {N} _{0}^{\vDash }$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (5 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Symmetrieaxiom genau dann gilt, wenn ${}R$ symmetrisch ist.

Lösung

Es sei ${}(M,R)$ gegeben. Es sei zunächst ${}R$ symmetrisch und sei

$w\vDash \alpha .$

Es sei eine von ${}w$ aus erreichbare Welt ${}v$ gegeben, also ${}wRv$. Wegen der Symmetrie ist auch ${}vRw$ und somit ist

$v\vDash \Diamond \alpha .$

Also ist

$w\vdash \Box \Diamond \alpha .$

Wenn ${}R$ hingegen nicht symmetrisch ist, so seien ${}w,v\in M$ Welten mit ${}wRv$, aber nicht ${}vRw$. Es sei ${}p$ eine Aussagenvariable und es sei ${}\mu$ die Belegung, bei der

$w\vDash p$

gelte und so, dass in allen von ${}v$ aus erreichbaren Welten ${}z\vDash \neg p$ gelte. Dann ist

$v\vDash \neg \Diamond p,$

und somit ist

$w\not \vDash \Box \Diamond p,$

also

$w\not \vDash p\rightarrow \Box \Diamond p.$

Aufgabe (4 Punkte)

Es sei ${}\Gamma$ die durch das Löb-Axiom gegebene ${}K$- Modallogik, also die Beweisbarkeitslogik. Wir setzen

${}\bot :=p\wedge \neg p\,$

(als Abkürzung für einen Widerspruch). Zeige, dass

$\Gamma \vdash \neg \Box \neg \Box \bot \leftrightarrow \neg \Box \bot$

ableitbar ist.

Lösung

Wegen Kontraposition genügt es,

$L\vdash \Box \neg \Box \bot \leftrightarrow \Box \bot$

zu zeigen, wobei wir die einzelnen Implikationen getrennt zeigen. Aus einem Widerspruch folgt Beliebiges, also

$\vdash \bot \rightarrow \neg \Box \bot .$

Nach Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1) folgt

$\vdash \Box \bot \rightarrow \Box \neg \Box \bot .$

Eine Instanz des Löb-Axioms ist

$L\vdash \Box (\Box \bot \rightarrow \bot )\rightarrow \Box \bot .$

Das Widerspruchsaxiom ergibt

$\vdash \neg \Box \bot \wedge \Box \bot \rightarrow \bot ,$

was wir als

$\vdash \neg \Box \bot \rightarrow (\Box \bot \rightarrow \bot )$

schreiben. Mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1) erhalten wir

$\vdash \Box \neg \Box \bot \rightarrow \Box (\Box \bot \rightarrow \bot ).$

Der Kettenschluss liefert

$L\vdash \Box \neg \Box \bot \rightarrow \Box \bot .$