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



Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Punkte 3 3 2 2 2 2 5 2 3 7 2 8 4 5 3 3 2 2 4 64




Aufgabe (3 Punkte)


Lösung

  1. Die Menge heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks die Menge widersprüchlich macht.
  2. Ein System aus offenen Teilmengen von heißt Filter, wenn folgende Eigenschaften gelten ( seien offen).
    1. .
    2. Mit und ist auch .
    3. Mit und ist auch .
  3. Die Terminterpretation wird induktiv über den Aufbau der Terme für jeden - Term definiert.
    1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
    2. Wenn Terme mit Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.
  4. Die Teilmenge heißt funktional abgeschlossen, wenn für jede Konstante das Element zu gehört und für jedes -stellige Funktionssymbol und beliebige Elemente auch zu gehört.
  5. Die Theorie heißt vollständig, wenn für jeden Satz gilt oder .
  6. Unter einem modallogischen Modell versteht man einen gerichteten Graphen zusammen mit einer Wahrheitsbelegung für die Aussagenvariablen für jeden Knotenpunkt .


Aufgabe (3 Punkte)


Lösung

  1. Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die maximal widerspruchsfrei ist und Beispiele enthält. Dann ist die durch die kanonische Termidentifizierung gegebene Interpretation ein Modell für .
  2. Die Menge

    ist nicht -

    entscheidbar.
  3. Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht - entscheidbar.


Aufgabe (2 Punkte)

wurde ermordet. Es gelten folgende Sachverhalte.

  1. Der Mörder ist oder oder oder .
  2. Wenn der Mörder ist, dann ist nicht der Mörder oder ist der Mörder.
  3. sind alle verschieden.
  4. Es gibt genau einen Mörder.
  5. Wenn nicht der Mörder ist, dann ist nicht der Mörder.
  6. ist genau dann der Mörder, wenn der Mörder ist.

Wer ist der Mörder?


Lösung

Aus (6), (3) und (4) folgt, dass und beide nicht der Mörder sind, denn sonst wären beide der Mörder. Nach (5) ist somit auch nicht der Mörder. Wegen (1) muss also der Mörder sein. ((2) wird nicht verwendet.)


Aufgabe (2 Punkte)

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

w w w w
w w f f
w f w w
w f f f
f w w f
f w f w
f f w f
f f f w


Lösung


Aufgabe (2 Punkte)

Erläutere die Beziehung zwischen dem Modus ponens und


Lösung Modus ponens/Interne Version/Erläuterung/Aufgabe/Lösung


Aufgabe (2 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Begründe die Widerspruchsregel für die Ableitungsbeziehung: Wenn und , dann ist auch .


Lösung

Es gilt

nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (5). Nach der Voraussetzung und Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (5) ergibt sich daraus .


Aufgabe (5 (2+2+1) Punkte)

Es sei ein einstelliges Funktionssymbol, und seien zweistellige Funktionssymbole und seien Variablen.

Wir betrachten die folgenden Modelle (wobei die Grundmenge bezeichnet).

a) , ist die Quadrierung, die Addition und die Multiplikation.


b) , ist das Differenzieren von Funktionen, die Multiplikation und die Addition von Funktionen. Bestimme, ob in diesen Modellen die folgenden Aussagen wahr werden.


Lösung

Im ersten Modell ist als und als zu interpretieren, wobei reelle Zahlen sind.

  1. Die Gleichung

    gilt in definitiv nicht für alle reelle Zahlen, beispielsweise gilt sie für und nicht.

  2. Wir schreiben die Gleichung als

    Für ein beliebiges aber fixiertes ist der Ausdruck links ein normiertes Polynom vom Grad in . Dieses besitzt nach dem Zwischenwertsatz eine Nullstelle, deshalb ist die Aussage wahr.

  3. Zu jedem ist der Ausdruck links aus (2) ein Polynom in vom Grad , also definitiv nicht das Nullpolynom, die Aussage ist also falsch.

