Kurs:Einführung in die mathematische Logik/19/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
Punkte 3 3 4 2 4 3 4 3 8 10 5 3 6 2 4 64




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein maximales Element in einer geordneten Menge .
  2. Die Termsubstitution für -Terme (dabei sei ein Symbolalphabet einer Sprache erster Stufe, paarweise verschiedene Variablen und fixierte -Terme).
  3. Der Rang eines prädikatenlogischen Ausdrucks .
  4. Die elementare Äquivalenz von zwei -Strukturen und über einem erststufigen Symbolalphabet .
  5. Eine -berechenbare Funktion
  6. Die -Funktion .


Lösung

  1. Ein Element heißt maximal, wenn es kein Element , , mit gibt.
  2. Die Termsubstitution wird rekursiv folgendermaßen definiert.
    1. Für eine Variable ist
    2. Für eine Konstante ist
    3. Für ein -stelliges Funktionssymbol und Terme ist
  3. Der Rang von wird rekursiv durch
    1. , falls atomar ist.
    2. , falls ist.
    3. , falls mit ist.
    4. , falls oder ist.

    definiert.

  4. Die beiden -Strukturen und heißen elementar äquivalent, wenn jeder -Satz, der in gilt, auch in gilt.
  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 der -Funktion versteht man die Abbildung

    die folgendermaßen festgelegt ist. ist die kleinste Zahl , die die Bedingung erfüllt, dass es natürliche Zahlen gibt, die die folgenden Eigenschaften erfüllen:

    1. .
    2. .
    3. .
    4. ist eine Quadratzahl.
    5. Alle Teiler von sind ein Vielfaches von .

    Wenn kein solches existiert, so ist .


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Euklid über Primzahlen.
  2. Das Substitutionslemma.
  3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .


Lösung

  1. Es gibt unendlich viele Primzahlen.
  2. Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben und es seien paarweise verschiedene Variablen und fixierte -Terme. Es sei eine -Interpretation gegeben. Dann gelten folgende Aussagen.
    1. Für jeden -Term gilt
    2. Für jeden -Ausdruck gilt
  3. Es sei eine Menge mit einem fixierten Element und einer Abbildung . Dann gibt es genau eine Abbildung

    die die beiden Eigenschaften

    erfüllt.


Aufgabe (4 Punkte)

Hanny, Nanny, Fanny und Sanny leben auf dem Ponyhof. Heute machen sie einen Ausflug mit den Ponies Pona, Pone, Pono und Ponu. Jedes der Mädchen sitzt dabei genau auf einem Pony, und sie reiten hintereinander. Folgende Fakten sind bekannt.

  1. Fanny sitzt nicht auf Pona.
  2. Pone und Ponu vertragen sich nicht so gut und laufen daher nicht direkt hintereinander.
  3. Nanny sitzt auf Pone oder auf Pono.
  4. Sanny reitet auf Pona oder auf Pone.
  5. Nanny reitet direkt hinter Sanny.
  6. Auf Ponu sitzt nicht Sanny.
  7. Pona läuft direkt zwischen Pone und Pono.
  8. Auf Pono sitzt weder Fanny noch Hanny.
  9. Sanny reitet weiter vorne als Hanny.

Wer sitzt auf welchem Pony und in welcher Reihenfolge laufen sie?


Lösung

Nach (7) liegt der Ponyabschnitt Pone-Pona-Pono oder Pono-Pona-Pone vor. Nach (2) sind somit nur die Ponyreihenfolgen Pone-Pona-Pono-Ponu oder Ponu-Pono-Pona-Pone möglich. Nach (8) sitzt auf Pono Nanny oder Sanny, nach (4) sitzt aber Sanny auf Pona oder Pone. Deshalb sitzt Nanny auf Pono. Nach (5) reitet Nanny direkt hinter Sanny. Bei der Reihenfolge Ponu-Pono-Pona-Pone müsste also Sanny auf Ponu reiten, was nach (4) ausgeschlossen ist. Also ist die Reihenfolge Pone-Pona-Pono-Ponu und Sanny reitet auf Pona. Nach (9) reitet Hanny auf Ponu und folglich reitet Fanny auf Pone.

Reihenfolge Pony Reiterin
1 Pone Fanny
2 Pona Sanny
3 Pono Nanny
4 Ponu Hanny


Aufgabe (2 Punkte)

Man gebe signifikante Beispiele zum Stichwort „Fortsetzung einer Abbildung“ aus der Mathematik und aus der mathematischen Logik.


Lösung Abbildung/Fortsetzung/Mathematik und Logik/Aufgabe/Lösung


Aufgabe (4 (1+3) Punkte)

Wir betrachten Wörter über dem Alphabet und den Prozess , der in einem solchen Wort jedes Vorkommen von durch das Wort ersetzt.

  1. Bestimme das Ergebnis von unter diesem Prozess.
  2. Diesen Prozess kann man iterieren. Mit bezeichnen wir das Ergebnis, wenn man den Prozess -mal hintereinander auf das Startwort anwendet. Bestimme die Anzahl der Buchstaben in zum Startwort .


