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

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Punkte 3 3 1 2 5 1 2 2 8 3 4 0 10 0 4 0 48




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Mersennesche Primzahl.
  2. Die (rekursiv definierte) Gültigkeit eines prädikatenlogischen -Ausdruckes bei einer -Interpretation auf einer Menge .
  3. Ein Isomorphismus

    zwischen zwei -Strukturen und .

  4. Die -Aufzählbarkeit einer Teilmenge .
  5. Das modallogische Transitivitätsaxiom.
  6. Die rekursive Definition der Gültigkeit eines modallogischen Ausdrucks in einem modallogischen Modell .


Lösung

  1. Eine Primzahl der Form heißt Mersennesche Primzahl.
  2. Die -Ausdrücke werden folgendermaßen als gültig charakterisiert (dabei seien Terme und Ausdrücke).
    1. , wenn .
    2. , wenn .
    3. , wenn nicht gilt.
    4. , wenn und gilt.
    5. , wenn die Gültigkeit die Gültigkeit impliziert.
    6. , wenn es ein gibt mit .
    7. , wenn für alle die Beziehung gilt.
  3. heißt -Isomorphismus, wenn bijektiv ist und sowohl als auch die Umkehrabbildung ein -Homomorphismus ist.

  4. Man sagt, dass -aufzählbar ist, wenn es ein Programm für eine Registermaschine gibt, die bei Eingabe von nach und nach genau die Zahlen aus ausdruckt.
  5. Das modallogische Axiomenschema

    nennt man Transitivitätsaxiom.

  6. Die Gültigkeit wird rekursiv wie folgt definiert: Sei der modallogische Ausdruck schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt

    genau dann, wenn in jeder von aus erreichbaren Welt die Beziehung

    gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).
  2. Das Koinzidenzlemma.
  3. Das Unvollständigkeitslemma.


Lösung

  1. Es sei eine abzählbare Menge an Aussagenvariablen und eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Dann kann man durch sukzessive Hinzunahme von entweder oder und durch Abschluss unter der Ableitungsbeziehung zu einer maximal widerspruchsfreien Teilmenge ergänzen.
  2. Es sei ein Symbolalphabet erster Stufe und eine Teilmenge. Es sei ein -Term und ein -Ausdruck. Es seien zwei -Interpretationen und in einer gemeinsamen Grundmenge gegeben, die auf identisch seien. Dann gelten folgende Aussagen.
    1. Es ist .
    2. Es ist genau dann, wenn .
  3. 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.


Aufgabe (1 Punkt)

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

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


Lösung

.


Aufgabe (2 Punkte)

Beweise die aussagenlogische Tautologie

aus den aussagenlogischen Axiomen.


Lösung

Es ist

nach Fakt ***** und

nach Axiom *****  (4). Modus Ponens liefert


Aufgabe (5 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Es sei widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable gelte oder . Zeige, dass dann maximal widerspruchsfrei ist.


Lösung

Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes die Alternative oder gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für eine Aussagenvariable ist dies Teil der Voraussetzung. Bei folgt wegen die Aussage aus der Induktionsvoraussetzung, da abgeschlossen unter Ableitungen ist. Sei nun . Bei und ist wegen der Ableitungsabgeschlossenheit auch . Wenn hingegen ist, so folgt nach Induktionsvoraussetzung . Aufgrund der Tautologie ergibt sich . Der Beweis für die Implikation verläuft ähnlich, siehe Aufgabe *****.

Zum Nachweis, dass maximal widerspruchsfrei ist, sei angenommen. Nachdem, was wir eben bewiesen haben, gilt dann . Dann ist aber und somit ist diese erweiterte Menge widersprüchlich.


Aufgabe (1 Punkt)

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.


Lösung

Es gibt eine Hochzeit, auf der Lucy Sonnenschein nicht tanzt.


Aufgabe (2 Punkte)

Es seien Variablen und ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. ,
  8. ,
  9. ,
  10. ,
  11. ,
  12. .


Lösung

Terme sind , die anderen sind keine Terme.


Aufgabe (2 Punkte)

Man erläutere für einen Ableitungskalkül den Unterschied zwischen einer syntaktischen Grundtautologie und einer Ableitungsregel.


Lösung Ableitungskalkül/Tautologie und Regel/Aufgabe/Lösung


Aufgabe (8 Punkte)

Es seien Variablen, Terme und ein Ausdruck in einer prädikatenlogischen Sprache. Es seien neue Variablen, die weder in noch in noch in vorkommen. Zeige, dass

allgemeingültig ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen (von links nach rechts) zu lesen ist.


Lösung

Sei eine Interpretation mit

Nach dem Substitutionslemma bedeutet dies

Von der anderen Seite her ist

mit dem Substitutionslemma äquivalent zu

Dies ist äquivalent zu

und wegen kann man dies als

schreiben. Wir nennen die Interpretation links . Mit dem Substitutionslemma ist dies äquivalent zu

Nach dem Substitutionslemma für Terme ist

Dabei ist

und somit ist

Zusammengefasst ist also

Die Interpretation links nennen wir wieder . Nach dem Substitutionslemma ist

Dabei ist

und wir haben

Daher ist

Also ist insgesamt

und

Nach dem Koinzidenzlemma ist dies äquivalent zu

da und in nicht vorkommen. Dies stimmt mit der eingangs erzielten Formulierung überein.


Aufgabe (3 Punkte)

Zeige


Lösung

Die Alleinführung im Antezedens ergibt

und

und daraus zusammen mit Fakt *****  (2)

Die Variable ist sowohl vorne als auch in gebunden. Daher ergibt die Alleinführung im Sukzedens


Aufgabe (4 Punkte)

Zeige, dass die Vorgängereigenschaft

aus der Menge der Peano-Axiome für den Nachfolger folgt.


Lösung

Es sei eine Menge mit und einer Abbildung , die die erststufigen Peano-Axiome für die Nachfolgerabbildung erfüllt, und es sei

Wir möchten zeigen. Dabei handelt es sich um einen erststufig mit der Symbolmenge formulierten Ausdruck, so dass wir ihn durch Induktion beweisen können. Für aus ist der Vordersatz falsch und die Gesamtaussage richtig. Sei nun und die Aussage für richtig, d.h. es gelte . Dann gilt direkt

und somit wiederum . Die Gesamtaussage ist also auch für richtig und es ergibt sich die Gültigkeit für alle .


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (10 Punkte)

Beweise den Fixpunktsatz der Prädikatenlogik.


Lösung

Wir betrachten die Abbildung

die durch

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

Der Ausdruck besitzt die Gödelnummer . Wir behaupten nun, dass der Satz

die zu beweisende Ableitungsbeziehung erfüllt.
Der Ausdruck besitzt die einzige freie Variable , daher gilt

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.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Es sei ein -modallogisches System, in dem zusätzlich das Transitivitätsaxiom gelte. Ferner sei ein modallogischer Ausdruck, für den

gelte. Zeige für einen beliebigen Ausdruck die Ableitbarkeit


Lösung

Aus der Fixpunkteigenschaft

ergibt sich insbesondere

Mit Fakt *****  (1) folgt

Mit dem Transitivitätsaxiom und dem Kettenschluss folgt

Dies zusammen mit der Tautologie

ergibt

Mit Fakt *****  (4) haben wir

und somit

Für ein beliebiges ist nun

und somit durch Fakt *****  (1)

und insgesamt

was durch Kontraposition die Behauptung ergibt.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung