Kurs:Einführung in die mathematische Logik/16/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	4	0	22	5	3	3	0	0	3	10	0	0	0	0	0	56

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.
2. Ein Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.
3. Die Variablensubstitution ${}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ für einen ${}S$-Ausdruck ${}\alpha$, wobei ${}x_{1},\ldots ,x_{k}$ Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme seien.
4. Die Ableitbarkeit eines Ausdrucks ${}\alpha \in L^{S}$ im prädikatenlogischen Kalkül.
5. Die Arithmetische Repräsentierbarkeit einer Abbildung

   $F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}.$

6. Eine (formale) Modallogik.

Lösung

1. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
   1. Wenn ${}t_{1}$ und ${}t_{2}$ Terme sind, so ist

      $t_{1}=t_{2}$

      ein Ausdruck.
   2. Wenn ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind, so ist

      $Rt_{1}{\ldots }t_{n}$

      ein Ausdruck.

   3. Wenn ${}\alpha$ und ${}\beta$ Ausdrücke sind, so sind auch

      $\neg {\left(\alpha \right)},\,{\left(\alpha \right)}\wedge {\left(\beta \right)},\,{\left(\alpha \right)}\vee {\left(\beta \right)},\,{\left(\alpha \right)}\rightarrow {\left(\beta \right)},\,{\left(\alpha \right)}\leftrightarrow {\left(\beta \right)}$

      Ausdrücke.

   4. Wenn ${}\alpha$ ein Ausdruck ist und ${}x$ eine Variable, so sind auch

      $\forall x{\left(\alpha \right)}\,\,{\text{ und }}\,\,\exists x{\left(\alpha \right)}$

      Ausdrücke.

2. Ein Ideal ist eine nichtleere Teilmenge ${}{\mathfrak {a}}\subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
   1. Für alle ${}a,b\in {\mathfrak {a}}$ ist auch ${}a+b\in {\mathfrak {a}}$.
   2. Für alle ${}a\in {\mathfrak {a}}$ und ${}r\in R$ ist auch ${}ra\in {\mathfrak {a}}$.
