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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Primzahlzwilling.
2. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
3. Eine maximal widerspruchsfreie Teilmenge ${}\Gamma \subseteq L^{V}$ zu einer Menge ${}V$ an Aussagenvariablen.
4. Die Interpretation der Terme zu einem Symbolalphabet ${}S$ in einer gegebenen ${}S$- Interpretation auf einer Grundmenge ${}M$.
5. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
6. Ein gerichteter Graph.

Lösung

1. Ein Primzahlzwilling ist ein Paar bestehend aus ${}p$ und ${}p+2$, wobei diese beiden Zahlen Primzahlen sind.
2. Unter einer Wahrheitsbelegung versteht man eine Abbildung

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

3. Die Teilmenge ${}\Gamma \subseteq L^{V}$ heißt maximal widerspruchsfrei, wenn ${}\Gamma$ widerspruchsfrei ist und jede echt größere Menge ${}\Gamma \subset \Gamma '$ widersprüchlich ist.
4. Die Terminterpretation ${}I(t)\in M$ wird induktiv über den Aufbau der Terme für jeden ${}S$- Term ${}t$ definiert.
   1. Für jede Konstante ${}c$ und jede Variable ${}x$ ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also ${}I(c)=c^{M}$ und ${}I(x)=x^{M}$.
   2. Wenn ${}t_{1},\ldots ,t_{n}$ Terme mit Interpretationen ${}I(t_{1}),\ldots ,I(t_{n})$ sind und wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist, so wird der Term ${}ft_{1}\ldots t_{n}$ als ${}f^{M}(I(t_{1}),\ldots ,I(t_{n}))$ interpretiert.
5. Man nennt ${}\alpha$ allgemeingültig, wenn er in jeder ${}S$- Interpretation ${}I$ gilt.
6. Ein gerichteter Graph ist eine Menge ${}M$ versehen mit einer fixierten Relation ${}R\subseteq M\times M$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Vollständigkeitssatz der Aussagenlogik.
3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Lösung

1. Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge mit der Eigenschaft, dass jede total geordnete Teilmenge ${}J\subseteq I$ eine obere Schranke in ${}I$ besitzt. Dann gibt es in ${}I$ maximale Elemente.
2. Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei ${}\alpha \in L^{V}$. Dann ist

   $\Gamma \vdash \alpha {\text{ genau dann, wenn }}\Gamma \vDash \alpha .$

3. Es sei ${}M$ eine Menge mit einem fixierten Element ${}s\in M$ und einer Abbildung ${}F\colon M\rightarrow M$. Dann gibt es genau eine Abbildung

   $\varphi \colon N\longrightarrow M,\,n\longmapsto \varphi (n),$

   die die beiden Eigenschaften

   $\varphi (0)=s{\text{ und }}\varphi (n^{\prime })=F(\varphi (n)){\text{ für alle }}n\in \mathbb {N}$

   erfüllt.

Aufgabe (1 Punkt)

Negiere die Aussage „Martina findet alle Jungs im Kurs außer Markus zuckersüß“ durch eine Aussage, in der eine Existenzaussage und eine Oder-Verknüpfung vorkommen.

Lösung

Martina findet Markus zuckersüß oder es gibt im Kurs einen von Markus verschiedenen Jungen, den sie nicht zuckersüß findet.

Aufgabe (7 Punkte)

Beweise den Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen im abzählbaren Fall.

Lösung

Es sei ${}p_{n}$, ${}n\in \mathbb {N} _{+}$, eine (surjektive, aber nicht notwendigerweise injektive) Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass ${}\Gamma _{0}:=\Gamma ^{\vdash }$ keinen Widerspruch enthält. Wir konstruieren eine (endliche oder abzählbar unendliche) Folge von aufsteigenden widerspruchsfreien Teilmengen ${}\Gamma _{n}\subseteq \Gamma _{n+1}$, wobei in ${}\Gamma _{n}$ für jede Variable ${}p_{i}$, ${}1\leq i\leq n$, die Alternative entweder ${}p_{i}\in \Gamma _{n}$ oder${}\neg p_{i}\in \Gamma _{n}$ gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über ${}n\in \mathbb {N}$. Für ${}\Gamma _{0}$ ist dies richtig. Es sei ${}\Gamma _{n}$ schon konstruiert. Bei ${}p_{n+1}\in \Gamma _{n}$ oder ${}\neg p_{n+1}\in \Gamma _{n}$ setzen wir