Lösung

  1. Es ist
  2. Es sei

    insbesondere ist . Wir behaupten, dass in die Anzahl der gleich und die Anzahl der gleich und somit die Anzahl der Buchstaben gleich ist. Diese Aussagen beweisen wir durch Induktion über . Für sind sie richtig. Seien sie nun für bewiesen, wir wissen also, dass es in genau viele und viele gibt. Beim Ersetzungsprozess bleiben die stehen, und die werden durch ersetzt. Daher ist die Anzahl der in gleich

    und die Anzahl der in gleich


Aufgabe (3 Punkte)

Es sei die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge und es sei eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation . Zeige, dass maximal widerspruchsfrei ist.


Lösung

Sei . Da der Ableitungskalkül korrekt ist, ist abgeschlossen unter Ableitungen. Aufgrund der rekursiv definierten Wahrheitsbelegung gilt für jedes entweder oder . Somit ist widerspruchsfrei. Sobald man zu einen Ausdruck hinzunimmt, hat man und daraus kann man einen Widerspruch ableiten. Die Menge ist also maximal widerspruchsfrei.


Aufgabe (4 Punkte)

Es seien einstellige Relationssymbole. Erstelle eine Ableitung im Prädikatenkalkül für den Modus Disamis, also die Aussage


Lösung

Es gilt die aussagenlogische Ableitbarkeit

Dies fassen wir als eine Aussage vom Typ

auf. Nach Fakt ***** gilt in dieser Situation auch

Nach Fakt *****  (3) ist

Dies zusammengenommen ergibt mit dem Kettenschluss

was im obigen Spezialfall die Ableitbarkeit

liefert. Eine aussagenlogische Umformulierung liefert


Aufgabe (3 Punkte)

In einem angeordneten Körper ist durch

eine zweistellige Relation gegeben. Drücke diese Relation mit den üblichen Symbolen , Variablen und aussagenlogischen Junktoren aus.


Lösung

Der Betrag von ist durch

definiert. Daher können wir die Bedingung

entlang der vier möglichen Fälle auflösen. Die Bedingung ist somit äquivalent zu


Aufgabe (8 Punkte)

Beweise den Satz von Henkin.


Lösung

Es sei das konstruierte Modell zu und die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

für alle Ausdrücke , durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von gleich , also atomar. D.h. ist entweder von der Form oder . Im ersten Fall ist äquivalent zu bzw. in . Dies ist nach Fakt ***** äquivalent zu und das bedeutet .

Im zweiten Fall ist - nach Konstruktion von und - äquivalent zu , und dies ist äquivalent zu .

Sei nun die Aussage für alle Ausdrücke vom Rang bewiesen und sei ein Ausdruck vom Rang . Wir betrachten die mögliche Struktur von gemäß Definition *****. Bei

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung ( hat kleineren Rang als ) und Fakt *****  (1). Bei

besitzen die beiden Bestandteile kleineren Rang als . Die Zugehörigkeit ist nach Fakt *****  (3) äquivalent zur gemeinsamen Zugehörigkeit . Nach Induktionsvoraussetzung bedeutet dies und . Dies bedeutet wiederum aufgrund der Modellbeziehung. Bei

besitzt wieder einen kleineren Rang. Die Zugehörigkeit ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom ***** äquivalent zur Existenz eines Terms und der Zugehörigkeit . Die Substitution von nach verändert nach Aufgabe ***** nicht den Rang. Wir können also auf die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu . Nach dem Substitutionslemma ist dies äquivalent zu bzw. wegen Fakt *****. Dies ist äquivalent zu aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.


Aufgabe weiter

Es sei das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol besteht. Wir betrachten die KO-Runden (also ab dem Achtelfinale) der Fußballweltmeisterschaften von 2014 und von 2018, ohne das Spiel um Platz , als -Modelle, wobei wir als die Gewinnrelation interpretieren, d.h. besagt, dass gegen (gespielt und) gewonnen hat.

  1. Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
  2. Ist eine Charakterisierung des Weltmeisters?
  3. Charakterisiere durch einen -Ausdruck in der einen freien Variablen , dass eine Mannschaft mindestens das Halbfinale erreicht hat.
  4. Charakterisiere durch einen -Ausdruck in der einen freien Variablen , dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
  5. Betrachte Schweden bei der WM 2018. Man gebe einen -Ausdruck in der einen freien Variablen , der Schweden charakterisiert.
  6. Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den -Ausdruck, der Schweden bei der WM 2018 charakterisiert?
  7. Definiere einen -Isomorphismus zwischen der WM 2014 und der WM 2018.
  8. Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz mitberücksichtigt?


Lösung

  1. Deutschland G Brasilien und Deutschland G Argentinien treffen zu, die beiden anderen nicht.
  2. Nein, da der Weltmeister nicht gegen alle Mannschaften gewinnt, da er gar nicht gegen alle spielt.
  3. Schweden ist diejenige Mannschaft, die das Viertelfinale erreicht hat und gegen diejenige Mannschaft (England) ausgeschieden ist, die gegen diejenige Mannschaft (Kroatien) ausgeschieden ist, die im Finale unterlag. In einer Formel
  4. Costa Rica.
  5. Wir definieren induktiv, ausgehend vom Weltmeister, Finalist, Halbfinalisten, Viertelfinalisten einen Isomorphismus, wobei die Fortsetzung dadurch festgelegt wird, wer gegen wen in der Runde zuvor verloren hat. Dies liefert einen eindeutig bestimmten Isomorphismus. Es ergibt sich
  6. Im Jahr 2014 verlor der Halbfinalist, der gegen den Weltmeister verloren hat, das Spiel um Platz, 2018 gewann er es hingegen. Deshalb ist die Abbildung bei Berücksichtigung des Spiels um Platz kein Isomorphismus mehr.


Aufgabe (5 Punkte)

Schreibe einen Programmabschnitt für eine Registermaschine, das zum Befehl wechselt, wenn im -ten Register der Wert steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.


Lösung

Wir arbeiten mit den Programmzeilen (in relativer Nummerierung)

Das Programm reduziert also höchstens -mal den Registerinhalt von um . Wenn der Registerinhalt von am Anfang kleiner als ist, so wird dieser Registerinhalt in weniger als Schritten geleert und in diesem Fall landet man durch einen der bedingten Sprungbefehle unmittelbar hinter dem Programmabschnitt. Wenn der Registerinhalt von am Anfang gleich ist, so wird der Registerinhalt genau im Befehl geleert und in diesem Fall wird man im letzten Befehl zum Befehl geleitet. Wenn der Registerinhalt von am Anfang größer als ist, so wird der Registerinhalt bis zum Befehl nicht geleert und in diesem Fall wird man im letzten Befehl unmittelbar weitergeleitet. Das Programm leistet also das Gewünschte.


Aufgabe (3 Punkte)

Es seien aufzählbar axiomatisierbare Theorien. Zeige, dass dann auch aufzählbar ist.


Lösung Aufzählbar axiomatisierbar/Vereinigung/Aufgabe/Lösung


Aufgabe (6 Punkte)

Es sei

die Menge der geraden natürlichen Zahlen. Es sei die Ausdrucksmenge, die besagt, dass eine assoziative, kommutative Verknüpfung mit als neutralem Element ist. Es sei

Zeige, dass durch in schwach repräsentiert wird, aber nicht stark.


Lösung

Wir zeigen zuerst die schwache Repräsentierbarkeit, dass also für alle die Zugehörigkeit genau dann vorliegt, wenn die Ableitbarkeit gilt.

Wenn eine gerade natürliche Zahl ist, so ist

wobei wir die in die zwei gleichgroßen Häften aufgeteilt haben. Da in die Assoziativität und Kommutativität ableitbar ist (was auch der Grund dafür ist, dass wir in der Darstellung von als Summe von keine Klammerung festlegen müssen), ist auch

wobei und Abkürzungen für Einsersummen sind. Aufgrund der Existenzeinführung im Sukzedens ist

und mit Modus Ponens auch

also

Wenn ungerade ist, so ist definitiv nicht

da wegen dies auch in gelten würde, was aber nicht der Fall ist.

Es liegt aber keine starke Repräsentierbarkeit vor. In diesem Fall würde nämlich für ungerade die Ableitbarkeit

gelten. Dies würde dann in jedem Modell, das erfüllt, gelten. Da die Gültigkeit von nur bedeutet, dass ein kommutatives Monoid vorliegt, ist beispielsweise auch ein Modell für . Innerhalb der rationalen Zahlen besitzt aber jede Zahl eine Hälfte.


Aufgabe (2 Punkte)

Es sei eine arithmetische Ausdrucksmenge und ein einstelliges Prädikat mit

für alle . Zeige, dass es einen Satz mit

gibt.


Lösung

Es sei eine in der arithmetischen Sprache formulierbare prädikatenlogische Tautologie ohne freie Variable, beispielsweise . Dann ist insbesondere und nach Voraussetzung ist auch . Also ist auch .


Aufgabe (4 Punkte)

Beweise das Unvollständigkeitslemma.


Lösung

Aus der Repräsentierbarkeit von folgt, dass es einen arithmetischen Ausdruck in einer freien Variablen gibt, sagen wir , mit der Eigenschaft, dass

genau dann gilt, wenn

gilt. Wir betrachten die Negation . Nach Fakt ***** gibt es für einen Fixpunkt, also einen Satz mit

bzw.

Sowohl aus als auch aus ergibt sich dann direkt ein ableitbarer Widerspruch, was der Widerspruchsfreiheit des Systems widerspricht.