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

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

Aufgabe (3 Punkte)

Lösung

1. Unter einer Wahrheitsbelegung versteht man eine Abbildung

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

2. Eine geordnete Menge ${}(I,\preccurlyeq )$ heißt induktiv geordnet, wenn jede total geordnete Teilmenge ${}J\subseteq I$ eine obere Schranke in ${}I$ besitzt.
3. Das Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.
   1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
   2. Zu jeder natürlichen Zahl ${}n\in \mathbb {N} _{+}$ eine Menge ${}R_{n}$ von ${}n$-stelligen Relationssymbolen.
   3. Die aussagenlogischen Junktoren

      $\neg ,\,\wedge ,\,\vee ,\,\rightarrow ,\,\leftrightarrow .$

   4. Das Gleichheitszeichen ${}=$.
   5. Die Quantoren ${}\forall$ und ${}\exists$.
   6. Klammern, also ${}($ und ${})$.
4. Man sagt, dass ${}\Gamma$ Beispiele enthält, wenn es für jeden Ausdruck der Form ${}\exists x\alpha$ aus ${}L^{S}$ einen ${}S$- Term ${}t$ derart gibt, dass

   $\exists x\alpha \rightarrow \alpha {\frac {t}{x}}$

   zu ${}\Gamma$ gehört.

5. Die Addition ${}n+k$ wird über die Addition ${}\alpha _{n}$ mit festem ${}n$ definiert, wobei ${}\alpha _{n}$ die eindeutig bestimmte Abbildung

   $\alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),$

   ist, für die

   $\alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N}$

   gilt.

6. Es sei ${}\Gamma$ eine Menge von modallogischen Ausdrücken und ${}\alpha$ ein modallogischer Ausdruck. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, wenn für jedes modallogische Modell ${}(M,R,\mu )$ mit

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

   auch

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

   gilt.

Aufgabe (3 Punkte)

Lösung

1. In einem Peano-Halbring ${}M$ gilt für jeden Ausdruck ${}\alpha \in L^{\{0,1,+,\cdot \}}$ in der freien Variablen ${}x$ die Aussage

   $\exists x\alpha \rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}.$

2. Es seien ${}M$ und ${}N$ isomorphe ${}S$- Strukturen über einem Symbolalphabet ${}S$. Dann sind ${}M$ und ${}N$ elementar äquivalent.
3. /Fakt

Aufgabe (3 Punkte)

In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit ${}V$ (vordere Tafel), ${}M$ (mittlere Tafel) und ${}H$ (hintere Tafel) bezeichnet. Aufgrund der Höhe des Gestells sind nur (maximal) zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge (alle Möglichkeiten!) muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll.

Lösung

Die Tafeln ${}M$ und ${}H$ sind nicht gleichzeitig sichtbar, da (mindestens) eine davon durch ${}V$ verdeckt wird. Dagegen sind sowohl ${}V$ und ${}H$ (${}M$ wird hinter ${}V$ geschoben) als auch ${}V$ und ${}M$ gleichzeitig einsehbar. Eine Beschreibungsreihenfolge erfüllt also genau dann die angegebene Bedingung, wenn ${}M$ und ${}H$ nicht direkt hintereinander beschrieben werden. Dies wird genau dann erreicht, wenn ${}V$ als zweite Tafel beschrieben wird. Erlaubt sind also die beiden Reihenfolgen ${}M-V-H$ und ${}H-V-M$.

Aufgabe (3 Punkte)

Bei einem Zwei-Personen-Regel-Spiel (wie Schach) spielen zwei Personen (${}A$ und ${}B$) nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für ${}A$ ist, da ist ${}A$ am Zug und kann ${}B$ schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge ${}S$ aller Stellungen eine Gewinnstellung für ${}A$ (mit ${}A$ am Zug) ist.

Lösung

Wir definieren

${}G_{0}={\text{jede Mattstellung für }}A\,$

und rekursiv

${}G_{n}:={\left\{s\in S\mid {\text{ es gibt einen Zug für }}A{\text{ derart, dass für alle Züge von }}B{\text{ die entstehende Stellung zu }}G_{n-1}{\text{ gehört}}\right\}}\,.$

Eine Gewinnstellung ist dann

${}G=\bigcup _{n\in \mathbb {N} }G_{n}\,.$

Aufgabe (2 Punkte)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}r$ ${}?$ w w w f w w f f w f w w w f f f f w w f f w f f f f w w f f f w

Lösung

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