${}\Gamma _{n+1}:=\Gamma _{n}\,.$

Wegen der Widerspruchsfreiheit von ${}\Gamma _{n}$ können nicht sowohl ${}p_{n+1}$ als auch ${}\neg p_{n+1}$ zu ${}\Gamma _{n}$ gehören. Wenn weder ${}p_{n+1}$ noch ${}\neg p_{n+1}$ zu ${}\Gamma _{n}$ gehören, so setzen wir

${}\Gamma _{n+1}:={\left(\Gamma _{n}\cup {p_{n+1}}\right)}^{\vdash }\,$

(man könnte genauso gut ${}\neg p_{n+1}$ hinzunehmen). Nach Konstruktion ist ${}\Gamma _{n+1}$ abgeschlossen unter der Ableitungsbeziehung und erfüllt die (Oder)-Alternative für alle Variablen ${}p_{i}$, ${}i\leq n+1$. Wenn ${}\Gamma _{n+1}$ widersprüchlich wäre, so gelte insbesondere ${}\Gamma _{n}\cup \{p_{n+1}\}\vdash \neg p_{n+1}$. Dann würde aber auch ${}\Gamma _{n}\vdash p_{n+1}\rightarrow \neg p_{n+1}$ gelten und somit nach der Fallunterscheidungsregel auch ${}\Gamma _{n}\vdash \neg p_{n+1}$, also ${}\neg p_{n+1}\in \Gamma _{n}$ im Widerspruch zu dem Fall, in dem wir uns befinden. Daher liegt für die Aussagenvariablen auch die Entweder-Oder-Alternative vor.

Mit dieser induktiven Definition setzen wir

${}\Gamma ':=\bigcup _{n\in \mathbb {N} }\Gamma _{n}\,.$

Diese Menge ${}\Gamma '$ ist widerspruchsfrei, da andernfalls schon eines der ${}\Gamma _{n}$ einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen ${}\Gamma _{n}$ gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes ${}n\in \mathbb {N}$ die Alternative ${}p_{n}\in \Gamma '$ oder ${}\neg p_{n}\in \Gamma '$. Damit sind die Voraussetzungen von Lemma 4.7 (Einführung in die mathematische Logik (Osnabrück 2021)) erfüllt und ${}\Gamma '$ ist maximal widerspruchsfrei.

Aufgabe (7 (1+1+2+3) Punkte)

Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an.

1. Die ${}n$-te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
2. Die ${}n$-te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
3. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt.
4. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?

Lösung

1. Wenn die Generation nur aus dem Geschlecht ${}X$ besteht, so sind nur Paarungen innerhalb dieses Geschlechts möglich und das Ergebnis gehört stets diesem Geschlecht an. Mit Induktion folgt, dass dies über alle folgenden Generationen so bleibt.
2. Die Generation bestehe aus einem Individuum des Geschlechts ${}X$ und aus einem Individuum des Geschlechts ${}Y\neq X$. Die Folgegeneration besteht dann ausschließlich aus dem dritten Geschlecht ${}Z$ und nach Teil (1) überträgt sich das auf alle folgenden Generationen.
3. Wenn es nur ein oder kein Individuum gibt, so ist keine Paarung möglich und die nächste Generation ist leer. Wenn es zwei Individuen gibt, so ist nur eine Paarung möglich und es gibt nur einen Nachkommen, der sich allein nicht fortpflanzen kann. Wenn es dagegen mindestens drei Individuen, egal welchen Geschlechts, gibt, so sind auch mindestens drei Paarungen möglich und die nächste Generation besitzt mindestens wieder drei Individuen.
4. Wenn drei gleichgeschlechtliche Individuen in einer Generation leben, so erzeugen die drei möglichen Paare stets wieder ebendieses Geschlecht. Die Möglichkeiten sind ${}A,A,A$ oder ${}B,B,B$ oder ${}C,C,C$ und die Periodenlänge ist ${}1$. Wenn drei unterschiedliche Geschlechter vertreten sind, so ist jedes Geschlecht durch genau ein Individuum vertreten, es liegt also ${}A,B,C$ vor. Die drei Paarungen führen dann wieder zu ${}A,B,C$ und die Periodenlänge ist ebenfalls ${}1$. Wenn ein Geschlecht durch zwei Individuen vertreten ist und ein zweites Geschlecht durch ein Individuum, sagen wir ${}X,X,Y$, so wird daraus ${}X,Z,Z$ und daraus ${}Y,Y,Z$ und daraus ${}X,X,Y$. Die Periodenlänge ist also ${}3$. Von diesem Typ gibt es zwei Generationsabfolgen, nämlich die mit ${}A,A,B$ (mit $A,C,C$ und $B,B,C$) und die mit ${}A,B,B$ (mit $B,C,C$ und $A,A,C$).

Aufgabe (2 Punkte)

Es seien ${}p,q$ verschiedene Aussagenvariablen. Begründe die (Un)Richtigkeit der beiden folgenden Aussagen.

1. ${}\vdash p$ genau dann, wenn ${}\vdash q$.
2. ${}\vdash p\leftrightarrow q$.

Lösung

1. Da ${}\vdash p$ ebensowenig wie ${}\vdash q$ gilt, ist die Äquivalenz der beiden Ableitungen gegeben.
2. Der Ausdruck ${}p\leftrightarrow q$ ist nicht ableitbar, da er keine semantische Tautologie ist, wie man sieht, wenn man ${}p$ mit ${}1$ und ${}q$ mit ${}0$ belegt.

Aufgabe (4 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme. Zeige, dass für jeden ${}S$-Satz ${}\alpha \in L_{0}^{S}$ die Gleichheit

${}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=\alpha \,$

gilt.

Lösung

Für Sätze ${}\alpha \in L_{0}^{S}$ gibt es mi rekursiven Aufbau grundsätzlich zwei Möglichkeiten. Entweder sind sie von der Form ${}\forall x\beta$ oder ${}\exists x\beta$, wobei in ${}\alpha$ höchstens die Variable ${}x$ frei vorkommt, oder sie entstehen durch aussagenlogische Verknüpfungen aus Sätzen.

Im ersten Fall ergibt sich aus der Voraussetzung ${}\alpha =\forall x\beta \in L_{0}^{S}$, dass in ${}\alpha$ keine Variable frei vorkommt. Somit ist die relevante Variablenmenge und entsprechend die relevante Termmenge leer. Daher ist als „Hilfsvariable“

${}v=x\,$

zu wählen, und es ist

${}(\forall x\beta ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=\forall x(\beta {\frac {x}{x}})=\forall x\beta \,.$

Bei aussagenlogisch zusammengesetzten Sätzen ergibt sich die Behauptung unmittelbar.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (5 Punkte)

Beweise den Satz über die Division mit Rest in einem Peano-Halbring.

Lösung

Wir betrachten zum Nachweis der Existenz die erststufige Aussage

$\forall d{\left(d\geq 1\rightarrow \exists q\exists r{\left(m=dq+r\wedge r\leq d\wedge \neg r=d\right)}\right)},$

die ${}m$ als einzige freie Variable besitzt. Für ${}m=0$ ist die Aussage mit ${}q=0$ und

${}r=0\,$

richtig. Zum Beweis des Induktionsschritts sei

${}m=dq+r\,$

mit den angegebenen Eigenschaften. Daher ist

${}m+1=dq+r+1\,.$

Wenn ${}r'=r+1$ kleiner als ${}d$ ist, so erfüllen ${}q,r'$ die geforderten Eigenschaften. Bei ${}r+1\geq d$ muss ${}r+1=d$ nach Aufgabe 12.23 (Einführung in die mathematische Logik (Osnabrück 2021)) gelten. Dann ist

${}m+1=dq+r+1=dq+d=d(q+1)\,,$

sodass ${}q+1$ und ${}0$ das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe 13.22 (Einführung in die mathematische Logik (Osnabrück 2021)).

Aufgabe (5 (3+2) Punkte)

Es sei ${}S$ ein Symbolalphabet ohne Funktionssymbole und sei ${}M$ eine endliche ${}S$- Struktur.

1. Charakterisiere die Automorphismengruppe von ${}M$ mit Hilfe der elementaren Äquivalenzklassen.
2. Beweise Satz 17.6 (Einführung in die mathematische Logik (Osnabrück 2021)) in diesem Fall.

Lösung

1. Es seien ${}M_{1},\ldots ,M_{k}\subseteq M$ die elementaren Äquivalenzklassen. Ein Automorphismus muss bijektiv sein und ein Element aus ${}M_{j}$ nach Satz 16.7 (Einführung in die mathematische Logik (Osnabrück 2021)) auf ein Element aus ${}M_{j}$ abbilden. Wir behaupten, dass jede bijektive Abbildung, die diese Bedingung erfüllt, bereits ein Automorphismus ist, also

   ${}\operatorname {Aut} \,M=\operatorname {Perm} \,(M_{1})\times \cdots \times \operatorname {Perm} \,(M_{k})\,.$

   Eine Abbildung aus der Menge rechts führt aber Konstanten in sich und erhält nach Lemma 16.14 (Einführung in die mathematische Logik (Osnabrück 2021)) die Relationen. Da es keine Funktionssymbole gibt, handelt es sich bereits um einen Isomorphismus.

2. Es seien ${}M$ und ${}N$ zueinander elementar äquivalent und seien ${}M_{1},\ldots ,M_{k}\subseteq M$ die elementare Äquivalenzklassen von ${}M$. Diese werden nach Lemma 16.11 (Einführung in die mathematische Logik (Osnabrück 2021)) durch Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{k}$ in einer freien Variablen charakterisiert. Mit Hilfe von ${}\exists x\alpha _{j}$ ergibt sich, dass es in ${}N$ die entsprechenden Äquivalenzklassen ${}N_{1},\ldots ,N_{k}\subseteq N$ gibt. Die Argumente aus Teil (1) zeigen, dass jede Bijektion, die jedes ${}M_{j}$ in das zugehörige ${}N_{j}$ überführt, bereits ein Isomorphismus ist.

Aufgabe (3 Punkte)

Erstelle ein Programm für eine Registermaschine, das abwechselnd ${}1$ und ${}0$ ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Druckbefehl verwendet.

Lösung

Der Register ${}R_{1}$ sei zu Beginn leer.

$1.\,\,1+$

$2.\,\,{\text{Drucke}}$

$3.\,\,C(1,1)$

$4.\,\,1-$

$5.\,\,C(1,2)$

$6.\,\,{\text{ Halte an}}$

Am Anfang wird ${}1$ ausgedruckt. Wenn im Befehl 2 eine ${}1$ ausgedruckt wird, so steht im ersten Register eine ${}1$ und im Befehl 3 wird nicht auf Befehl 1 umgeleitet, sondern nach Befehl 4 weitergeleitet. Danach steht im ersten Register eine ${}0$ und Befehl 5 leitet nach Befehl 2 um, wo die ${}0$ gedruckt wird. Wenn im Befehl 2 eine ${}0$ ausgedruckt wird, so steht im ersten Register eine ${}0$ und im Befehl 3 wird auf Befehl 1 umgeleitet. Dort wird der erste Register auf ${}1$ erhöht und dies wird im Befehl 2 ausgedruckt.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Es sei ${}M$ eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von ${}M$ in die Potenzmenge ${}{\mathfrak {P}}\,(M)$ geben kann.

Lösung

Wir nehmen an, dass es eine surjektive Abbildung

$F\colon M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto F(x),$

gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir

${}T={\left\{x\in M\mid x\notin F(x)\right\}}\,.$

Da dies eine Teilmenge von ${}M$ ist, muss es wegen der Surjektivität ein ${}y\in M$ geben mit

${}F(y)=T\,.$

Es gibt nun zwei Fälle, nämlich ${}y\in F(y)$ oder ${}y\not \in F(y)$. Im ersten Fall ist also ${}y\in T$, und damit, nach der Definition von ${}T$, auch ${}y\notin F(y)$, Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von ${}T$, ${}y\in T$, und das ist ebenfalls ein Widerspruch.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Möglichkeitsaxiom genau dann gilt, wenn in ${}M$ jeder Punkt einen Nachfolger besitzt.

Lösung

Es sei ${}(M,R)$ gegeben. Es sei zunächst vorausgesetzt, dass in ${}R$ jedes Element einen Nachfolger besitzt und sei

$w\vDash \Box \alpha$

für eine Welt ${}w\in M$. Es sei ${}v\in M$ mit ${}wRv$. Dann ist

$v\vDash \alpha$

und somit

$w\vDash \Diamond \alpha ,$

also

$w\vDash \Box \alpha \rightarrow \Diamond \alpha .$

Es sei umgekehrt angenommen, dass ${}M$ eine Sackgassenwelt ${}w$ besitzt. Dann ist für eine beliebige Aussagenvariable ${}p$

$w\vDash \Box p,$

aber

$w\not \vDash \Diamond p,$

und das Möglichkeitsaxiom kann nicht gelten.