3. Die Variablensubstitution definiert man rekursiv über den Aufbau der ${}S$- Ausdrücke.
   1. Für Terme ${}s_{1},s_{2}$ setzt man

      $(s_{1}=s_{2}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.$

   2. Für ein ${}n$-stelliges Relationssymbol ${}R$ und ${}n$ Terme ${}s_{1},\ldots ,s_{n}$ setzt man

      $(Rs_{1}\ldots s_{n}){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=Rs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.$

   3. Für einen Ausdruck ${}\alpha$ setzt man

      $(\neg \alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\neg \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}.$

   4. Für Ausdrücke ${}\alpha$ und ${}\beta$ setzt man

      $(\alpha \wedge \beta ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\wedge \beta {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$

      und ebenso für die anderen zweistelligen Junktoren.

   5. Für einen Ausdruck ${}\alpha$ seien ${}x_{i_{1}},\ldots ,x_{i_{r}}$ diejenigen Variablen (unter den $x_{1},\ldots ,x_{k}$), die in ${}\forall x\alpha$ frei vorkommen. Es sei ${}v=x$, falls ${}x$ nicht in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Andernfalls sei ${}v$ die erste Variable (in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge), die weder in ${}\alpha$ noch in ${}t_{i_{1}},\ldots ,t_{i_{r}}$ vorkommt. Dann setzt man

      $(\forall x\alpha ){\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=\forall v\alpha {\frac {t_{i_{1}},\ldots ,t_{i_{r}},v}{x_{i_{1}},\ldots ,x_{i_{r}},x}}$

      und ebenso für den Existenzquantor.

4. Der Ausdruck ${}\alpha$ heißt ableitbar, wenn er sich aus den Grundtautologien, also
   • den aussagenlogischen syntaktischen Tautologien,
   • den Gleichheitsaxiomen,
   • der Existenzeinführung im Sukzedens,

   durch sukzessive Anwendung der Ableitungsregeln Modus ponens und der Existenzeinführung im Antezedens erhalten lässt.

5. Die Abbildung ${}F$ heißt arithmetisch repräsentierbar, wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die Äquivalenz ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r+s})$ gilt.
6. Eine unter aussagenlogischen Ableitungen abgeschlossene Teilmenge der modallogischen Sprache heißt (formale) Modallogik.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Endlichkeitssatz für die Prädikatenlogik.
3. Das Unvollständigkeitslemma.

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 ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$-Ausdrücken und ${}\alpha$ ein weiterer ${}S$-Ausdruck. Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn es eine endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ gibt mit ${}\Gamma _{e}\vDash \alpha$.
3. Es sei ${}\Gamma$ eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge ${}\Gamma ^{\vdash }$ (also die Menge der zugehörigen Gödelnummern) sei schwach repräsentierbar in ${}\Gamma$. Dann gibt es einen arithmetischen Satz ${}q\in L_{0}^{\rm {Ar}}$ derart, dass weder ${}q$ noch seine Negation ${}\neg q$ aus ${}\Gamma$ ableitbar ist.

Aufgabe (4 (1+3) Punkte)

In einer Höhle befinden sich im Innern am Ende des Ganges vier Personen. Sie haben eine Taschenlampe bei sich und der Gang kann nur mit der Taschenlampe begangen werden. Dabei können höchstens zwei Leute gemeinsam durch den Gang gehen. Die Personen sind unterschiedlich geschickt, die erste Person benötigt eine Stunde, die zweite Person benötigt zwei Stunden, die dritte Person benötigt vier Stunden und die vierte Person benötigt fünf Stunden, um den Gang zu durchlaufen. Wenn zwei Personen gleichzeitig gehen, entscheidet die langsamere Person über die Geschwindigkeit.

1. Die Batterie für die Taschenlampe reicht für genau ${}13$ Stunden. Können alle vier die Höhle verlassen?
2. Die Batterie für die Taschenlampe reicht für genau ${}12$ Stunden. Können alle vier die Höhle verlassen?

Lösung Höhle/Taschenlampe/Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe weiter

Es sei ${}V$ eine (nichtleere) Aussagenvariablenmenge und

${}\operatorname {Bel} \,{\left(V\right)}=\operatorname {Abb} \,{\left(V,\{0,1\}\right)}\,$

die Menge aller Wahrheitsbelegungen auf ${}V$. In dieser Aufgabe untersuchen wir ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ und die Abbildung

$\Psi \colon L^{V}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)},\,\alpha \longmapsto {\left(\lambda \mapsto I^{\lambda }(\alpha )\right)}.$

Dabei spielen die beiden folgenden Teilmengen eine Rolle.

Es sei ${}N\subseteq \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ die folgendermaßen festgelegte Teilmenge. Eine Abbildung ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ gehört genau dann zu ${}N$, wenn es eine endliche Teilmenge ${}W\subseteq V$ derart gibt, dass ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ ist (dies ist in Aufgabenteil 2 zu erläutern).

Es sei ${}M\subseteq \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ die durch die folgenden Bedingungen rekursiv festgelegte Teilmenge.

a) Zu ${}p\in V$ gehört

$\operatorname {ev} _{p}\colon \operatorname {Bel} \,{\left(V\right)}\longrightarrow \{0,1\},\,\lambda \longmapsto \lambda (p),$

zu ${}M$.

b) Wenn ${}\varphi \in M$ ist, so gehört auch ${}\tau \circ \varphi$ zu ${}M$, wobei ${}\tau \colon \{0,1\}\rightarrow \{0,1\}$ die Vertauschungsabbildung bezeichnet.

c) Wenn ${}\varphi ,\theta \in M$ sind, so gehören auch ${}{\min {\left(\varphi ,\theta \right)}}$ und ${}{\max {\left(\varphi ,\theta \right)}}$ zu ${}M$.

1. Ist ${}\Psi$ injektiv?
2. Es sei ${}W\subseteq V$ eine Teilmenge. Zeige, dass es eine natürliche surjektive Abbildung

   $\operatorname {Bel} \,{\left(V\right)}\longrightarrow \operatorname {Bel} \,{\left(W\right)}$

   und eine natürliche injektive Abbildung

   $\Phi _{W}\colon \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$

