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

Aus Wikiversity



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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Ableitbarkeit eines -Ausdrucks aus einer Menge an - Ausdrücken.
  2. Eine Abbildung von einer Menge in eine Menge .
  3. Die endliche Axiomatisierbarkeit einer Theorie .
  4. Ein reell-abgeschlossener Körper.
  5. Die Eigenschaft einer Menge von arithmetischen Ausdrücken, Repräsentierungen zu erlauben.
  6. Das modallogische Symmetrieaxiom.


Lösung

  1. Man sagt, dass aus ableitbar ist, wenn es endlich viele Ausdrücke derart gibt, dass

    gilt.

  2. Eine Abbildung von nach ist dadurch gegeben, dass jedem Element der Menge genau ein Element der Menge zugeordnet wird.
  3. Die endliche Axiomatisierbarkeit von liegt vor, wenn es endlich viele Sätze mit gibt.
  4. Ein angeordneter Körper heißt reell-abgeschlossen, wenn folgende Eigenschaften gelten.
    1. Jedes nichtnegative Element aus besitzt eine Quadratwurzel in .
    2. Jedes Polynom mit ungeradem Grad besitzt in eine Nullstelle.
  5. Man sagt, dass Repräsentierungen erlaubt, wenn jede - berechenbare Relation und jede - berechenbare Funktion repräsentiert.
  6. Das modallogische Axiomenschema

    nennt man Symmetrieaxiom.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Wiles (Großer Fermat).
  2. Der Satz von Henkin.
  3. Der Fixpunktsatz für arithmetische Ausdrücke.


Lösung

  1. Die diophantische Gleichung

    besitzt für kein

    eine ganzzahlige nichttriviale Lösung.
  2. 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 .
  3. Es sei eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem einen Satz mit


Aufgabe (1 Punkt)

Petra fliegt zu ihrer ersten internationalen Konferenz. Als sie auf dem Weg zum Flughafen ihre Wohnung (sie wohnt allein) verlässt und gerade die Wohnungstür zugemacht hat, merkt sie (eine der drei Möglichkeiten)

  1. Sie hat ihr Flugticket auf dem Schreibtisch vergessen.
  2. Sie hat ihre Schlüssel auf dem Schreibtisch vergessen.
  3. Sie hat ihren Reisepass auf dem Schreibtisch vergessen.

Was ist am schlimmsten?


Lösung

(1) und (3) sind jedenfalls nicht schlimm, da Petra die Schlüssel hat und daher direkt die vergessenen Sachen holen kann. Bei (2) hat sie dagegen ein Problem, wenn sie zurückkommt.


Aufgabe (2 Punkte)

Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?


Lösung

  1. Leere Mulde auf dem Straßenplatz abladen.
  2. Volle Mulde auf Fahrzeug hochladen.
  3. Volle Mulde auf dem Straßenplatz abladen.
  4. Leere Mulde auf Fahrzeug hochladen.
  5. Leere Mulde auf den Garagenvorplatz abladen.
  6. Volle Mulde auf Fahrzeug hochladen.

Es sind also sechs Ladevorgänge nötig.


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)

Zeige, dass der aussagenlogische Ausdruck

allgemeingültig ist


Lösung

Wir müssen zeigen, dass für jede Wahrheitsbelegung der Variablen der Wahrheitswert der Gesamtaussage gleich ist. Bei ist und damit ist der Nachsatz und die Gesamtaussage wahr. Es sei also im Folgenden . Dann ist . Bei ist der Vordersatz falsch und somit die Gesamtaussage wahr. Es sei also . Dann ist der Vordersatz wahr und wir müssen zeigen, dass auch der Nachsatz wahr ist. Es ist dann und , also ist auch in diesem Fall der Nachsatz und die Gesamtaussage wahr.


Aufgabe (6 (2+4) Punkte)

Es seien und Aussagen.

  1. Zeige
  2. Zeige


Lösung

  1. Mit (einer Variante von) Lemma 3.17 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

    Mit Kontraposition des Nachsatzes ergibt sich daraus

    Mit Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (4) folgt

    und mit Kontraposition

  2. Es ist

    und

    nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1). Mit Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021))  (6) (Kontraposition) ergibt sich

    und daraus und der zweiten Zeile mit der Kettenschlussregel

    Mit Kontraposition (als Regel) ergibt sich aus der ersten und der letzten Zeile unter Verwendung von Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021)) wiederum

    und

    Daraus ergibt sich wegen Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3)

    und somit


Aufgabe (4 Punkte)

Es sei eine Menge an Aussagenvariablen und eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Zeige, dass für jedes entweder oder gilt.


Lösung

Wegen der Widerspruchsfreiheit können nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so ist entweder oder widerspruchsfrei, was der maximalen Widerspruchsfreiheit von widerspricht. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck sowohl

als auch

gelten. Dies bedeutet nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))

und

woraus aufgrund der Fallunterscheidungsregel

folgt. Dies würde aber bedeuten, dass widersprüchlich wäre.


Aufgabe (3 (2+1) Punkte)

Es sei eine Menge und eine Teilmenge der Potenzmenge, die unter beliebigen Vereinigungen abgeschlossen ist.

  1. Zeige, dass induktiv geordnet ist.
  2. Zeige, dass ein größtes Element besitzt.


Lösung

  1. Es sei eine Kette in . Nach Voraussetzung gehört zu und offenbar gilt

    für jedes aus . Für die Kette gibt es also eine obere Schranke in , so dass die Menge induktiv geordnet ist.

  2. Die Menge

    enthält jede Menge von und gehört zu , sie ist somit das größte Element von .


Aufgabe (1 Punkt)

Wir betrachten den Satz „Diese Vorlesung versteht keine Sau“. Negiere diesen Satz durch eine Existenzaussage.


Lösung

Es gibt eine Sau, die diese Vorlesung versteht.


Aufgabe (2 Punkte)

Zeige, dass der prädikatenlogische Ausdruck

erfüllbar ist.


Lösung

Es sei eine zweielementige Menge. Bei der Interpretation mit und ist und für alle muss oder sein. Also gilt

und

und damit

Also ist die Existenzaussage erfüllbar.


Aufgabe (4 Punkte)

Beweise den Satz über die Vorgängereigenschaft in einem Peano-Halbring.


Lösung

Beide Teilaussagen können wegen des ersten Peano-Axioms nicht zugleich wahr sein. Es geht also um die Aussage

die wir durch Induktion beweisen. Der Induktionsanfang für ist durch den linken Bestandteil gesichert. Es sei also die Aussage für ein gewisses schon bewiesen, und sie ist für zu beweisen. Bei ist , so dass man nehmen kann. Bei ist

und somit kann man nehmen.


Aufgabe (3 Punkte)

Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung die Gleichheit folgt (dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden).


Lösung

Wir führen Induktion über (für die Aussage für beliebige ). Für

folgt die Aussage daraus, dass das neutrale Element der Addition ist. Die Aussage gelte nun für ein bestimmtes . Wir müssen zeigen, dass sie auch für den Nachfolger gilt. Es sei also

Aufgrund von Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (2) bedeutet dies

woraus nach Induktionsvoraussetzung

folgt. Aufgrund der Injektivität der Nachfolgerabbildung ergibt sich


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

In einem Zugabteil sitzen die sechs Personen . Wir betrachten die folgenden Relationen:

  1. bedeutet, dass über die deutsche Bahn motzt.
  2. bedeutet, dass einen Fensterplatz hat.
  3. bedeutet, dass der Person die Fahrkarte klaut.

Es gelten ausschließlich die Beziehungen

  1. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Relationen.
  2. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .
  3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .


Lösung Zugabteil/Relationen/Elementare Äquivalenz/2/Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Zeige, dass die erststufige Peano-Arithmetik eine vollständige widerspruchsfreie erststufige Erweiterung , also , besitzt, die von verschieden ist.


Lösung

Nach Korollar 21.13 (Einführung in die mathematische Logik (Osnabrück 2021)) liegt eine echte Erweiterung vor. Es gibt somit Sätze mit . Es ist ferner , da andernfalls widersprüchlich wäre. Es ist widerspruchsfrei, da man sonst aus den Satz ableiten könnte, was wegen der Abgeschlossenheit unter Ableitungen und wegen nicht der Fall ist. Nach dem Vollständigkeitssatz gibt es somit ein Modell mit

Dabei ist vollständig. Wegen und ist .


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (5 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Symmetrieaxiom genau dann gilt, wenn symmetrisch ist.


Lösung

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

Es sei eine von aus erreichbare Welt gegeben, also . Wegen der Symmetrie ist auch und somit ist

Also ist

Wenn hingegen nicht symmetrisch ist, so seien Welten mit , aber nicht . Es sei eine Aussagenvariable und es sei die Belegung, bei der

gelte und so, dass in allen von aus erreichbaren Welten gelte. Dann ist

und somit ist

also


Aufgabe (4 Punkte)

Es sei die durch das Löb-Axiom gegebene - Modallogik, also die Beweisbarkeitslogik. Wir setzen

(als Abkürzung für einen Widerspruch). Zeige, dass

ableitbar ist.


Lösung

Wegen Kontraposition genügt es,

zu zeigen, wobei wir die einzelnen Implikationen getrennt zeigen. Aus einem Widerspruch folgt Beliebiges, also

Nach Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1) folgt

Eine Instanz des Löb-Axioms ist

Das Widerspruchsaxiom ergibt

was wir als

schreiben. Mit Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (1) erhalten wir

Der Kettenschluss liefert