Lösung
- Die folgenden rekursiv definierten Wörter heißen die
Ausdrücke
dieser Sprache.
- Wenn
und
Terme sind, so ist -
ein Ausdruck.
- Wenn
ein
-stelliges Relationssymbol ist und
Terme sind, so ist
-
ein Ausdruck.
- Wenn
und
Ausdrücke sind, so sind auch
-
Ausdrücke.
- Wenn
ein Ausdruck ist und
eine Variable, so sind auch
-
Ausdrücke.
- Ein Ideal ist eine nichtleere Teilmenge
, für die die beiden folgenden Bedingungen erfüllt sind:
- Für alle
ist auch
.
- Für alle
und
ist auch
.
- Die Variablensubstitution definiert man rekursiv über den Aufbau der
-
Ausdrücke.
- Für Terme
setzt man
-
- Für ein
-stelliges Relationssymbol
und
Terme
setzt man
-
- Für einen Ausdruck
setzt man
-
- Für Ausdrücke
und
setzt man
-
und ebenso für die anderen zweistelligen Junktoren.
- Für einen Ausdruck
seien
diejenigen Variablen
(unter den
),
die in
frei vorkommen. Es sei
, falls
nicht in
vorkommt. Andernfalls sei
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
noch in
vorkommt. Dann setzt man
-
und ebenso für den Existenzquantor.
- Der Ausdruck
heißt
ableitbar,
wenn er sich aus den Grundtautologien, also
- den aussagenlogischen syntaktischen Tautologien,
- der Existenzeinführung im Sukzedens,
durch sukzessive Anwendung der Ableitungsregeln
Modus ponens
und der Existenzeinführung im Antezedens
erhalten lässt.
Die Abbildung
heißt arithmetisch repräsentierbar, wenn es einen
-Ausdruck
in
freien Variablen
derart gibt, dass für alle
-Tupel
die Äquivalenz
genau dann, wenn
gilt.
Eine unter aussagenlogischen Ableitungen abgeschlossene Teilmenge der
modallogischen Sprache
heißt
(formale) Modallogik.
Lösung
- Es sei
eine
geordnete Menge
mit der Eigenschaft, dass jede
total geordnete
Teilmenge
eine
obere Schranke
in
besitzt. Dann gibt es in
maximale Elemente.
- Es sei
ein Symbolalphabet,
eine Menge an
-Ausdrücken und
ein weiterer
-Ausdruck. Dann gilt
genau dann, wenn es eine endliche Teilmenge
gibt mit
.
- Es sei
eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge
(also die Menge der zugehörigen Gödelnummern)
sei
schwach repräsentierbar
in
. Dann gibt es einen arithmetischen Satz
derart, dass weder
noch seine Negation
aus
ableitbar ist.
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.
- Die Batterie für die Taschenlampe reicht für genau
Stunden. Können alle vier die Höhle verlassen?
- Die Batterie für die Taschenlampe reicht für genau
Stunden. Können alle vier die Höhle verlassen?
Lösung Höhle/Taschenlampe/Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Es sei
eine
(nichtleere)
Aussagenvariablenmenge
und
-
![{\displaystyle {}\operatorname {Bel} \,{\left(V\right)}=\operatorname {Abb} \,{\left(V,\{0,1\}\right)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dd989d7e370a051c917c092042f6c6f9b80c754)
die Menge aller Wahrheitsbelegungen auf
. In dieser Aufgabe untersuchen wir
und die Abbildung
-
Dabei spielen die beiden folgenden Teilmengen eine Rolle.
Es sei
die folgendermaßen festgelegte Teilmenge. Eine Abbildung
gehört genau dann zu
, wenn es eine endliche Teilmenge
derart gibt, dass
ist
(dies ist in Aufgabenteil 2 zu erläutern).
Es sei
die durch die folgenden Bedingungen rekursiv festgelegte Teilmenge.
a) Zu
gehört
-
zu
.
b) Wenn
ist, so gehört auch
zu
, wobei
die Vertauschungsabbildung bezeichnet.
c) Wenn
sind, so gehören auch
und
zu
.
- Ist
injektiv?
- Es sei
eine Teilmenge. Zeige, dass es eine natürliche surjektive Abbildung
-
und eine natürliche injektive Abbildung
-
- Zeige, dass die in (2) beschriebene Abbildung
-
die Evaluationen
, die Verknüpfung mit
und die Minima und Maxima respektiert.
- Man gebe bei
unendlich ein
an, das nicht zu
gehört.
- Es sei
endlich. Zeige
-
![{\displaystyle {}M=\operatorname {Abb} \,{\left(\operatorname {Bel} \,{\left(V\right)},\{0,1\}\right)}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c7e93359ac673765d5940bd59d8a7a1134202b8)
- Zeige
.
- Zeige, dass das Bild von
mit
übereinstimmt.
Lösung
ist nicht injektiv, da beispielsweise
und
Tautologien sind und daher beide auf die konstante Abbildung geschickt werden, die jeder Belegung den Wert
zuordnet.
- Es sei
eine Teilmenge. Es gibt die natürliche Abbildung
-
die jeder Belegung auf
die eingeschränkte Belegung auf der Teilmenge
zuordnet. Diese Abbildung ist surjektiv, da man jede Belegung auf
zu einer Belegung auf
fortsetzen kann, indem man auf
willkürlich Wahrheitswerte festlegt
(beispielsweise konstant gleich
).
Mit Hilfe dieser Abbildung ist durch
-
eine Abbildung festgelegt. Diese ist injektiv: wenn zwei Abbildungen
verschieden sind, so gibt es eine Belegung
mit
.
Dann gilt dies auch für eine Fortsetzung
von
auf ganz
, und somit sind die Bilder von
und von
in
verschieden.
- Es sei
. Dann ist für jede Belegung
-
![{\displaystyle {}\Phi _{W}(\operatorname {ev} _{p})(\lambda )=\operatorname {ev} _{p}(\lambda {|}_{W})=\lambda {|}_{W}(p)=\lambda (p)=\operatorname {ev} _{p}(\lambda )\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/320bd93985dc5350a3d322e0c87c896188b71d8c)
also ist
-
![{\displaystyle {}\Phi _{W}(\operatorname {ev} _{p})=\operatorname {ev} _{p}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/044e1111620f0ba772dafd35397244d4bb83e0e8)
Für
ist
![{\displaystyle {}{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa2a251b5bc783a0873d4990bc505678586ab4e1)
Für
ist
![{\displaystyle {}{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/481f3dc3d36f7715958c122244e3b62c0a40c89e)
und ebenso für das Minimum.
- Wir betrachten die Abbildung
, die die konstante Nullbelegung auf
und jede andere Belegung auf
abbildet. Wir müssen zeigen, dass diese Abbildung nicht von einer Abbildung aus
zu einer endlichen Teilmenge
herrührt. Es sei also
endlich gegeben. Da
unendlich ist, gibt es ein
,
.
Es sei
die Belegung auf
, die auf der Teilmenge
den Wert
hat und an
den Wert
(und an den anderen Variablen einen beliebigen Wert)
und
die konstante Nullbewertung auf
. Dann ist
und
.
Wegen
-
![{\displaystyle {}\lambda {|}_{W}=\lambda _{0}{|}_{W}=0\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f91a004408c76daf9911755a4d9b7bdf2de9a689)
besitzen aber die beiden auf
eingeschränkten Belegungen unter jedem
den gleichen Wert und somit ist
-
![{\displaystyle {}\psi \neq \varphi \,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa6611b5cde8b26364f4ac043fa0bdff6d794aee)
- Es sei
endlich. Die Belegungen auf
entsprechen den Teilmengen aus
, indem man
mit
identifiziert. Zu jeder Belegung
gibt es eine Abbildung
, die diese Belegung auf
und alle anderen Belegungen auf
abbildet. Dabei gilt
-
![{\displaystyle {}\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)}}\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/775002b8d6de950e8e056a909c77dc9e3d26cc25)
da der zweite Ausdruck für eine Belegung
genau dann den Wert
liefert, wenn für alle
die Beziehung
-
![{\displaystyle {}\operatorname {ev} _{p}(\delta )=\delta (p)=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2662d32bb1801b4ef8028344a02b54a9e69ae55)
genau dann gilt, wenn
ist, was genau bei
der Fall ist. Da die
zu
gehören und
unter der Verknüpfung mit
und unter den Minima von
(endlich vielen)
Abbildungen abgeschlossen ist, gehören die
zu
.
Ein Abbildung
ist dadurch festgelegt, für welche Belegungen sie den Wert
ergibt. Wenn
,
,
diese Belegungen sind, so ist
-
![{\displaystyle {}\varphi ={\max {\left(\varphi _{\lambda _{i}},i\in I\right)}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42f151d28815c9fe2c72fd27d92c3402a17cd2a4)
Da
unter den Maxima von
(endlich vielen)
Abbildungen abgeschlossen ist, gehört
zu
.
- Es sei zuerst
. Dann gibt es eine endliche Teilmenge
mit
. Nach Teil (5), angewendet auf
, gehört
zu der in
mit den gleichen Rekursionsvorschriften erzeugten Menge
und damit zu
. Wenn umgekehrt
ist, so wird
rekursiv erzeugt. Dabei gehen nur endlich viele Startglieder
ein. Den Konstruktionsprozess, der zu
führt, kann man daher auch über der endlichen Menge
durchführen, und somit ist
nach Teil (3).
- Den Nachweis, dass zu jedem
das Bild
zu
gehört, führen wir rekursiv über den Aufbau von
. Zu einer Aussagenvariablen
ist
-
![{\displaystyle {}\Psi (p)=\operatorname {ev} _{p}\in M\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/464a463c46a596c37c19558f21818e81c0a27bcc)
Zu
ist
-
![{\displaystyle {}\Psi (\neg \alpha )=\tau \circ \Psi (\alpha )\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc0e51cfadc8729a5a30d035779e3bc890e779f1)
wenn also
nach
abgebildet wird, so auch die Negation. Wegen
-
![{\displaystyle {}\Psi (\alpha \wedge \beta )={\min {\left(\Psi (\alpha ),\Psi (\beta )\right)}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ecb36a5faf604277775a2e2f739a56f8db626dc)
und
-
![{\displaystyle {}\Psi (\alpha \vee \beta )={\max {\left(\Psi (\alpha ),\Psi (\beta )\right)}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84af7083109e906242620e0114a053581fa29f20)
werden mit
und
auch die Konjunktion und die Disjunktion nach
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
gleich bleibt, werden mit den Bestandteilen auch
und
nach
abgebildet.
Zum Nachweis, dass jede Abbildung
zum Bild gehört, gehen wir rekursiv über den Aufbau von
vor. Für die Evaluationen
gilt
-
![{\displaystyle {}\Psi (p)=\operatorname {ev} _{p}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0597650628088bb11ef69626bda535ad70a4f017)
Wenn
zum Bild gehört, sagen wir
-
![{\displaystyle {}\Psi (\alpha )=\varphi \,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe1f48d4f244e6d38b47875e2852f751d0d6ef33)
so gehört wegen
-
![{\displaystyle {}\Psi (\neg \alpha )=\tau \circ \varphi \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c677f2d0a338a47099d783a4e1abe61ef89f61b)
auch
zum Bild. Wenn
und
zum Bild gehören, sagen wir
-
![{\displaystyle {}\Psi (\alpha )=\varphi \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86888b6d6ce3bd4bd1eeb83b4c5f2fa7d72eb661)
und
-
![{\displaystyle {}\Psi (\beta )=\theta \,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f4667554fd19f0af5a7a08e3fc663fe9c7ed613)
so gehören wegen
-
![{\displaystyle {}\Psi (\alpha \wedge \beta )={\min {\left(\varphi ,\theta \right)}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a4654ed66ee17a61b21101eab77a16649c7d63b)
und
-
![{\displaystyle {}\Psi (\alpha \vee \beta )={\max {\left(\varphi ,\theta \right)}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f0ee790f711462c8768ace6363d2414e6ac62b6)
auch das Minimum und das Maximum dazu.
Es sei
eine endliche Menge an Aussagen. Skizziere ein Entscheidungsverfahren, mit dem man feststellen kann, ob
widersprüchlich
ist oder nicht.
Lösung
In den endlich vielen Ausdrücken
von
kommen insgesamt nur endlich viele Aussagenvariablen vor, sagen wir
. Für jede
-Kombination
-
![{\displaystyle {}\gamma =\pm p_{1}\wedge \ldots \wedge \pm p_{k}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1bc594d1838257cbe3f94933ad04fe22d9de3b1)
untersucht man, ob
widersprüchlich ist. Da durch
jede Aussagenvariable entweder positiv oder in ihrer Negation aus
ableitbar ist, kann man für jedes
überprüfen, ob
aus
ableitbar ist. Wenn die durch
gegebene Belegung sämtliche
erfüllt, so hat man eine Belegung gefunden, die zeigt, dass
erfüllbar und damit widerspruchsfrei ist. Im andern Fall stellt sich heraus, dass zu jedem
mindestens ein
die Belegung falsch bekommt. Nach
Aufgabe 5.28 (Einführung in die mathematische Logik (Osnabrück 2021))
ist
oder
ableitbar, wobei im gegebenen Fall nur die zweite Möglichkeit
-
verbleibt. Wegen
erhält man also
-
Da dies für jede Kombination
gilt, kann man mit mehrfacher Anwendung der Fallunterscheidungsregel
-
zeigen. In diesem Fall ist also
widersprüchlich.
Es sei
eine Aussage(nform),
in die man eine natürliche Zahl einsetzen kann. Diskutiere den Unterschied zwischen den beiden Aussagen
-
Was ist die mathematische Relevanz der beiden Aussagen?
Lösung Vollständige Induktion/Allquantor/Aufgabe/Lösung
Lösung
Es sei
die in Frage stehende Struktur mit der angegebenen Addition und Multiplikation. Die Abbildung
-
die
auf
,
auf
,
auf
und jede weitere Zahl auf
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
nach
. Die Abziehregel gilt in
nicht, da
-
![{\displaystyle {}1+v=v=2+v\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d1f40029942a01b8e898f94f768f2e5479c646)
ist, aber
-
![{\displaystyle {}1\neq 2\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbb65c4897afce3b8b1d11cb6390850d5ba4001d)
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Erstelle ein Programm für eine Registermaschine, das abwechselnd
und
ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Sprungbefehl verwendet.
Lösung
Die Register
und
seien zu Beginn leer.
-
-
-
-
-
-
Am Anfang wird der erste Register auf
erhöht und dies wird im zweiten Befehl ausgedruckt. Im dritten Befehl wird dieser Registerinhalt auf
reduziert und dies im vierten Befehl ausgedruckt. Mit dem fünften Befehl wird auf den ersten Befehl umgeleitet, da der zweite Register stets auf
bleibt, so dass sich alles wiederholt.
Beweise den Fixpunktsatz der Prädikatenlogik.
Lösung
Wir betrachten die Abbildung
-
die durch
-
![{\displaystyle 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}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a651738f9aeff59de513fd406a2262f324bb6e)
festgelegt ist. Bei der Berechnung von
wird also zuerst geschaut, ob das erste Argument, also
, die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist
,
unabhängig von
. Falls ja, so ist also
mit
.
In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also
, ersetzt, wobei man einen Satz
erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung
. In diesem Fall ist also
.
Diese Erläuterungen zeigen zugleich, dass
berechenbar
ist.
Da
nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck
mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen
die Beziehungen
(wir können annehmen, dass
widerspruchsfrei
ist, da andernfalls das Resultat trivial ist)
-
-
und
(für jede Belegung
für
und
)
-
Den Fixpunkt zu einem vorgegebenen
erhalten wir nun durch eine trickreiche Anwendung von
. Wir setzen
-
![{\displaystyle {}s:=\forall z{\left(\varphi (x,x,z)\rightarrow \alpha (z)\right)}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75f7fa03f9670a1820e52138339c7c8d4a2e7852)
Der Ausdruck
besitzt die Gödelnummer
. Wir behaupten nun, dass der Satz
-
![{\displaystyle {}q:=s{\frac {GN(s)}{x}}=\forall z{\left(\varphi (GN(s),GN(s),z)\rightarrow \alpha (z)\right)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b59d6d76565e50a8276b63fb5355a834877ca4d)
die zu beweisende Ableitungsbeziehung
erfüllt.
Der Ausdruck
besitzt die einzige freie Variable
, daher gilt
-
![{\displaystyle {}F(GN(s),GN(s))=GN{\left(s{\frac {GN(s)}{x}}\right)}=GN(q)\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee7e54cce1d33173fc35558c47445b43543a933d)
Aufgrund der Repräsentierungseigenschaft ist daher
-
Aus der Allaussage
erhält man durch
Spezialisierung
(man ersetzt die Variable
durch den Term
)
-
Da das Antezedens der rechten Implikation aus
ableitbar ist, folgt
-
Dies besagt also die Ableitbarkeit der Hinrichtung.
Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu
-
Durch
Substitution
ergibt sich
-
und somit nach einer prädikatenlogischen Umformulierung
-
Da hierbei
keine freie Variablen besitzt, ist auch
-
und das Sukzedens ist gerade
, so dass auch die Rückrichtung ableitbar ist.
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung
Lösung /Aufgabe/Lösung