Lösung
- Die Termmenge ist diejenige Teilmenge
der Wörter
über dem Termalphabet
, die durch die folgenden rekursiven Vorschriften festgelegt wird.
- Jede Variable
ist ein Term.
- Jede Konstante
ist ein Term.
- Für jedes
und
Terme
ist auch
ein Term.
- Die Menge
heißt
maximal widerspruchsfrei,
wenn sie
widerspruchsfrei
ist und wenn jede Hinzunahme eines jeden Ausdrucks
die Menge widersprüchlich macht.
- Die Multiplikation mit
ist diejenige aufgrund von
Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021))
eindeutig bestimmte Abbildung
-
für die
-
gilt.
- Die Befehle für eine Registermaschine sind
(dabei bezeichnen
Register und
Befehlszeilen).
(erhöhe den Inhalt des Registers
um
, d.h. um einen Strich).
(reduziere den Inhalt des Registers
um
, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
(wenn das
-te Register leer ist, so gehe zum Befehl
, andernfalls zum nächsten Befehl).
- Drucke
(drucke den Inhalt des ersten Registers).
- Halte an.
- Das
modallogische Axiomenschema
-
nennt man
Löb-Axiom.
- Unter einem
modallogischen Modell
versteht man einen
gerichteten Graphen
zusammen mit einer
Wahrheitsbelegung
für die
Aussagenvariablen
für jeden Knotenpunkt
.
Formuliere die folgenden Sätze.
- Das
Lemma von Zorn.
- Der
Vollständigkeitssatz für Tautologien
(Prädikatenlogik).
- Der
zweite Gödelsche Unvollständigkeitssatz.
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
und
ein
-Ausdruck. Dann ist
genau dann eine
ableitbare Tautologie,
wenn
allgemeingültig
ist.
- Es sei
eine arithmetische Ausdrucksmenge, die
widerspruchsfrei
und
entscheidbar
sei und die
Peano-Arithmetik
umfasse. Dann ist die Widerspruchsfreiheit
nicht aus
ableitbar, d.h. es ist
-
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“.
- Ist die Aussage von Frau Schummele logisch korrekt?
- 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
- Die Aussage ist logisch korrekt.
- 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.
- Löse das folgende Minisudoku
-
- Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
- Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?
Lösung
-
- Wir gehen von
-
aus. In der dritten Stelle der zweiten Zeile muss eine
sein und somit muss rechts oben eine
stehen. Dies ergibt
-
An der vierten Stelle der dritten Zeile muss eine
stehen. In der vierten Zeile muss an der dritten Stelle eine
und somit in der vierten Zeile an der ersten Stelle eine
stehen. Dies ergibt
-
Dies erzwingt
-
An der zweiten Stelle der ersten Zeile muss eine
stehen, dies ergibt dann die eindeutige Lösung
-
-
- Direkter Beweis: Durch Betrachten der schon gefundenen Zahlen erschließt man, welche Zahl in ein bestimmtes Feld gesetzt werden muss.
- Beweis durch Fallunterscheidung: Man weiß, dass in einem gewissen Feld nur noch zwei Zahlen, sagen wir
oder
möglich sind. Wenn man nun in beiden Fällen, dass es sich um
oder um
handelt, jeweils erschließen kann, dass in einem bestimmten anderen Feld die Zahl
stehen muss, so steht diese Zahl fest.
- Beweis durch Widerspruch: Man weiß, dass in einem gewissen Feld nur noch zwei Zahlen, sagen wir
oder
möglich sind. Man nimmt nun an, dass es sich um
handelt. Wenn man nun erschließen kann, dass sich daraus an irgendeiner Stelle ein Widerspruch ergibt, so kann die Belegung durch
nicht gelten und
ist richtig.
Beweise durch Induktion über den rekursiven Aufbau der Sprache
, dass in jeder Aussage
die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.
Lösung
Wenn
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
und vorausgesetzt, dass die Anzahl der linken und die Anzahl der rechten Klammern in
übereinstimmen. Dann besitzt
sowohl eine linke als auch eine rechte Klammer mehr als
, so dass die Anzahlen wieder übereinstimmen. Es sei nun
mit
und sei vorausgesetzt, dass
linke und auch rechte Klammern und
linke und auch rechte Klammern besitzt. Dann besitzt
linke und auch rechte Klammern.
Zeige, dass eine Regel der Form
Wenn
, dann
gelten kann, ohne dass
gilt.
Lösung
Lösung
Die Voraussetzung bedeutet, dass es Ausdrücke
mit
-
und mit
-
gibt. Daraus ergibt sich mit Hilfe
(der Regelversion)
von
Lemma 3.16 (Einführung in die mathematische Logik (Osnabrück 2021)) (2)
-
Es gilt die Tautologie
(Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))
(2),)
-
Aus der Regelversion dieses Axioms ergibt sich
-
Dies bedeutet
.
Es sei
eine Variablenmenge,
eine Konstante und
zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck
, der durch
-
gegeben ist.
- Zeige, dass
bei Interpretation in einem Körper
wahr wird, wenn man
als
und
als Subtraktion, Addition und Multiplikation interpretiert.
- Welcher wichtige mathematische Satz verbirgt sich dahinter?
Lösung
- Es sei ein Körper
mit Elementen
gegeben und sei vorausgesetzt, dass
-
![{\displaystyle {}(z-x)(z-y)+(w-u)(w-v)=0\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f971d72b53d574dd03db86147b94658ce72466e9)
ist. Unter Verwendung des Distributivgesetzes
(bzw. der zweiten binomischen Formel)
bedeutet dies
-
![{\displaystyle {}z^{2}-xz-yz+xy+w^{2}-uw-vw+uv=0\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46bb50adf99a660dacb64ce00436cbe74d875bf4)
Entsprechend ist
![{\displaystyle {}{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e47e66758d5bb2eae5430db8f2441c0ea3522441)
Wenn wir davon zweimal
abziehen, und zwar in der oben etablierten Form, so ändert sich der Wert nicht und dies ist gleich
![{\displaystyle {}{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/515be1b793114866ceb750af0b47687006b06a46)
was insgesamt die Behauptung ist.
- Es handelt sich bei
um den Satz des Pythagoras. Die sechs Variablen definieren drei Punkte in der Ebene
, sagen wir
-
Die Verbindungsvektoren sind dann
-
![{\displaystyle {}R-P={\begin{pmatrix}z\\w\end{pmatrix}}-{\begin{pmatrix}x\\u\end{pmatrix}}={\begin{pmatrix}z-x\\w-u\end{pmatrix}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4420b04296145e8e820a2d8de2339c99fe62fe0)
und
-
![{\displaystyle {}R-Q={\begin{pmatrix}z\\w\end{pmatrix}}-{\begin{pmatrix}y\\v\end{pmatrix}}={\begin{pmatrix}z-y\\w-v\end{pmatrix}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dd9ab61e5375a07075db253f15b3c292c84d714)
Das Skalarprodukt dieser beiden Vektoren ist
-
![{\displaystyle {}\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)\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d23d10c9ce7ea993d1ea2b3e46fe242a555684e)
Dass dies gleich
ist, bedeutet, dass diese beiden Vektoren aufeinander senkrecht stehen, dass also
ein rechtwinkliges Dreieck mit dem rechten Winkel an
bilden. Das Quadrat der Länge der Strecke von
nach
ist
![{\displaystyle {}{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66ec0c36852f0d92eaa6e27b9d5218e2694c4e59)
und entsprechend ist
-
![{\displaystyle {}d(P,R)^{2}=(x-z)(x-z)+(u-w)(u-w)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84e2820fc3b9e634cd39b5b2bf61e5cc515694f8)
und
-
![{\displaystyle {}d(Q,R)^{2}=(y-z)(y-z)+(v-w)(v-w)\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9902cf4bf0df5741b7fc6bc64cdfa966b4bfdb61)
Der Nachsatz drückt also die Längenbeziehung im rechtwinkligen Dreieck aus.
Beweise die Termaussage des Substitutionslemmas.
Lösung
Dies wird über den induktiven Aufbau der Terme bewiesen. (1). Für eine Konstante
ist die Aussage richtig, da ihre Interpretation unverändert ist. Für eine Variable
macht man eine Fallunterscheidung. Wenn
-
![{\displaystyle {}x=x_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f27a93dcd7644d471dfd62eede871874ec836f52)
mit einer der an der Substitution beteiligten Variablen ist, so ist
-
![{\displaystyle {}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})\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22dcc7dfe943c2bb2e59cdfbaefcf470d03fbc10)
Bei einer an der Substitution nicht beteiligten Variablen
ist
-
![{\displaystyle {}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)\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c67b42339d387e636a569b12a0c27bef28525134)
Wenn
ein
-stelliges Funktionssymbol ist und
Terme sind, für die die Gleichheit schon bekannt ist, so ist
![{\displaystyle {}{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de0c6247b02f6bc076c3fb89adb6873bed99cc24)
Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet
, dass ein
Untervektorraum
in einem
Vektorraum
über einem
Körper
vorliegt.
Lösung
Lösung
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
Lösung
Die Äquivalenzklassen sind
und
.
Die in der angegebenen Sprache formulierbare Eigenschaft
wird nur durch das neutrale Element erfüllt und ist somit ein charakterisierender Ausdruck für
. 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
auf
ab und die invertierbare Matrix
(wir fassen
als Vektorraum über
auf)
ergibt einen Automorphismus, der
auf
abbildet.
Lösung
Wir ordnen die endlich vielen, sagen wir
, Zahlen aus
in aufsteigender Reihenfolge, also
-
![{\displaystyle {}n_{1}<n_{2}<n_{3}<\cdots <n_{s-1}<n_{s}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30ae2748a59dd47851a4034fe18a16fb0ea57ea4)
Wir setzen
-
![{\displaystyle {}d_{1}:=n_{1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d007777b00a0848330df778e7d914e7c3b81a5a)
und
-
![{\displaystyle {}d_{i}:=n_{i}-n_{i-1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3aa79747dfe430f2953d715830f3001b6e363ffe)
für
.
Die
sind also einfach die Differenzen zwischen den aufeinanderfolgenden Zahlen aus
, und es ist
-
![{\displaystyle {}n_{i}=d_{1}+d_{2}+\cdots +d_{i}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/192cf1b771097560e6954bcceb06509f9e310955)
Wir erstellen das Programm mit Hilfe von
Programmblöcken der Länge
der Form
-
-
-
-
-
-
-
-
-
Der Inhalt von
wird also abwechselnd um
reduziert und abwechselnd wird gefragt, ob der Inhalt leer ist, wobei im leeren Fall auf die Befehlszeile
verwiesen, aber die allerletzte Abfrage des Blockes auf die
-te Befehlszeile verweist. Bei
-
![{\displaystyle {}d_{1}=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b45bd261f79cf9da3f8954164c0db3911b7e02bc)
besteht der erste Block allein aus
. Diese
Blöcke werden hintereinander geschrieben, und das Programm wird durch
-
-
abgeschlossen.
Die Wirkungsweise des Programms macht man sich folgendermaßen klar. Zu jedez zu testenden Zahl
gibt es ein eindeutiges
mit
-
![{\displaystyle {}n_{i-1}<n\leq n_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcf7fcc03a11ed76e5b0decc6a91b549ee7981a7)
(wobei
als
zu lesen ist)
oder aber
-
![{\displaystyle {}n>n_{s}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1639226ea326644bccd69236912fce0a6d209fd5)
In den ersten
Programmblöcken bleibt der Inhalt des Registers positiv, da ja insgesamt nur
-
![{\displaystyle {}n_{i-1}=d_{1}+\cdots +d_{i-1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48dcbf420aa6105c0f9111ba4762baf138b150e5)
von
abgezogen wird. Daher gelangt man in den entscheidenden
-ten Block. Wenn dieser Block begonnen wird, steht im Register der Wert
, und für diesen Wert gilt
-
![{\displaystyle {}0<n-n_{i-1}\leq n_{i}-n_{i-1}=d_{i}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d85bb8e9281e6f8e7cec586a26725c9fbc26e47)
Bei
-
![{\displaystyle {}n<n_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d25d617ad9c1652bdaf0cf96e1b10cdf39232818)
ist
-
![{\displaystyle {}n-n_{i}<d_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e904ab7008ec397fea44bb45934da560b382f895)
so dass durch das Abziehen in diesem Block die
erreicht wird, und zwar vor dem vorletzten Befehl des Blocks, so dass nach
umgeleitet wird. Dort wird um
erhöht
(was nur bei
benötigt wird)
und das Endergebnis ist nicht
, was korrekt ist.
Bei
-
![{\displaystyle {}n=n_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87229dafe8ab02bf8c352abd03b3dbcd01e09e9e)
ist
-
![{\displaystyle {}n-n_{i}=d_{i}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72d9621980f6d3b476c65c894022b474f23633a7)
so dass durch das Abziehen in diesem Block die
erreicht wird, und zwar genau im vorletzten Befehl des Blocks. Im nächsten Befehl wird nach
umgeleitet und das Programm hält an mit der
als Ausgabe, was auch korrekt ist. Bei
werden alle Blöcke ohne Umleitung durchlaufen, in
wird erhöht und anschließend wird angehalten mit einen positivem Inhalt des ersten Registers.
Es sei
-
eine
arithmetisch repräsentierbare
Abbildung. Zeige, dass zu jedem Punkt
die
Faser
-
![{\displaystyle {}F^{-1}(P)\subseteq \mathbb {N} ^{r}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9a64f3575eb6c692458c6f1a09d6e1272bef68b)
arithmetisch repräsentierbar
ist.
Lösung
Nach Voraussetzung gibt es einen
-Ausdruck
in
freien Variablen
derart, dass für alle
-Tupel
die Äquivalenz
genau dann, wenn
gilt. Es sei
-
![{\displaystyle {}P=(p_{1},\ldots ,p_{s})\in \mathbb {N} ^{s}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cdd02f0e31997e05fa530456552322e5c8fbb4d)
ein Punkt. Dabei gilt insbesondere für beliebige
die Gleichheit
genau dann, wenn
gilt. Diese Gleichung bedeutet, dass
zur Faser über
gehört. Daher ist der Ausdruck
-
![{\displaystyle {}\varphi :=\psi (x_{1},\ldots ,x_{r},p_{1},\ldots ,p_{s})\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34f943cd724e302b34da4429562feac592782fab)
in den freien Variablen
ein Ausdruck, der die Faser über
arithmetisch repräsentiert.
Zeige, dass eine aufzählbar axiomatisierbare Theorie
auch
-aufzählbar ist.
Lösung
Es sei
eine
-
aufzählbare
Satzmenge, die
axiomatisiert, und es sei
,
,
eine
-Aufzählung von
. Es sei
,
,
eine
-Aufzählung der prädikatenlogischen Tautologien aus
. Wenn ein Satz
aus
ableitbar ist, so gibt es eine endliche Auswahl
aus
(bzw. aus der gewählten Aufzählung)
derart, dass
-
eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem
wächst, das Gewünschte: Für jedes
notiert man die Tautologien
in der Form
-
![{\displaystyle {}\beta _{i}=\delta _{1}\wedge \ldots \wedge \delta _{s}\rightarrow \epsilon \,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5d7b3f4b52d4a0dba6f042c3eda6290f87e0f28)
Wenn
überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes
,
ob alle
zu
gehören. Falls ja, und wenn
ein Satz ist, so wird
notiert. Danach geht man zum nächsten
. Wenn man
,
erreicht hat, so geht man zu
, wobei man aber wieder bei
anfängt.