Im zweiten Modell ist als und als zu interpretieren, wobei unendlich oft differenzierbare Funktionen sind. Dies ist die Produktregel für die Ableitung, also wahr für beliebige . Damit gilt insbesondere auch (2) und (3), da es ja unendlich oft differenzierbare Funktionen gibt.


Aufgabe (2 Punkte)

Es sei ein Symbolalphabet erster Stufe mit der Variablenmenge

gegeben und eine - Interpretation in der Menge mit

Bestimme die Werte von bei der Interpretation auf .


Lösung

Es ist

Ferner ist dieser Ausdruck von innen nach außen, bzw. von links nach rechts zu lesen, also als

Daher ist


Aufgabe (3 Punkte)

Es seien Variablen (mit der angegebenen Reihenfolge), eine Konstante und ein einstelliges Funktionssymbol.

  1. Bestimme
  2. Bestimme
  3. Bestimme


Lösung

Die zu substituierende Variable kommt im Ausdruck nicht frei vor. Somit ist jedenfalls für den jeweiligen Term

Da die relevante Termmenge leer ist, ist

Also ist


Aufgabe (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.


Lösung

Es sei allgemeingültig, d.h.

für jede - Interpretation . Wir müssen zeigen, dass dann auch allgemeingültig ist (unter den gegebenen Voraussetzungen). Es sei dazu eine Interpretation mit

Aufgrund der Modellbeziehung bedeutet dies, dass es ein (aus der Grundmenge der Interpretation) mit

gibt. Die Variable kommt nach Voraussetzung in nicht frei vor, d.h. bei , dass in nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten

Diese Aussage gilt trivialerweise auch bei . Damit gilt auch

Wir schreiben dies (etwas künstlich) als

Darauf können wir das Substitutionslemma (für die Interpretation und den Term ) anwenden und erhalten

Wegen der vorausgesetzten Allgemeingültigkeit von folgt

Da in nicht frei vorkommt, liefert das Koinzidenzlemma


Aufgabe (2 Punkte)

Zeige, dass in einem kommutativen Halbring die Beziehung gilt.


Lösung

Dies ergibt sich aus


Aufgabe (8 (1+2+3+2) Punkte)

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Es sei eine - Interpretation mit der Grundmenge und es sei mit der zugehörigen Äquivalenzrelation auf der Termmenge .

  1. Zeige, dass genau dann gilt, wenn gilt.
  2. Zeige, dass es eine injektive Abbildung

    mit

    gibt.

  3. Zeige, dass ein - Homomorphismus ist, wenn die Quotientenmenge mit der kanonischen - Struktur versehen wird.
  4. Es sei die kanonische Interpretation auf . Es sei vorausgesetzt, dass die Terminterpretation für surjektiv sei. Zeige, dass genau dann gilt, wenn gilt.


Lösung

  1. Es ist genau dann, wenn ist, und dies ist genau dann der Fall, wenn gilt, was nach Definition bedeutet.
  2. Die Termabbildung

    besitzt nach Teil (1) die Eigenschaft, dass äquivalente Terme auf das gleiche Element abgebildet werden. Dies bedeutet nach Lemma 11.13 (Diskrete Mathematik (Osnabrück 2020)), dass es eine Abbildung

    mit gibt. Da nichtäquivalente Terme nach Teil (1) unter auf verschiedene Elemente abgebildet werden, werden verschiedene Klassen unter auf verschiedene Elemente abgebildet und somit ist injektiv.

  3. Sei

    Für eine Konstante ist

    Für ein -stelliges Funktionssymbol und Termklassen ist

    Es sei nun eine -stellige Relation und Termklassen gegeben und sei die Gültigkeit von in vorausgesetzt. Dies bedeutet, dass ist. Somit ist , was bedeutet. Somit ist . Es liegt also ein - Homomorphismus vor.

  4. Nach Definition von ist genau dann, wenn gilt. Nach Lemma 14.5 (Einführung in die mathematische Logik (Osnabrück 2021)) ist maximal widerspruchsfrei und enthält Beispiele und nach dem Satz von Henkin ist


Aufgabe (4 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe zum Symbolalphabet .


Lösung

Die Äquivalenzklassen sind

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 Abbildung, die in der ersten Komponente die Identität und in der zweiten Komponente und vertauscht, ist ein Automorphismus. Daher sind die in den zweielementigen Klassen angegebenen Elemente zueinander elementar äquivalent. Es ist also noch zu zeigen, dass die vier Klassen voneinander trennbar sind. Die in der angegebenen Sprache formulierbare Eigenschaft wird nur durch das neutrale Element erfüllt und ist somit ein charakterisierender Ausdruck für . Die Eigenschaft

charakterisiert die zweite Klasse. Die Eigenschaft

charakterisiert die dritte Klasse. Die Eigenschaft

(der letzte Teil der Konjunktion ist nicht nötig) charakterisiert die vierte Klasse.


Aufgabe (5 Punkte)

Man entwerfe ein Programm für eine Registermaschine, das bei der Eingabe im ersten Register den Rest bei der Division mit Rest von durch ausgibt.


Lösung Registermaschine/Modulo 5/Rest/Aufgabe/Lösung


Aufgabe (3 (2+1) Punkte)

  1. Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, arithmetisch repräsentierbar ist.
  2. Formuliere in der arithmetischen Sprache, dass die keine Summe von drei Quadraten ist.


Lösung

  1. Wir betrachten die Ausdruck

    in der einen freien Variablen . Offenbar kann man eine natürliche Zahl genau dann als Summe von drei Quadraten schreiben, wenn innerhalb von der Ausdruck gilt.

  2. Eine Formulierung ist


Aufgabe (3 Punkte)

Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.


Lösung

 Wir nehmen an, dass vollständig ist. Da aufzählbar ist, ist nach Lemma 21.9 (Einführung in die mathematische Logik (Osnabrück 2021)) aufzählbar und nach Satz 21.10 (Einführung in die mathematische Logik (Osnabrück 2021)) auch entscheidbar. Da Repräsentierungen erlaubt, ist insbesondere repräsentierbar. Daher sind die Voraussetzungen von Lemma 23.1 (Einführung in die mathematische Logik (Osnabrück 2021)) erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.


Aufgabe (2 Punkte)

Zeige, dass in der - Modallogik das Schema

ableitbar ist.


Lösung

Aus der aussagenlogischen Tautologie

ergibt sich mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)

Wegen Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) gilt

