Kurs:Einführung in die mathematische Logik/3/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	2	5	3	3	4	7	6	2	4	4	3	6	4	5	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Termmenge zu einer Grundtermmenge ${}(V,K,F_{n})$.
2. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge ${}\Gamma \subseteq L^{S}$.
3. Die Multiplikation mit ${}n\in \mathbb {N}$ in einem Dedekind-Peano-Modell ${}\mathbb {N}$.
4. Die Befehle für eine Registermaschine.
5. Das modallogische Löb-Axiom.
6. Ein modallogisches Modell.

Lösung

1. Die Termmenge ist diejenige Teilmenge ${}T=T(G)$ der Wörter ${}A^{*}$ über dem Termalphabet ${}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}$, die durch die folgenden rekursiven Vorschriften festgelegt wird.
   1. Jede Variable ${}v\in V$ ist ein Term.
   2. Jede Konstante ${}c\in K$ ist ein Term.
   3. Für jedes ${}f\in F_{n}$ und ${}n$ Terme ${}t_{1},t_{2},\ldots ,t_{n}$ ist auch ${}ft_{1}t_{2}\ldots t_{n}$ ein Term.
2. Die Menge ${}\Gamma$ heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks ${}\alpha \not \in \Gamma$ die Menge widersprüchlich macht.
3. Die Multiplikation mit ${}n$ ist diejenige aufgrund von Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)) eindeutig bestimmte Abbildung

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

   für die

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

   gilt.

