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


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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Wohlordnung auf einer Menge .
  2. Eine -stellige Relation auf einer Menge .
  3. Die Termmenge zu einer Grundtermmenge .
  4. Ein allgemeingültiger prädikatenlogischer Ausdruck .
  5. Die Befehle für eine Registermaschine.
  6. Die modallogische Sprache zu einer Aussagenvariablenmenge .


Lösung

  1. Eine totale Ordnung auf einer Menge heißt Wohlordnung, wenn jede nichtleere Teilmenge ein kleinstes Element besitzt.
  2. Unter einer -stelligen Relation auf versteht man eine Teilmenge der -fachen Produktmenge .
  3. Die Termmenge ist diejenige Teilmenge der Wörter über dem Termalphabet , die durch die folgenden rekursiven Vorschriften festgelegt wird.
    1. Jede Variable ist ein Term.
    2. Jede Konstante ist ein Term.
    3. Für jedes und Terme ist auch ein Term.
  4. Man nennt allgemeingültig, wenn er in jeder - Interpretation gilt.
  5. Die Befehle für eine Registermaschine sind (dabei bezeichnen Register und Befehlszeilen).
    1. (erhöhe den Inhalt des Registers um , d.h. um einen Strich).
    2. (reduziere den Inhalt des Registers um , d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
    3. (wenn das -te Register leer ist, so gehe zum Befehl , andernfalls zum nächsten Befehl).
    4. Drucke (drucke den Inhalt des ersten Registers).
    5. Halte an.
  6. Die modallogische Sprache zu besteht aus den Aussagenvariablen, aus allen rekursiv-konstruierbaren aussagenlogischen Verknüpfungen und aus allen rekursiv-konstruierbaren Ausdrücken der Form .


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).
  2. Der Vollständigkeitssatz der Prädikatenlogik.
  3. /Fakt/Name


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, eine Menge an - Ausdrücken und ein weiterer -Ausdruck. Dann gilt genau dann, wenn gilt.
  3. /Fakt


Aufgabe (1 Punkt)

Bruno liest in der Zeitung: „Im letzen Jahr war bei aller Autounfälle Alkohol mit im Spiel“. Bruno überlegt: „ mit Alkohol, ohne Alkohol. Dann ist es also egal, ob man was trinkt oder nicht. In Zukunft werde ich das auch nicht mehr so streng sehen“. Beurteile diese Überlegung!


Lösung Autounfall/Alkoholanteil/Aufgabe/Lösung


Aufgabe (3 Punkte)

Beweise den Satz, dass es unendlich viele Primzahlen gibt.


Lösung

Angenommen, die Menge aller Primzahlen sei endlich, sagen wir . Man betrachtet die Zahl

Diese Zahl ist durch keine der Primzahlen teilbar, da bei Division von durch immer ein Rest verbleibt. Damit sind die Primfaktoren von , die es nach Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024)) geben muss, nicht in der Ausgangsmenge enthalten - Widerspruch.


Aufgabe (3 Punkte)

Definiere zu jeder Aussage die Menge der in vorkommenden Aussagenvariablen.


Lösung

Wir legen die Abbildung

rekursiv über den Aufbau von fest. Wegen dem eindeutigen rekursiven Aufbau von ist dadurch eine wohldefinierte Abbildung gegeben. Für

setzt man

Für

setzt man

Für

mit

setzt man


Aufgabe (2 Punkte)

Zeige

unter Verwendung von

(Lemma 3.14 (Einführung in die mathematische Logik (Osnabrück 2021))).


Lösung

Aufgrund von Lemma 3.14 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

Das Widerspruchsaxiom besagt

Das Kettenschlussaxiom liefert

Da die beiden Teile des Vordersatzes ableitbar sind, ist auch der Nachsatz ableitbar.


Aufgabe (3 Punkte)

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


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)

Dies bedeutet .


Aufgabe (5 (4+1) Punkte)

Es sei ein topologischer Raum und ein topologischer Filter auf , eine offene Teilmenge und .

  1. Zeige, dass das Mengensystem

    ein Filter auf ist, der enthält und nicht enthält.

  2. Zeige mit Hilfe des Lemmas von Zorn, dass es einen Ultrafilter mit und mit gibt.


Lösung

  1. Sei

    Zu ist

    und daher ist

    und insbesondere ist . Zu gibt es mit

    und diese Bedingung wird auch von jedem erfüllt, also ist auch . Zu gibt es mit

    und

    Daraus ergibt sich

    und wegen ist . Somit ist ein Filter. Wegen und

    ist . Angenommen . Dann gibt es mit

    und dann ist insbesondere , also im Widerspruch zur Voraussetzung.

  2. Zu dem in Teil (1) gegebenen Filter gibt es nach Lemma 5.13 (Einführung in die mathematische Logik (Osnabrück 2021)) einen Ultrafilter mit . Wegen ist , da sonst auch

    wäre.


Aufgabe (1 Punkt)

Man finde eine äquivalente Formulierung für die Aussage „Frau Maier-Sengupta hat nicht alle Tassen im Schrank“ mit Hilfe einer Existenzaussage.


Lösung

Es gibt eine Tasse, die Frau Maier-Sengupta nicht im Schrank hat.


Aufgabe (5 Punkte)

Es seien Terme und ein -stelliges Funktionssymbol. Zeige, dass die Ableitbarkeit

gilt.


Lösung

Es sei eine Variable, die weder in einem der noch in einem der vorkommt. Für jedes setzen wir . Nach Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))   (2) ergibt sich daraus

also

Da der Vordersatz in der Implikation rechts nach Axiom 10.5 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) ableitbar ist, ergibt eine aussagenlogische Umformulierung

Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion

ersetzt. Durch die Transitivität der Implikation ergibt sich daher


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Reflexivitätsaxiom genau dann gilt, wenn reflexiv ist.


Lösung

Es sei gegeben. Es sei zunächst reflexiv und sei

Wegen ist insbesondere

und damit

Wenn nicht reflexiv ist, so sei und gelte nicht. Es sei die Belegung, bei der

gelte, aber in allen anderen Welten . Dann ist

und somit ist