Der Kettenschluss liefert


Aufgabe (2 Punkte)

Wir arbeiten mit den Aussagenvariablen . Im Weltpunkt gelte

und im Weltpunkt gelte

Bestimme die Wahrheitswerte von in den beiden Weltpunkten.


Lösung

Wegen und gilt . Wegen gilt und somit gilt in der Vordersatz der Aussage. Wegen gilt . Daher ist der Nachsatz der Aussage falsch in und somit ist die Gesamtaussage dort falsch.

Von aus ist nur erreichbar ist, dort gilt also auch . Damit gilt der Nachsatz und damit die Gesamtaussage in .


Aufgabe (4 Punkte)

Beweise den Vollständigkeitssatz der Modallogik.


Lösung

Die Hinrichtung ergibt sich aus Lemma 26.9 (Einführung in die mathematische Logik (Osnabrück 2021)). Für die Rückrichtung nehmen wir

an. Dann ist

(aussagenlogisch) nicht widersprüchlich und wir müssen zeigen, dass durch ein -modallogisches Modell erfüllbar ist. Wir betrachten dazu das - universelle modallogische Modell , in dem (in jedem Weltpunkt) gilt. Nach Lemma 27.1 (Einführung in die mathematische Logik (Osnabrück 2021)) gibt es eine maximal widerspruchsfreie -Ausdrucksmenge , die wir als Welt in betrachten können. Nach Lemma 27.6 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt , was insbesondere die Gültigkeit von in zeigt.