4. Die Befehle für eine Registermaschine sind (dabei bezeichnen ${}R_{i}$ Register und ${}B_{j}$ Befehlszeilen).
   1. ${}i+$ (erhöhe den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. um einen Strich).
   2. ${}i-$ (reduziere den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
   3. ${}C(ij)$ (wenn das ${}i$-te Register leer ist, so gehe zum Befehl ${}B_{j}$, andernfalls zum nächsten Befehl).
   4. Drucke (drucke den Inhalt des ersten Registers).
   5. Halte an.
5. Das modallogische Axiomenschema

   $\Box (\Box \alpha \rightarrow \alpha )\rightarrow \Box \alpha$

   nennt man Löb-Axiom.

6. Unter einem modallogischen Modell versteht man einen gerichteten Graphen ${}(M,R)$ zusammen mit einer Wahrheitsbelegung ${}\mu$ für die Aussagenvariablen für jeden Knotenpunkt ${}w\in M$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Vollständigkeitssatz für Tautologien (Prädikatenlogik).
3. Der zweite Gödelsche Unvollständigkeitssatz.

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 und ${}\alpha \in L^{S}$ ein ${}S$-Ausdruck. Dann ist ${}\alpha$ genau dann eine ableitbare Tautologie, wenn ${}\alpha$ allgemeingültig ist.
3. Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse. Dann ist die Widerspruchsfreiheit ${}WF(\Gamma )$ nicht aus ${}\Gamma$ ableitbar, d.h. es ist

   $\Gamma \not \vdash WF(\Gamma ).$

Aufgabe (2 (1+1) Punkte)

Im Pokal spielt Bayern München gegen den TSV Wildberg. Der Trainer vom TSV Wildberg, Herr Tor Acker, sagt „Wir haben in dem Spiel nichts zu verlieren“. Die Logiklehrerin von Wildberg, Frau Loki Schummele, sagt „Wenn die Wildberger in dem Spiel nichts zu verlieren haben, dann haben auch die Münchner in dem Spiel nichts zu gewinnen“. Der Trainer von Bayern München, Herr Roland Rollrasen, sagt „Wir haben in dem Spiel etwas zu gewinnen“.

1. Ist die Aussage von Frau Schummele logisch korrekt?
2. Es sei vorausgesetzt, dass die Aussage des Bayerntrainers wahr ist. Welche Folgerung kann man dann für die Aussage von Herrn Acker ziehen?

Lösung

1. Die Aussage ist logisch korrekt.
2. Die Kontraposition der korrekten Aussage aus Teil (1) ist: Wenn die Münchner in dem Spiel etwas zu gewinnen haben, dann haben die Wildberger in dem Spiel etwas zu verlieren. Da der Vordersatz, der die Aussage des Bayerntrainers ist, vorausgesetzt werden soll, so folgt mit Modus ponens, dass die Wildberger in dem Spiel etwas zu verlieren haben. Dies steht im Widerspruch zur Aussage des Trainers von Wildberg, seine Aussage ist also falsch.

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

1. Löse das folgende Minisudoku

   ${\begin{pmatrix}-&-&2&-\\3&-&-&4\\-&-&-&-\\-&4&-&1\end{pmatrix}}.$

2. Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
3. Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?

Lösung

1. ${\begin{pmatrix}4&1&2&3\\3&2&1&4\\1&3&4&2\\2&4&3&1\end{pmatrix}}.$

2. Wir gehen von

   ${\begin{pmatrix}-&-&2&-\\3&-&-&4\\-&-&-&-\\-&4&-&1\end{pmatrix}}$

   aus. In der dritten Stelle der zweiten Zeile muss eine ${}1$ sein und somit muss rechts oben eine ${}3$ stehen. Dies ergibt

   ${\begin{pmatrix}-&-&2&3\\3&-&1&4\\-&-&-&-\\-&4&-&1\end{pmatrix}}.$

   An der vierten Stelle der dritten Zeile muss eine ${}2$ stehen. In der vierten Zeile muss an der dritten Stelle eine ${}3$ und somit in der vierten Zeile an der ersten Stelle eine ${}2$ stehen. Dies ergibt

   ${\begin{pmatrix}-&-&2&3\\3&-&1&4\\-&-&-&2\\2&4&3&1\end{pmatrix}}.$

   Dies erzwingt

   ${\begin{pmatrix}-&-&2&3\\3&2&1&4\\-&-&4&2\\2&4&3&1\end{pmatrix}}.$

   An der zweiten Stelle der ersten Zeile muss eine ${}1$ stehen, dies ergibt dann die eindeutige Lösung

   ${\begin{pmatrix}4&1&2&3\\3&2&1&4\\1&3&4&2\\2&4&3&1\end{pmatrix}}.$

3. 1. Direkter Beweis: Durch Betrachten der schon gefundenen Zahlen erschließt man, welche Zahl in ein bestimmtes Feld gesetzt werden muss.
   2. Beweis durch Fallunterscheidung: Man weiß, dass in einem gewissen Feld nur noch zwei Zahlen, sagen wir ${}a$ oder ${}b$ möglich sind. Wenn man nun in beiden Fällen, dass es sich um ${}a$ oder um ${}b$ handelt, jeweils erschließen kann, dass in einem bestimmten anderen Feld die Zahl ${}c$ stehen muss, so steht diese Zahl fest.
   3. Beweis durch Widerspruch: Man weiß, dass in einem gewissen Feld nur noch zwei Zahlen, sagen wir ${}a$ oder ${}b$ möglich sind. Man nimmt nun an, dass es sich um ${}a$ handelt. Wenn man nun erschließen kann, dass sich daraus an irgendeiner Stelle ein Widerspruch ergibt, so kann die Belegung durch ${}a$ nicht gelten und ${}b$ ist richtig.

Aufgabe (3 Punkte)

Beweise durch Induktion über den rekursiven Aufbau der Sprache ${}L^{V}$, dass in jeder Aussage ${}\alpha \in L^{V}$ die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.

Lösung

Wenn ${}p$ eine Aussagenvariable ist, so kommt darin weder eine linke noch eine rechte Klammer vor und die Anzahl stimmt überein. Zum Beweis der Rekursionsschritte sei zunächst ${}\alpha =\neg (\beta )$ und vorausgesetzt, dass die Anzahl der linken und die Anzahl der rechten Klammern in ${}\beta$ übereinstimmen. Dann besitzt ${}\alpha$ sowohl eine linke als auch eine rechte Klammer mehr als ${}\beta$, so dass die Anzahlen wieder übereinstimmen. Es sei nun ${}\alpha =(\beta )\star (\gamma )$ mit ${}\star =\wedge ,\vee ,\rightarrow ,\leftrightarrow$ und sei vorausgesetzt, dass ${}\beta$ ${}k$ linke und auch rechte Klammern und ${}\gamma$ ${}\ell$ linke und auch rechte Klammern besitzt. Dann besitzt ${}\alpha$ ${}k+l+2$ linke und auch rechte Klammern.

Aufgabe (3 Punkte)

Zeige, dass eine Regel der Form

Wenn ${}\vdash \alpha$, dann ${}\vdash \beta$ gelten kann, ohne dass ${}\vdash \alpha \rightarrow \beta$ gilt.

Lösung

Es gilt die Regel: Wenn ${}\vdash p$, dann ${}\vdash q$, wobei ${}p,q$ zwei verschiedene Aussagenvariablen sind, und zwar aus dem einfachen Grund, dass ${}\vdash p$ nicht gilt. Dagegen gilt ${}\vdash p\rightarrow q$ nicht.

Aufgabe (4 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Begründe die Kettenschlussregel für die Ableitungsbeziehung: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \beta \rightarrow \gamma$, dann auch ${}\Gamma \vdash \alpha \rightarrow \gamma$.

Lösung

Die Voraussetzung bedeutet, dass es Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{m},\beta _{1},\ldots ,\beta _{n}\in \Gamma$ mit

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{m}\rightarrow {\left(\alpha \rightarrow \beta \right)}$

und mit

$\vdash \beta _{1}\wedge \ldots \wedge \beta _{n}\rightarrow {\left(\beta \rightarrow \gamma \right)}$

gibt. Daraus ergibt sich mit Hilfe (der Regelversion) von Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021))  (2)

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{m}\wedge \beta _{1}\wedge \ldots \wedge \beta _{n}\rightarrow {\left(\alpha \rightarrow \beta \right)}\wedge {\left(\beta \rightarrow \gamma \right)}.$