3. Zeige, dass die in (2) beschriebene Abbildung

   $\Phi _{W}\colon \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$

   die Evaluationen ${}\operatorname {ev} _{p}$, die Verknüpfung mit ${}\tau$ und die Minima und Maxima respektiert.

4. Man gebe bei ${}V$ unendlich ein ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ an, das nicht zu ${}N$ gehört.
5. Es sei ${}V$ endlich. Zeige

   ${}M=\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}\,.$

6. Zeige ${}M=N$.
7. Zeige, dass das Bild von ${}\Psi$ mit ${}M$ übereinstimmt.

Lösung

1. ${}\Psi$ ist nicht injektiv, da beispielsweise ${}p\wedge p$ und ${}p\rightarrow p$ Tautologien sind und daher beide auf die konstante Abbildung geschickt werden, die jeder Belegung den Wert ${}1$ zuordnet.
2. Es sei ${}W\subseteq V$ eine Teilmenge. Es gibt die natürliche Abbildung

   $\operatorname {Bel} \,{\left(V\right)}\longrightarrow \operatorname {Bel} \,{\left(W\right)},\,\lambda \longmapsto \lambda {|}_{W},$

   die jeder Belegung auf ${}V$ die eingeschränkte Belegung auf der Teilmenge ${}W$ zuordnet. Diese Abbildung ist surjektiv, da man jede Belegung auf ${}W$ zu einer Belegung auf ${}V$ fortsetzen kann, indem man auf ${}V\setminus W$ willkürlich Wahrheitswerte festlegt (beispielsweise konstant gleich ${}0$). Mit Hilfe dieser Abbildung ist durch

   $\Phi _{W}\colon \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}\longrightarrow \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)},\,\varphi \longmapsto {\left(\lambda \mapsto \varphi {\left(\lambda {|}_{W}\right)}\right)},$

   eine Abbildung festgelegt. Diese ist injektiv: wenn zwei Abbildungen ${}\varphi ,\theta \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ verschieden sind, so gibt es eine Belegung ${}\lambda \in \operatorname {Bel} \,{\left(W\right)}$ mit ${}\varphi (\lambda )\neq \theta (\lambda )$. Dann gilt dies auch für eine Fortsetzung ${}{\tilde {\lambda }}$ von ${}\lambda$ auf ganz ${}V$, und somit sind die Bilder von ${}\varphi$ und von ${}\theta$ in ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ verschieden.

3. Es sei ${}p\in W$. Dann ist für jede Belegung ${}\lambda \in \operatorname {Bel} \,{\left(V\right)}$

   ${}\Phi _{W}(\operatorname {ev} _{p})(\lambda )=\operatorname {ev} _{p}(\lambda {|}_{W})=\lambda {|}_{W}(p)=\lambda (p)=\operatorname {ev} _{p}(\lambda )\,,$

   also ist

   ${}\Phi _{W}(\operatorname {ev} _{p})=\operatorname {ev} _{p}\,.$

   Für ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ ist

   ${}{\begin{aligned}\Phi _{W}(\tau \circ \varphi )(\lambda )&=(\tau \circ \varphi )(\lambda {|}_{W})\\&=\tau (\varphi (\lambda {|}_{W}))\\&=\tau (\Phi _{W}(\varphi )(\lambda ))\\&=(\tau \circ \Phi _{W})(\varphi )(\lambda ).\end{aligned}}$

   Für ${}\varphi ,\theta \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ ist

   ${}{\begin{aligned}{\max {\left(\Phi _{W}(\varphi ),\Phi _{W}(\theta )\right)}}(\lambda )&={\max {\left(\Phi _{W}(\varphi )(\lambda ),\Phi _{W}(\theta )(\lambda )\right)}}\\&={\max {\left(\varphi (\lambda {|}_{W}),\theta (\lambda {|}_{W})\right)}}\\&={\max {\left(\varphi ,\theta \right)}}(\lambda {|}_{W})\\&=\Phi _{W}{\left({\max {\left(\varphi ,\theta \right)}}\right)}(\lambda )\end{aligned}}$

   und ebenso für das Minimum.

4. Wir betrachten die Abbildung ${}\psi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$, die die konstante Nullbelegung auf ${}0$ und jede andere Belegung auf ${}1$ abbildet. Wir müssen zeigen, dass diese Abbildung nicht von einer Abbildung aus ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ zu einer endlichen Teilmenge ${}W\subseteq V$ herrührt. Es sei also ${}W\subseteq V$ endlich gegeben. Da ${}V$ unendlich ist, gibt es ein ${}p\in V$, ${}p\notin W$. Es sei ${}\lambda$ die Belegung auf ${}V$, die auf der Teilmenge ${}W$ den Wert ${}0$ hat und an ${}p$ den Wert ${}1$ (und an den anderen Variablen einen beliebigen Wert) und ${}\lambda _{0}$ die konstante Nullbewertung auf ${}V$. Dann ist ${}\psi (\lambda )=1$ und ${}\psi (\lambda _{0})=0$. Wegen

   ${}\lambda {|}_{W}=\lambda _{0}{|}_{W}=0\,$

   besitzen aber die beiden auf ${}W$ eingeschränkten Belegungen unter jedem ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ den gleichen Wert und somit ist

   ${}\psi \neq \varphi \,.$

5. Es sei ${}V$ endlich. Die Belegungen auf ${}V$ entsprechen den Teilmengen aus ${}V$, indem man ${}\lambda$ mit ${}\lambda ^{-1}(1)$ identifiziert. Zu jeder Belegung ${}\lambda \in \operatorname {Bel} \,{\left(V\right)}$ gibt es eine Abbildung ${}\varphi _{\lambda }\in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$, die diese Belegung auf ${}1$ und alle anderen Belegungen auf ${}0$ abbildet. Dabei gilt

   ${}\varphi _{\lambda }={\min {\left({\min {\left(\operatorname {ev} _{p},p\in \lambda ^{-1}(1)\right)}},{\min {\left(\tau \circ \operatorname {ev} _{p},p\in \lambda ^{-1}(0)\right)}}\right)}}\,,$

   da der zweite Ausdruck für eine Belegung ${}\delta$ genau dann den Wert ${}1$ liefert, wenn für alle ${}p$ die Beziehung

   ${}\operatorname {ev} _{p}(\delta )=\delta (p)=1\,$

   genau dann gilt, wenn ${}p\in \lambda ^{-1}(1)$ ist, was genau bei ${}\delta =\lambda$ der Fall ist. Da die ${}\operatorname {ev} _{p}$ zu ${}N$ gehören und ${}N$ unter der Verknüpfung mit ${}\tau$ und unter den Minima von (endlich vielen) Abbildungen abgeschlossen ist, gehören die ${}\varphi _{\lambda }$ zu ${}N$.

   Ein Abbildung ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}$ ist dadurch festgelegt, für welche Belegungen sie den Wert ${}1$ ergibt. Wenn ${}\lambda _{i}$, ${}i\in I$, diese Belegungen sind, so ist

   ${}\varphi ={\max {\left(\varphi _{\lambda _{i}},i\in I\right)}}\,.$

   Da ${}M$ unter den Maxima von (endlich vielen) Abbildungen abgeschlossen ist, gehört ${}\varphi$ zu ${}N$.

6. Es sei zuerst ${}\varphi \in N$. Dann gibt es eine endliche Teilmenge ${}W\subseteq V$ mit ${}\varphi \in \operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$. Nach Teil (5), angewendet auf ${}W$, gehört ${}\varphi$ zu der in ${}\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(W\right)},\{0,1\}\right)}$ mit den gleichen Rekursionsvorschriften erzeugten Menge ${}M_{W}$ und damit zu ${}M$. Wenn umgekehrt ${}\varphi \in M$ ist, so wird ${}\varphi$ rekursiv erzeugt. Dabei gehen nur endlich viele Startglieder ${}\operatorname {ev} _{p_{1}},\ldots ,\operatorname {ev} _{p_{n}}$ ein. Den Konstruktionsprozess, der zu ${}\varphi$ führt, kann man daher auch über der endlichen Menge ${}W=\{p_{1},\ldots ,p_{n}\}$ durchführen, und somit ist ${}\varphi \in N$ nach Teil (3).
7. Den Nachweis, dass zu jedem ${}\alpha$ das Bild ${}\Psi (\alpha )$ zu ${}M$ gehört, führen wir rekursiv über den Aufbau von ${}L^{V}$. Zu einer Aussagenvariablen ${}p\in V$ ist

   ${}\Psi (p)=\operatorname {ev} _{p}\in M\,.$

   Zu ${}\alpha \in L^{V}$ ist

   ${}\Psi (\neg \alpha )=\tau \circ \Psi (\alpha )\,,$

   wenn also ${}\alpha$ nach ${}M$ abgebildet wird, so auch die Negation. Wegen

   ${}\Psi (\alpha \wedge \beta )={\min {\left(\Psi (\alpha ),\Psi (\beta )\right)}}\,$

   und

   ${}\Psi (\alpha \vee \beta )={\max {\left(\Psi (\alpha ),\Psi (\beta )\right)}}\,$

   werden mit ${}\Psi (\alpha )$ und ${}\Psi (\beta )$ auch die Konjunktion und die Disjunktion nach ${}M$ abgebildet. Da man die Implikation und die Äquivalenz durch die anderen Junktoren ausdrücken kann, und für semantisch äquivalente Ausdrücke der Wert unter ${}\Psi$ gleich bleibt, werden mit den Bestandteilen auch ${}\alpha \rightarrow \beta$ und ${}\alpha \leftrightarrow \beta$ nach ${}M$ abgebildet.

   Zum Nachweis, dass jede Abbildung ${}\varphi \in M$ zum Bild gehört, gehen wir rekursiv über den Aufbau von ${}M$ vor. Für die Evaluationen ${}\operatorname {ev} _{p}$ gilt

   ${}\Psi (p)=\operatorname {ev} _{p}\,.$

   Wenn ${}\varphi$ zum Bild gehört, sagen wir

   ${}\Psi (\alpha )=\varphi \,,$

   so gehört wegen

   ${}\Psi (\neg \alpha )=\tau \circ \varphi \,$

   auch ${}\tau \circ \varphi$ zum Bild. Wenn ${}\varphi$ und ${}\theta$ zum Bild gehören, sagen wir

   ${}\Psi (\alpha )=\varphi \,$

   und

   ${}\Psi (\beta )=\theta \,,$

   so gehören wegen

   ${}\Psi (\alpha \wedge \beta )={\min {\left(\varphi ,\theta \right)}}\,$

   und

   ${}\Psi (\alpha \vee \beta )={\max {\left(\varphi ,\theta \right)}}\,$

   auch das Minimum und das Maximum dazu.

Aufgabe (5 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine endliche Menge an Aussagen. Skizziere ein Entscheidungsverfahren, mit dem man feststellen kann, ob ${}\Gamma$ widersprüchlich ist oder nicht.

Lösung

In den endlich vielen Ausdrücken ${}\alpha _{1},\ldots ,\alpha _{n}$ von ${}\Gamma$ kommen insgesamt nur endlich viele Aussagenvariablen vor, sagen wir ${}p_{1},\ldots ,p_{k}$. Für jede ${}\pm$-Kombination

${}\gamma =\pm p_{1}\wedge \ldots \wedge \pm p_{k}\,$

untersucht man, ob ${}\Gamma \cup \{\gamma \}$ widersprüchlich ist. Da durch ${}\gamma$ jede Aussagenvariable entweder positiv oder in ihrer Negation aus ${}\Gamma \cup \{\gamma \}$ ableitbar ist, kann man für jedes ${}\alpha _{i}$ überprüfen, ob ${}\neg \alpha _{i}$ aus ${}\Gamma \cup \{\gamma \}$ ableitbar ist. Wenn die durch ${}\gamma$ gegebene Belegung sämtliche ${}\alpha _{i}$ erfüllt, so hat man eine Belegung gefunden, die zeigt, dass ${}\Gamma$ erfüllbar und damit widerspruchsfrei ist. Im andern Fall stellt sich heraus, dass zu jedem ${}\gamma$ mindestens ein ${}\alpha _{i}$ die Belegung falsch bekommt. Nach Aufgabe 5.28 (Einführung in die mathematische Logik (Osnabrück 2021)) ist ${}\gamma \rightarrow \alpha _{i}$ oder ${}\gamma \rightarrow \neg \alpha _{i}$ ableitbar, wobei im gegebenen Fall nur die zweite Möglichkeit

$\vdash \gamma \rightarrow \neg \alpha _{i}$

verbleibt. Wegen ${}\alpha _{i}\in \Gamma$ erhält man also

$\Gamma \vdash \gamma \rightarrow q\wedge \neg q.$

Da dies für jede Kombination ${}\gamma$ gilt, kann man mit mehrfacher Anwendung der Fallunterscheidungsregel

$\Gamma \vdash q\wedge \neg q$

zeigen. In diesem Fall ist also ${}\Gamma$ widersprüchlich.

Aufgabe (3 Punkte)

Es sei ${}A(n)$ eine Aussage(nform), in die man eine natürliche Zahl einsetzen kann. Diskutiere den Unterschied zwischen den beiden Aussagen

${\left(\forall nA(n)\right)}\rightarrow {\left(\forall nA(n+1)\right)}\,\,{\text{ und }}\,\,\forall n{\left(A(n)\rightarrow A(n+1)\right)}.$

Was ist die mathematische Relevanz der beiden Aussagen?

Lösung Vollständige Induktion/Allquantor/Aufgabe/Lösung

Aufgabe (3 Punkte)

Wir rechnen mit den Zahlen ${}0,1,2,{\text{viele}}\,\,(v)$ nach den folgenden Verknüpfungstabellen.

${}+$	${}0$	${}1$	${}2$	${}v$
${}0$	${}0$	${}1$	${}2$	${}v$
${}1$	${}1$	${}2$	${}v$	${}v$
${}2$	${}2$	${}v$	${}v$	${}v$
${}v$	${}v$	${}v$	${}v$	${}v$

und

${}\cdot$	${}0$	${}1$	${}2$	${}v$
${}0$	${}0$	${}0$	${}0$	${}0$
${}1$	${}0$	${}1$	${}2$	${}v$
${}2$	${}0$	${}2$	${}v$	${}v$
${}v$	${}0$	${}v$	${}v$	${}v$

Zeige, dass es sich dabei um einen kommutativen Halbring handelt. Gilt für diesen die Abziehregel?

Lösung

Es sei ${}H$ die in Frage stehende Struktur mit der angegebenen Addition und Multiplikation. Die Abbildung

$\varphi \colon \mathbb {N} \longrightarrow H,$

die ${}0$ auf ${}0$, ${}1$ auf ${}1$, ${}2$ auf ${}2$ und jede weitere Zahl auf ${}v$ abbildet, ist surjektiv und sie respektiert, wie eine direkte Durchsicht zeigt, die Addition und die Multiplikation. Somit übertragen sich die Gesetze eines kommutativen Halbringes von ${}\mathbb {N}$ nach ${}H$. Die Abziehregel gilt in ${}H$ nicht, da

${}1+v=v=2+v\,$

ist, aber

${}1\neq 2\,.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

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

Lösung

Die Register ${}R_{1}$ und ${}R_{2}$ seien zu Beginn leer.

$1.\,\,1+$

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

$3.\,\,1-$

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

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

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

Am Anfang wird der erste Register auf ${}1$ erhöht und dies wird im zweiten Befehl ausgedruckt. Im dritten Befehl wird dieser Registerinhalt auf ${}0$ reduziert und dies im vierten Befehl ausgedruckt. Mit dem fünften Befehl wird auf den ersten Befehl umgeleitet, da der zweite Register stets auf ${}0$ bleibt, so dass sich alles wiederholt.

Aufgabe (10 Punkte)

Beweise den Fixpunktsatz der Prädikatenlogik.

Lösung

Wir betrachten die Abbildung

$F\colon \mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(m,n)\longmapsto F(m,n),$

die durch

$F(m,n):={\begin{cases}GN(\alpha (n)),\,{\text{ falls }}m{\text{ die }}GN{\text{ eines }}\alpha \in L_{1}^{\rm {Ar}}{\text{ ist}}\,,\\0{\text{ sonst}}\,,\end{cases}}\,$

festgelegt ist. Bei der Berechnung von ${}F$ wird also zuerst geschaut, ob das erste Argument, also ${}m$, die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist ${}F(m,n)=0$, unabhängig von ${}n$. Falls ja, so ist also ${}m=GN(\alpha )$ mit ${}\alpha \in L_{1}^{\rm {Ar}}$. In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also ${}n$, ersetzt, wobei man einen Satz ${}\alpha (n)$ erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung ${}F(m,n)$. In diesem Fall ist also ${}F(m,n)=GN(\alpha (n))$. Diese Erläuterungen zeigen zugleich, dass ${}F$ berechenbar ist.
Da ${}\Gamma$ nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck ${}\varphi (x,y,z)$ mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen ${}m,n,k$ die Beziehungen (wir können annehmen, dass ${}\Gamma$ widerspruchsfrei ist, da andernfalls das Resultat trivial ist)

$F(m,n)=k{\text{ genau dann, wenn }}\Gamma \vdash \varphi (m,n,k),$

$F(m,n)\not =k{\text{ genau dann, wenn }}\Gamma \vdash \neg \varphi (m,n,k)$

und (für jede Belegung ${}m,n$ für ${}x$ und ${}y$)

$\Gamma \vdash \exists !z\varphi (m,n,z).$

Den Fixpunkt zu einem vorgegebenen ${}\alpha \in L_{1}^{\rm {Ar}}$ erhalten wir nun durch eine trickreiche Anwendung von ${}\varphi$. Wir setzen

${}s:=\forall z{\left(\varphi (x,x,z)\rightarrow \alpha (z)\right)}\,.$

Der Ausdruck ${}s$ besitzt die Gödelnummer ${}GN(s)$. Wir behaupten nun, dass der Satz

${}q:=s{\frac {GN(s)}{x}}=\forall z{\left(\varphi (GN(s),GN(s),z)\rightarrow \alpha (z)\right)}\,$

die zu beweisende Ableitungsbeziehung ${}\Gamma \vdash q\leftrightarrow \alpha (GN(q))$ erfüllt.
Der Ausdruck ${}s$ besitzt die einzige freie Variable ${}x$, daher gilt

${}F(GN(s),GN(s))=GN{\left(s{\frac {GN(s)}{x}}\right)}=GN(q)\,.$

Aufgrund der Repräsentierungseigenschaft ist daher

$\Gamma \vdash \varphi (GN(s),GN(s),GN(q)).$

Aus der Allaussage ${}q$ erhält man durch Spezialisierung (man ersetzt die Variable ${}z$ durch den Term $GN(q)$)

$\vdash q\rightarrow {\left(\varphi (GN(s),GN(s),GN(q))\rightarrow \alpha (GN(q))\right)}.$

Da das Antezedens der rechten Implikation aus ${}\Gamma$ ableitbar ist, folgt

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

 Dies besagt also die Ableitbarkeit der Hinrichtung.

Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu

$\Gamma \vdash \forall z{\left(\varphi (GN(s),GN(s),z)\rightarrow (z=GN(q))\right)}.$

Durch Substitution ergibt sich

$\vdash (z=GN(q))\rightarrow (\alpha (GN(q))\rightarrow \alpha (z))$

und somit nach einer prädikatenlogischen Umformulierung

$\Gamma \vdash \forall z{\left(\varphi (GN(s),GN(s),z)\wedge \alpha (GN(q))\rightarrow \alpha (z)\right)}.$

Da hierbei ${}\alpha (GN(q))$ keine freie Variablen besitzt, ist auch

$\Gamma \vdash \alpha (GN(q))\rightarrow {\left(\forall z(\varphi (GN(s),GN(s),z)\rightarrow \alpha (z))\right)},$

und das Sukzedens ist gerade ${}q$, so dass auch die Rückrichtung ableitbar ist.

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