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

Aus Wikiversity


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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine maximal widerspruchsfreie Teilmenge zu einer Menge an Aussagenvariablen.
  2. Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.
  3. Die Interpretation der Terme zu einem Symbolalphabet in einer gegebenen - Interpretation auf einer Grundmenge .
  4. Ein atomarer Ausdruck in der Prädikatenlogik.
  5. Eine -berechenbare Funktion
  6. Das modallogische Reflexivitätsaxiom.


Lösung

  1. Die Teilmenge heißt maximal widerspruchsfrei, wenn widerspruchsfrei ist und jede echt größere Menge widersprüchlich ist.
  2. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
    1. Wenn und Terme sind, so ist
      ein Ausdruck.
    2. Wenn ein -stelliges Relationssymbol ist und Terme sind, so ist

      ein Ausdruck.

    3. Wenn und Ausdrücke sind, so sind auch

      Ausdrücke.

    4. Wenn ein Ausdruck ist und eine Variable, so sind auch

      Ausdrücke.

  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. Unter einem atomaren Ausdruck versteht man Ausdrücke der Form , wobei und Terme sind, und der Form , wobei ein -stelliges Relationssymbol ist und Terme sind.
  5. Die Funktion

    heißt -berechenbar, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe (in den ersten Registern) anhält und als (einzige) Ausgabe besitzt.

  6. Unter dem Reflexivitätsaxiom versteht man das modallogische Axiomenschema


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Division mit Rest in einem Peano-Halbring.
  2. Der Vollständigkeitssatz der Prädikatenlogik.
  3. Der erste Gödelsche Unvollständigkeitssatz.


Lösung

  1. Es sei ein Peano-Halbring und . Dann gibt es zu jedem eindeutig bestimmte mit , , und mit
  2. Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck. Dann gilt genau dann, wenn gilt.
  3. Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube. Dann ist unvollständig.


Aufgabe (1 Punkt)

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

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


Lösung

.


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

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

  1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
  2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
  3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
  4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr weiß man, dass Tage sockenzerstreut und Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr weiß man, dass Tage sockenzerstreut und Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.


Lösung

a) Zerstreutheit: Die sockenzerstreuten Tage sind jedenfalls zerstreut. Das Minimum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind . Das Maximum ergibt sich, wenn kein Tag gleichzeitig sockenzerstreut und schuhzerstreut war, das ergibt Tage.

Totale Zerstreutheit: Die total zerstreuten Tage sind insbesondere schuhzerstreut. Das Maximum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind Tage. Das Minimum ergibt sich, wenn kein Tag gleichzeitig schuh- und sockenzerstreut war, also .

b) Wegen

können alle Jahre des Tages zerstreut gewesen sein, also . Minimal waren Tage total zerstreut.

c) Es sei die Anzahl der sockenzerstreuten Tage, die Anzahl der schuhzerstreuten Tage, die Anzahl der zerstreuten Tage und die Anzahl der total zerstreuten Tage. Dann gilt die Formel

Beide Seiten der Formel sind additiv in den Tagen, sie muss also nur für einen Tag nachgewiesen werden. Wenn der Tag nicht zerstreut ist, steht beidseitig . Wenn der Tag sockenzerstreut ist, aber nicht schuhzerstreut (oder umgekehrt), so ist der Tag zerstreut, aber nicht total zerstreut, und beidseitig steht . Wenn der Tag total zerstreut ist, so steht beidseitig .


Aufgabe (3 Punkte)

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.


Lösung Wohldefiniertheit/Typisches Beispiel/Aufgabe/Lösung


Aufgabe (2 Punkte)

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


Lösung

Aus der Voraussetzung und der Konjunktionsregel (Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (1)) ergibt sich

Daraus und aus der Voraussetzung

ergibt sich mittels Modus ponens (Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (3))


Aufgabe (8 (3+5) Punkte)

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. Beweise die folgenden Aussagen.

  1. Es ist .
  2. Es ist genau dann, wenn (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus und auf den in frei vorkommenden Variablen identisch sind).


Lösung

(1). Wir führen Induktion über den Aufbau der -Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus betrachten. Für eine Variable (oder eine Konstante) aus ist nach Voraussetzung . Im Induktionsschritt können wir annehmen, dass ein -stelliges Funktionssymbol aus gegeben ist sowie -Terme , für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird in beiden Interpretationen durch die gleiche Funktion interpretiert. Daher ist


(2). Wir führen Induktion über den Aufbau der -Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol aus folgt die Aussage unmittelbar aus (1), da ja in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein -Ausdruck der Form gegeben, und es gelte . Dies bedeutet aufgrund der Modellbeziehung, dass es ein derart gibt, dass gilt. Die beiden umbelegten Interpretationen und stimmen auf den Symbolen aus und den in frei vorkommenden Variablen überein: Die Variable wird so oder so als interpretiert und die anderen freien Variablen aus sind auch in frei. Nach Induktionsvoraussetzung gilt und daher wiederum .


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Es seien einstellige Relationssymbole. Zeige, dass der Modus Darii, also die Aussage