Es gilt die Tautologie (Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (2),)

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

Aus der Regelversion dieses Axioms ergibt sich

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{m}\wedge \beta _{1}\wedge \ldots \wedge \beta _{n}\rightarrow {\left(\alpha \rightarrow \gamma \right)}.$

Dies bedeutet ${}\Gamma \vdash \alpha \rightarrow \gamma$.

Aufgabe (7 (3+4) Punkte)

Es sei ${}V=\{x,y,z,u,v,w\}$ eine Variablenmenge, ${}0$ eine Konstante und ${}-,+,\cdot$ zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck ${}\alpha$, der durch

$\forall x\forall y\forall z\forall u\forall v\forall w{\left(\left[(z-x)(z-y)+(w-u)(w-v)=0\right]\longrightarrow \left[(x-y)(x-y)+(u-v)(u-v)=(x-z)(x-z)+(u-w)(u-w)+(y-z)(y-z)+(v-w)(v-w)\right]\right)}$

gegeben ist.

1. Zeige, dass ${}\alpha$ bei Interpretation in einem Körper ${}K$ wahr wird, wenn man ${}0$ als ${}0$ und ${}\{-,+,\cdot \}$ als Subtraktion, Addition und Multiplikation interpretiert.
2. Welcher wichtige mathematische Satz verbirgt sich dahinter?

Lösung

1. Es sei ein Körper ${}K$ mit Elementen ${}x,y,z,u,v,w$ gegeben und sei vorausgesetzt, dass

   ${}(z-x)(z-y)+(w-u)(w-v)=0\,$

   ist. Unter Verwendung des Distributivgesetzes (bzw. der zweiten binomischen Formel) bedeutet dies

   ${}z^{2}-xz-yz+xy+w^{2}-uw-vw+uv=0\,.$

   Entsprechend ist

   ${}{\begin{aligned}(x-z)(x-z)+(u-w)(u-w)+(y-z)(y-z)+(v-w)(v-w)&=x^{2}+z^{2}-2xz+u^{2}+w^{2}-2uw+y^{2}+z^{2}-2yz+v^{2}+w^{2}-2vw\\&=x^{2}-2xz+u^{2}-2uw+y^{2}-2yz+v^{2}-2vw+2z^{2}+2w^{2}.\end{aligned}}$

   Wenn wir davon zweimal ${}0$ abziehen, und zwar in der oben etablierten Form, so ändert sich der Wert nicht und dies ist gleich

   ${}{\begin{aligned}x^{2}-2xz+u^{2}-2uw+y^{2}-2yz+v^{2}-2vw+2z^{2}+2w^{2}-2{\left(z^{2}-xz-yz+xy+w^{2}-uw-vw+uv\right)}&=x^{2}+u^{2}+y^{2}+v^{2}-2xy-2uv\\&=(x-y)(x-y)+(u-v)(u-v),\end{aligned}}$

   was insgesamt die Behauptung ist.

2. Es handelt sich bei ${}K=\mathbb {R}$ um den Satz des Pythagoras. Die sechs Variablen definieren drei Punkte in der Ebene ${}\mathbb {R} ^{2}$, sagen wir

   $P={\begin{pmatrix}x\\u\end{pmatrix}},\,Q={\begin{pmatrix}y\\v\end{pmatrix}},\,R={\begin{pmatrix}z\\w\end{pmatrix}}.$

   Die Verbindungsvektoren sind dann

   ${}R-P={\begin{pmatrix}z\\w\end{pmatrix}}-{\begin{pmatrix}x\\u\end{pmatrix}}={\begin{pmatrix}z-x\\w-u\end{pmatrix}}\,$

   und

   ${}R-Q={\begin{pmatrix}z\\w\end{pmatrix}}-{\begin{pmatrix}y\\v\end{pmatrix}}={\begin{pmatrix}z-y\\w-v\end{pmatrix}}\,.$

   Das Skalarprodukt dieser beiden Vektoren ist

   ${}\left\langle {\begin{pmatrix}z-x\\w-u\end{pmatrix}},{\begin{pmatrix}z-y\\w-v\end{pmatrix}}\right\rangle =(z-x)(z-y)+(w-u)(w-v)\,.$

   Dass dies gleich ${}0$ ist, bedeutet, dass diese beiden Vektoren aufeinander senkrecht stehen, dass also ${}P,Q,R$ ein rechtwinkliges Dreieck mit dem rechten Winkel an ${}R$ bilden. Das Quadrat der Länge der Strecke von ${}P$ nach ${}Q$ ist

   ${}{\begin{aligned}d(P,Q)^{2}&=\Vert {{\begin{pmatrix}x\\u\end{pmatrix}}-{\begin{pmatrix}y\\v\end{pmatrix}}}\Vert ^{2}\\&=\Vert {\begin{pmatrix}x-y\\u-v\end{pmatrix}}\Vert ^{2}\\&=(x-y)(x-y)+(u-v)(u-v)\end{aligned}}$

   und entsprechend ist

   ${}d(P,R)^{2}=(x-z)(x-z)+(u-w)(u-w)\,$

   und

   ${}d(Q,R)^{2}=(y-z)(y-z)+(v-w)(v-w)\,.$

   Der Nachsatz drückt also die Längenbeziehung im rechtwinkligen Dreieck aus.

Aufgabe (6 Punkte)

Beweise die Termaussage des Substitutionslemmas.

Lösung

Dies wird über den induktiven Aufbau der Terme bewiesen. (1). Für eine Konstante ${}c$ ist die Aussage richtig, da ihre Interpretation unverändert ist. Für eine Variable ${}x$ macht man eine Fallunterscheidung. Wenn

${}x=x_{i}\,$

mit einer der an der Substitution beteiligten Variablen ist, so ist