Aufgabe (4 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Zeige

${}\Gamma ^{\vdash }={\left(\Gamma ^{\vdash }\right)}^{\vdash }\,.$

Lösung

Die Inklusion

${}\Gamma ^{\vdash }\subseteq {\left(\Gamma ^{\vdash }\right)}^{\vdash }\,$

ist wegen ${}\vdash \alpha \rightarrow \alpha$ klar. Es sei also ${}{\left(\alpha \in \Gamma ^{\vdash }\right)}^{\vdash }$. Dies bedeutet, dass es Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma ^{\vdash }$ mit

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

gibt. Für die einzelnen ${}\alpha _{i}$ gibt es ${}\beta _{i1},\ldots ,\beta _{ik_{i}}\in \Gamma$ mit

$\vdash \beta _{i1}\wedge \ldots \wedge \beta _{ik_{i}}\rightarrow \alpha _{i}$

für jedes ${}i$. Daraus ergibt sich mit Hilfe (der Regelversion) von Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021))  (2)

$\vdash \beta _{11}\wedge \ldots \wedge \beta _{1k_{1}}\wedge \beta _{21}\wedge \ldots \wedge \beta _{2k_{2}}\wedge \ldots \wedge \beta _{n1}\wedge \ldots \wedge \beta _{nk_{n}}\rightarrow \alpha _{1}\wedge \ldots \wedge \alpha _{n}.$

Mit der Kettenschlussregel ergibt sich daraus

$\vdash \beta _{11}\wedge \ldots \wedge \beta _{1k_{1}}\wedge \beta _{21}\wedge \ldots \wedge \beta _{2k_{2}}\wedge \ldots \wedge \beta _{n1}\wedge \ldots \wedge \beta _{nk_{n}}\rightarrow \alpha ,$

was ${}\alpha \in \Gamma ^{\vdash }$ bedeutet.

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 (3 Punkte)

Es seien ${}x_{1},x_{2}$ Variablen, ${}t_{1},t_{2}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Zeige, dass

${\left(\alpha {\frac {t_{1}}{x_{1}}}\right)}{\frac {t_{2}}{x_{2}}}\rightarrow \alpha {\frac {t_{1},t_{2}}{x_{1},x_{2}}}$

im Allgemeinen nicht allgemeingültig ist.

Lösung

Für ${}\alpha$ betrachten wir den Ausdruck ${}x_{1}=x_{2}$ und wir setzen ${}t_{1}:=x_{2}$ und ${}t_{2}:=x_{1}$. Dann ist einerseits (wir schreiben ${}\equiv$ für die Gleichheit von Ausdrücken)

${}{\begin{aligned}{\left(\alpha {\frac {t_{1}}{x_{1}}}\right)}{\frac {t_{2}}{x_{2}}}&\equiv {\left((x_{1}=x_{2}){\frac {x_{2}}{x_{1}}}\right)}{\frac {x_{1}}{x_{2}}}\\&\equiv {\left(x_{2}=x_{2}\right)}{\frac {x_{1}}{x_{2}}}\\&\equiv x_{1}=x_{1},\end{aligned}}$

was allgemeingültig ist, und andererseits

${}{\begin{aligned}\alpha {\frac {t_{1},t_{2}}{x_{1},x_{2}}}&\equiv (x_{1}=x_{2}){\frac {x_{2},x_{1}}{x_{1},x_{2}}}\\&\equiv (x_{1}{\frac {x_{2},x_{1}}{x_{1},x_{2}}}=x_{2}{\frac {x_{2},x_{1}}{x_{1},x_{2}}})\\&\equiv x_{2}=x_{1},\end{aligned}}$

was nicht allgemeingültig ist. Somit ist

$x_{1}=x_{1}\rightarrow x_{2}=x_{1}$

nicht allgemeingültig.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 (0.5+0.5+0.5+0.5) Punkte)

Wir zählen

${\text{ ich}},\,{\text{ Mama}},\,{\text{ Oma}},\,{\text{Uroma}},\,{\text{Ururoma}},\ldots .$

1. Was ist die Mama der Urururoma?
2. Was ist die Uroma der Uroma?
3. Was ist die Oma der Oma der Oma?
4. Was ist die Ururoma der Uroma?

Lösung

1. Ururururoma.
2. Ururururoma.
3. Ururururoma.
4. Urururururoma.

Aufgabe (8 Punkte)

Beweise das Wohlordnungsprinzip für erststufige Aussagen für Peano-Halbringe.

Lösung

Wir betrachten den Ausdruck

$\forall u{\left(\exists x{\left(\alpha \wedge x\leq u\right)}\rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}\right)}$

und wollen zeigen, dass er in jedem Peano-Halbring gilt. Dies zeigen wir unter Verwendung des Induktionsaxioms und fixieren einen Peano-Halbring ${}M$. Für ${}u=0$ ist die Aussage richtig, da dann, falls der Vordersatz ${}\exists x{\left(\alpha \wedge x\leq 0\right)}$ gilt, dann insbesondere ${}\alpha {\frac {0}{x}}$ in ${}M$ gilt und man im Nachsatz

${}y=0\,$

nehmen kann, da ja ${}0$ das kleinste Element ist. Zum Beweis des Induktionsschrittes müssen wir die Gültigkeit von

$\forall u{\left({\left(\exists x{\left(\alpha \wedge x\leq u\right)}\rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow y\leq x\right)}\right)}\right)}\rightarrow {\left(\exists x{\left(\alpha \wedge x\leq u+1\right)}\rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}\right)}\right)}$