im Prädikatenkalkül ableitbar ist.


Lösung

Es gilt die aussagenlogische Ableitbarkeit

Dies fassen wir als eine Aussage vom Typ

auf. Nach Aufgabe 11.7 (Einführung in die mathematische Logik (Osnabrück 2021)) gilt in dieser Situation auch

Nach Lemma 11.9 (Einführung in die mathematische Logik (Osnabrück 2021))  (3) ist

Dies zusammengenommen ergibt mit dem Kettenschluss

was im obigen Spezialfall die gewünschte Ableitbarkeit

liefert.


Aufgabe (6 (3+3) Punkte)

Es sei ein Modell für die Peano-Axiome für den Nachfolger.

  1. Zeige, dass fixpunktfrei ist, d.h. dass

    für alle .

  2. Zeige, dass periodenfrei ist. D.h. für jedes ist

    wobei

    die -fache Hintereinanderschaltung von bedeutet.


Lösung

  1. Wir zeigen die Aussage

    durch Induktion über . Bei

    ergibt sich unmittelbar aus dem Axiom, dass kein Nachfolger ist. Es sei die Aussage für richtig, also

    Die Gleichheit

    wäre in Verbindung mit der Induktionsvoraussetzung ein direkter Widerspruch zur Injektivität der Nachfolgerabbildung. Also ist

    und die Aussage ist bewiesen.

  2. Es sei nun und

    fixiert. Wir zeigen

    durch Induktion über . Bei ergibt sich

    da sonst der Nachfolger von wäre. Es sei die Aussage nun für richtig, also

    Nehmen wir an, dass die Gleichheit

    gilt. Wegen

    folgt aus der Injektivität der Nachfolgerabbildung direkt

    im Widerspruch zur Induktionsvoraussetzung. Also ist

    und die Aussage ist bewiesen.


Aufgabe (4 Punkte)

Zeige, dass es einen Peano-Halbring mit der Eigenschaft gibt, dass es darin ein Element gibt, das größer als jede natürliche Zahl in (also Zahlen der Form ) ist.


Lösung

Es sei die Menge der aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Wir betrachten die Ausdrücke mit

wobei rechts die -fache formale Summe der mit sich selbst steht. Es sei

Diese Menge ist widerspruchsfrei, da jede endliche Teilmenge davon widerspruchsfrei ist, da sie in mit einer hinreichend großen Belegung für erfüllbar ist. Nach Korollar 15.10 (Einführung in die mathematische Logik (Osnabrück 2021)) ist also auch erfüllbar, und es sei ein erfüllendes Modell. Es gibt dann in ein Element , wodurch belegt wird. Dieses ist dann von allen natürlichen Zahlen, die in natürlicherweise eingebettet sind, verschieden, und somit ist .


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

Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz bestreiten. Von einer solchen Runde seien die Mannschaften und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.

  1. Welche Information über die Platzierung kann man stets aus den Daten erschließen?
  2. Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
  3. unter welcher nicht?


Lösung

  1. Es gibt genau eine Mannschaft, die zweimal gewinnt, diese ist Weltmeister, und genau eine Mannschaft, die zweimal verliert, diese ist Vierter. Die beiden anderen Mannschaften gewinnen einmal und verlieren einmal und sind Zweiter oder Dritter.
  2. Wenn der Erste gegen den Vierten (die ja beide bekannt sind) spielt, so muss dieses Spiel ein Hauptfinale sein. Das komplementäre Spiel ist ebenfalls ein Halbfinale, das andere Spiel des Ersten muss das Finale und das andere Spiel des Vierten muss das Spiel um Platz drei sein. Somit sind alle Platzierungen bekannt.
  3. Wenn der Erste nicht gegen den Vierten spielt, so kann man den Zweiten nicht vom Dritten unterscheiden.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


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 (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (6 (4+2) Punkte)

  1. Skizziere ein modallogisches Modell, bei dem es verschiedene Weltpunkte mit

    und

    gibt.

  2. Was ist die minimale Anzahl von Welten in einem modallogischen Modell, in dem die Anforderungen aus 1) realisierbar sind.


Lösung

  1. Wir betrachten das Modell bestehend aus den vier Welten mit der Erreichbarkeitsrelation

    und der Belegung

    (die Belegung von auf ist irrelevant). Dann gilt

    da es für diese beiden Welten keine erreichbaren Welten gibt. In allen von aus erreichbaren Welten gilt somit und daher

    Ferner gilt

    wegen der Erreichbarkeit und

    wegen der Erreichbarkeit und auch

    also

    wegen der Erreichbarkeit .

  2. Wir behaupten, dass die Anforderungen nicht mit weniger als vier Welten realisierbar sind. Nach Voraussetzung müssen und verschieden sein. Wegen

    kann von weder noch selbst erreichbar sein, da dies ein Widerspruch zu ergeben würde. Zugleich braucht man, um die Gültigkeit von und zu realisieren, zwei von aus erreichbare Welten, also insgesamt mindestens vier Welten.