${}I{\left(x_{i}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}=I(t_{i})={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(x_{i})\,.$

Bei einer an der Substitution nicht beteiligten Variablen ${}x$ ist

${}I{\left(x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}=I(x)={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(x)\,.$

Wenn ${}f$ ein ${}n$-stelliges Funktionssymbol ist und ${}s_{1},\ldots ,s_{n}$ Terme sind, für die die Gleichheit schon bekannt ist, so ist

${}{\begin{aligned}I{\left({\left(fs_{1}\ldots s_{n}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}&=I{\left(fs_{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}}}\right)}\\&=I(f){\left(I{\left(s_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)},\ldots ,I{\left(s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}\right)}\\&=I(f){\left({\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s_{1}),\ldots ,{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s_{n})\right)}\\&={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(f){\left({\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}{\left(s_{1}\right)},\ldots ,{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}{\left(s_{n}\right)}\right)}\\&={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}{\left(fs_{1}\ldots s_{n}\right)}.\end{aligned}}$

Aufgabe (2 Punkte)

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet ${}S$, dass ein Untervektorraum in einem Vektorraum über einem Körper vorliegt.

Lösung

Wir gehen davon aus, dass wir für ${}K$ und ${}V$ schon eine prädikatenlogische Beschreibung wie in Beispiel 8.8 (Einführung in die mathematische Logik (Osnabrück 2021)) gefunden haben. Zur prädikatenlogischen Beschreibung eines Untervektorraumes führen wir ein weiteres einstelliges Relationssysmbol ${}U$ ein. Die folgenden Axiome charakterisieren dann einen Untervektorraum.

1. $\forall x(Ux\rightarrow Vx),$

2. $U0_{V},$

3. $\forall x\forall y(Ux\wedge Uy\rightarrow Ux+_{V}y),$

4. $\forall x\forall y(Kx\wedge Uy\rightarrow Ux\cdot y).$

Aufgabe (4 Punkte)

Zeige, dass in einem Peano-Halbring ${}M$ zu ${}d\geq 1$ die Division mit Rest eindeutig ist.

Lösung

Es gelte

${}qd+r=q'd+r'\,$

mit

${}0\leq r,r'<d\,.$

Ohne Einschränkung können wir ${}q'\geq q$ annehmen. Dann ist

${}q'=q+u\,$

mit einem ${}u\in M$ und somit ist

${}qd+r=q'd+r'=(q+u)d+r'=qd+ud+r'\,.$

Aufgrund der Abziehregel ergibt sich

${}r=ud+r'\,.$

Bei ${}u\neq 0$ ist ${}u\geq 1$ nach Lemma 13.4 (Einführung in die mathematische Logik (Osnabrück 2021)). Dann ergibt sich der Widerspruch

${}d=ud+r'\geq ud\geq d\,$

wegen der Verträglichkeit der Ordnung mit der Multiplikation. (siehe Lemma 13.6 (Einführung in die mathematische Logik (Osnabrück 2021))). Also ist ${}u=0$ und damit ${}q'=q$ und ${}r'=r$.

Aufgabe (4 Punkte)

Beschreibe die wesentlichen Punkte bei der Konstruktion eines Modells, mit dem man die Erfüllbarkeit einer maximal widerspruchsfreien Ausdrucksmenge, die Beispiele enthält, nachweist.

Lösung Vollständigkeitssatz/Konstruktion/Aufgabe/Lösung

Aufgabe (3 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe ${}\mathbb {Z} /(2)\times \mathbb {Z} /(2)$ zum Symbolalphabet ${}S=\{0,+\}$.

Lösung

Die Äquivalenzklassen sind ${}\{(0,0)\}$ und ${}\{(1,0),(0,1),(1,1)\}$. Die in der angegebenen Sprache formulierbare Eigenschaft ${}x=0$ wird nur durch das neutrale Element erfüllt und ist somit ein charakterisierender Ausdruck für ${}\{(0,0)\}$. Nach (dem Zusatz zu) Satz 16.7 (Einführung in die mathematische Logik (Osnabrück 2021)) sind Elemente, die unter einem Automorphismus aufeinander abgebildet werden, zueinander elementar äquivalent. Die Komponentenvertauschung bildet ${}(1,0)$ auf ${}(0,1)$ ab und die invertierbare Matrix ${}{\begin{pmatrix}1&1\\1&0\end{pmatrix}}$ (wir fassen ${}\mathbb {Z} /(2)\times \mathbb {Z} /(2)$ als Vektorraum über ${}\mathbb {Z} /(2)$ auf) ergibt einen Automorphismus, der ${}(1,0)$ auf ${}(1,1)$ abbildet.

Aufgabe (6 Punkte)

Es sei ${}T\subseteq \mathbb {N}$ eine endliche Teilmenge. Man gebe ein Programm für eine Registermaschine an, das nur auf einen einzigen Register ${}R_{1}$ Bezug nimmt, das bei jeder Eingabe (in ${}R_{1}$) immer anhält und das im Anhaltezustand in ${}R_{1}$ genau dann den Wert ${}0$ besitzt, wenn die Eingabe zu ${}T$ gehört.

Lösung

Wir ordnen die endlich vielen, sagen wir ${}s$, Zahlen aus ${}T$ in aufsteigender Reihenfolge, also

${}n_{1}<n_{2}<n_{3}<\cdots <n_{s-1}<n_{s}\,.$

Wir setzen

${}d_{1}:=n_{1}\,$

und

${}d_{i}:=n_{i}-n_{i-1}\,$

für ${}i=2,\ldots ,s$. Die ${}d_{i}$ sind also einfach die Differenzen zwischen den aufeinanderfolgenden Zahlen aus ${}T$, und es ist

${}n_{i}=d_{1}+d_{2}+\cdots +d_{i}\,.$

Wir erstellen das Programm mit Hilfe von ${}s$ Programmblöcken der Länge ${}2d_{i}$ der Form

$\,\,1-$

$\,\,C(1,h-1)$

$\,\,1-$

$\,\,C(1,h-1)$

$\vdots$

$\,\,1-$

$\,\,C(1,h-1)$

$\,\,1-$

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

Der Inhalt von ${}R_{1}$ wird also abwechselnd um ${}1$ reduziert und abwechselnd wird gefragt, ob der Inhalt leer ist, wobei im leeren Fall auf die Befehlszeile ${}h-1$ verwiesen, aber die allerletzte Abfrage des Blockes auf die ${}h$-te Befehlszeile verweist. Bei

${}d_{1}=1\,$

besteht der erste Block allein aus ${}C(1,h)$. Diese ${}s$ Blöcke werden hintereinander geschrieben, und das Programm wird durch

$h-1.\,\,1+$

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

abgeschlossen.

Die Wirkungsweise des Programms macht man sich folgendermaßen klar. Zu jedez zu testenden Zahl ${}n\in \mathbb {N}$ gibt es ein eindeutiges ${}i$ mit

${}n_{i-1}<n\leq n_{i}\,$

(wobei ${}n_{-1}$ als ${}0$ zu lesen ist) oder aber

${}n>n_{s}\,.$

In den ersten ${}i-1$ Programmblöcken bleibt der Inhalt des Registers positiv, da ja insgesamt nur

${}n_{i-1}=d_{1}+\cdots +d_{i-1}\,$

von ${}n$ abgezogen wird. Daher gelangt man in den entscheidenden ${}i$-ten Block. Wenn dieser Block begonnen wird, steht im Register der Wert ${}n-n_{i-1}$, und für diesen Wert gilt

${}0<n-n_{i-1}\leq n_{i}-n_{i-1}=d_{i}\,.$

Bei

${}n<n_{i}\,$

ist

${}n-n_{i}<d_{i}\,$

so dass durch das Abziehen in diesem Block die ${}0$ erreicht wird, und zwar vor dem vorletzten Befehl des Blocks, so dass nach ${}h-1$ umgeleitet wird. Dort wird um ${}1$ erhöht (was nur bei $n=0\notin T$ benötigt wird) und das Endergebnis ist nicht ${}0$, was korrekt ist.

Bei

${}n=n_{i}\,$

ist

${}n-n_{i}=d_{i}\,$

so dass durch das Abziehen in diesem Block die ${}0$ erreicht wird, und zwar genau im vorletzten Befehl des Blocks. Im nächsten Befehl wird nach ${}h$ umgeleitet und das Programm hält an mit der ${}0$ als Ausgabe, was auch korrekt ist. Bei ${}n>n_{s}$ werden alle Blöcke ohne Umleitung durchlaufen, in ${}h-1$ wird erhöht und anschließend wird angehalten mit einen positivem Inhalt des ersten Registers.

Aufgabe (4 Punkte)

Es sei

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

eine arithmetisch repräsentierbare Abbildung. Zeige, dass zu jedem Punkt ${}P\in \mathbb {N} ^{s}$ die Faser

${}F^{-1}(P)\subseteq \mathbb {N} ^{r}\,$

arithmetisch repräsentierbar ist.

Lösung

Nach Voraussetzung gibt es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen ${}x_{1},\ldots ,x_{r},x_{r+1},\ldots ,x_{r+s}$ derart, 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. Es sei

${}P=(p_{1},\ldots ,p_{s})\in \mathbb {N} ^{s}\,$

ein Punkt. Dabei gilt insbesondere für beliebige ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Gleichheit ${}F(n_{1},\ldots ,n_{r})=(p_{1},\ldots ,p_{s})$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r},p_{1},\ldots ,p_{s})$ gilt. Diese Gleichung bedeutet, dass ${}(n_{1},\ldots ,n_{r})$ zur Faser über ${}P$ gehört. Daher ist der Ausdruck

${}\varphi :=\psi (x_{1},\ldots ,x_{r},p_{1},\ldots ,p_{s})\,$

in den freien Variablen ${}x_{1},\ldots ,x_{r}$ ein Ausdruck, der die Faser über ${}P$ arithmetisch repräsentiert.

Aufgabe (5 Punkte)

Zeige, dass eine aufzählbar axiomatisierbare Theorie ${}T\subseteq L_{0}^{S}$ auch ${}R$-aufzählbar ist.

Lösung

Es sei ${}\Gamma$ eine ${}R$- aufzählbare Satzmenge, die ${}T$ axiomatisiert, und es sei ${}\alpha _{n}$, ${}n\in \mathbb {N} _{+}$, eine ${}R$-Aufzählung von ${}\Gamma$. Es sei ${}\beta _{n}$, ${}n\in \mathbb {N} _{+}$, eine ${}R$-Aufzählung der prädikatenlogischen Tautologien aus ${}L^{S}$. Wenn ein Satz ${}\gamma$ aus ${}\Gamma$ ableitbar ist, so gibt es eine endliche Auswahl ${}\alpha _{1},\ldots ,\alpha _{n}$ aus ${}\Gamma$ (bzw. aus der gewählten Aufzählung) derart, dass

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

eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem ${}n$ wächst, das Gewünschte: Für jedes ${}n$ notiert man die Tautologien ${}\beta _{1},\ldots ,\beta _{n}$ in der Form

${}\beta _{i}=\delta _{1}\wedge \ldots \wedge \delta _{s}\rightarrow \epsilon \,.$

Wenn ${}\beta _{i}$ überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes ${}i\leq n$, ob alle ${}\delta _{1},\ldots ,\delta _{s}$ zu ${}\{\alpha _{1},\ldots ,\alpha _{n}\}$ gehören. Falls ja, und wenn ${}\epsilon$ ein Satz ist, so wird ${}\epsilon$ notiert. Danach geht man zum nächsten ${}i$. Wenn man ${}i=n$, erreicht hat, so geht man zu ${}n+1$, wobei man aber wieder bei ${}i=1$ anfängt.