zeigen. Es sei also die Aussage für ein bestimmtes ${}u\in M$ (also der Vordersatz links) im Modell wahr. Wir müssen dann den Nachsatz, also die Aussage für ${}u+1$ als wahr erweisen. Es gelte also

$\exists x{\left(\alpha \wedge x\leq u+1\right)}.$

Wenn sogar ${}\exists x{\left(\alpha \wedge x\leq u\right)}$ gilt, so sind wir nach Induktionsvoraussetzung fertig. Es gelte diese Aussage also nicht. Das bedeutet einerseits, dass der Ausdruck ${}\alpha$ für kein Element aus ${}M$ gilt, das kleiner als oder gleich ${}u$ ist, und andererseits, dass ${}\alpha$ gilt, wenn ${}x$ durch ${}u+1$ interpretiert wird. Somit gilt der Ausdruck

$\alpha {\frac {u+1}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq u+1\right)}$

und damit

$\exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (11 (2+2+4+1+2) Punkte)

Wir betrachten die Identität

$\operatorname {Id} \colon \mathbb {N} \longrightarrow \mathbb {N}$

und den Ausdruck ${}x=y$, den wir mit ${}\psi$ bezeichnen. Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ die Ausdrucksmenge, die die Kommutativität und die Assoziativität der Addition besagt sowie, dass ${}0$ das neutrale Element der Addition ist.

1. Zeige, dass der Graph der Identität durch ${}\psi$ schwach repräsentierbar in ${}\Gamma$ ist.
2. Zeige, dass der Graph der Identität nicht repräsentierbar in ${}\Gamma$ ist.
3. Zeige, dass der Graph der Identität repräsentierbar in der Peano-Arithmetik ${}{\rm {PA}}$ ist.
4. Ist die Identität als Abbildung repräsentierbar in der Peano-Arithmetik?
5. Gilt

   $\Gamma \vdash \exists !y\psi (n,y)$

   für jedes ${}n\in \mathbb {N}$ (dabei werde ${}n$ durch eine ${}n$-fache Summe der ${}1$ mit sich in beliebiger Klammerung wiedergegeben)?

Lösung

1. Wenn eine Gleichheit

   ${}m=n\,$

   von natürlichen Zahlen vorliegt, so wird diese eine Zahl durch den einen Term ${}1+\cdots +1$ in ${}L^{\rm {Ar}}$ dargestellt. Wegen Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt

   $\Gamma \vdash n=n.$

   Wenn hingegen ${}m$ und ${}n$ verschiedene natürliche Zahlen sind, so ist die Gleichheit ${}m=n$ nicht aus ${}\Gamma$ ableitbar, da andernfalls wegen ${}\Gamma \subseteq \mathbb {N} ^{\vDash }$ die Gleichheit auch in ${}\mathbb {N}$ gelten würde.

2. Seien

   ${}m\neq n\,$

   verschiedene natürliche Zahlen. Wir behaupten

   $\Gamma \not \vdash m\neq n.$

   Wäre das nämlich doch ableitbar, so müsste diese Ungleichheit in jedem Modell von ${}\Gamma$ gelten. Die Gültigkeit von ${}\Gamma$ in einem Modell bedeutet aber lediglich, dass ein kommutatives Monoid vorliegt. Da es auch das triviale Monoid ${}\{0\}$ gibt, in dem alle Elemente gleich sind, erhalten wir einen Widerspruch.

3. Bei gleichen Zahlen folgt die Ableitbarkeit nach Teil (1) sogar aus ${}\Gamma$, also erst recht aus der Peano-Arithmetik. Es seien also

   ${}m\neq n\,$

   verschiedene natürliche Zahlen. Es ist

   ${\rm {PA}}\vdash \neg (m=n)$

   zu zeigen. Wegen der (ableitbaren) Symmetrie des Gleichheitszeichens können wir

   ${}m>n\,$

   annehmen. Es sei

   ${}m=k+n\,$

   mit ${}k\in \mathbb {N} _{+}$. Nach Axiom 12.11 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) ist

   ${\rm {PA}}\vdash \neg (k=0).$

   Die Kontraposition zu Axiom 12.11 (Einführung in die mathematische Logik (Osnabrück 2021))   (2) liefert der Reihe nach

   ${\rm {PA}}\vdash \neg (k+1=1),$

   ${\rm {PA}}\vdash \neg (k+2=2),\ldots$

   bis man schließlich bei

   ${\rm {PA}}\vdash \neg (k+n=n)$

   anlangt.

4. Die folgt aus Teil (5).
5. Das gilt, es ist

   $\Gamma \vdash n=y\wedge n=z\rightarrow y=z$

   für jedes ${}n\in \mathbb {N}$ zu zeigen. Dies ergibt sich aber einfach aus der (ableitbaren) Symmetrie und der Transitivität des Gleichheitszeichens.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung