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


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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Primzahl.
  2. Die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .
  3. Die Uminterpretation zu einer - Interpretation in einer Menge , wobei eine Variable und ein Element der Grundmenge ist.
  4. Der Rang eines prädikatenlogischen Ausdrucks .
  5. Eine -berechenbare Funktion
  6. Eine -Modallogik.


Lösung

  1. Eine natürliche Zahl heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr und sind.
  2. Die Sprache der Aussagenlogik wird rekursiv durch folgende Regeln definiert.
    1. Jedes gehört zu .
    2. Wenn , so ist auch .
    3. Wenn , so sind auch .
  3. Unter der Uminterpretation versteht man diejenige Interpretation von in , die strukturgleich zu ist und für deren Variablenbelegung

    gilt.

  4. Der Rang von wird rekursiv durch
    1. , falls atomar ist.
    2. , falls ist.
    3. , falls mit ist.
    4. , falls oder ist.

    definiert.

  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. Eine Modallogik heißt eine -Modallogik, wenn das Axiomenschema

    für beliebige Ausdrücke und die Nezessisierungsregel

    aus folgt

    für alle gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Substitutionslemma.
  2. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .
  3. Der Vollständigkeitssatz der Modallogik.


Lösung

  1. 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
  2. Es sei eine Menge mit einem fixierten Element und einer Abbildung . Dann gibt es genau eine Abbildung

    die die beiden Eigenschaften

    erfüllt.
  3. Es sei eine Menge von modallogischen Ausdrücken und ein modallogischer Ausdruck. Dann ist

    genau dann, wenn


Aufgabe (4 (2+1+1) Punkte)

Folgende Aussagen seien bekannt.

  1. Der frühe Vogel fängt den Wurm.
  2. Doro wird nicht von Lilly gefangen.
  3. Lilly ist ein Vogel oder ein Igel.
  4. Für Igel ist 5 Uhr am Morgen spät.
  5. Doro ist ein Wurm.
  6. Für Vögel ist 5 Uhr am Morgen früh.
  7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

  1. Ist Lilly ein Vogel oder ein Igel?
  2. Ist sie ein frühes oder ein spätes Tier?
  3. Fängt der späte Igel den Wurm?


Lösung

  1. Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2).
  2. Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier.
  3. Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm.


Aufgabe (8 Punkte)

Es sei eine aussagenlogische Aussage und es seien die darin vorkommenden Aussagenvariablen. Es sei

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Zeige, dass dann

gilt.


Lösung

Wir führen Induktion über den Aufbau der Sprache . Bei

ergibt sich die Aussage aus Lemma 3.12 (Einführung in die mathematische Logik (Osnabrück 2021)). Bei

ergibt sich die Aussage aus der Induktionsvoraussetzung und aus Lemma 3.19 (Einführung in die mathematische Logik (Osnabrück 2021))  (3). Es sei nun

Bei

ergibt sich die Ableitung

im Wesentlichen aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3). Bei

ergibt sich die Ableitung

aus Kontraposition auf Lemma 3.12 (Einführung in die mathematische Logik (Osnabrück 2021)). Es sei nun

Bei

ergibt sich die Ableitung

aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) bzw. aus Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (5). Bei

hingegen ergibt sich die Ableitung

folgendermaßen. Nach Lemma 3.17 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

was wir als

schreiben. Kontraposition auf den Nachsatz ergibt

was wir wiederum als

schreiben. Aus den beiden Voraussetzungen ergibt sich mit Hilfe von Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (3)

und somit mit der Kettenschlussregel


Aufgabe (2 Punkte)

Es sei eine Konstantenmenge, ein einstelliges Funktionssymbol und ein zweistelliges Funktionssymbol. Es sei die Interpretation mit als Grundmenge, bei der als Quadrieren, als Multiplikation und die Konstanten als und interpretiert wird. Ist der Ausdruck

unter dieser Interpretation gültig?


Lösung

Die Gültigkeit des Ausdrucks bei der Interpretation würde bedeuten, dass

mit

übereinstimmt. Da eine fehlt, ist dies nicht richtig und daher ist der Ausdruck bei der Interpretation nicht gültig.


Aufgabe (4 (1+2+1) Punkte)

  1. Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
  2. Beschreibe die Bedingung (und zwar so, dass die Bedingung erkennbar ist) aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck (also mit dem Symbolalphabet und Variablen) in der einen freien Variablen .
  3. Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen .


Lösung

  1. Da eine natürliche Zahl ist, sind die ersten Quadratzahlen und somit ist die erste natürliche Zahl, die größer als drei Quadratzahlen ist.


Aufgabe (3 Punkte)

Formuliere die Injektivität für eine Abbildung

prädikatenlogisch mit Hilfe der Verwendung von Sorten.


Lösung

Die Symbolmenge bestehe aus einem einstelligen Funktionssymbol und zwei einstelligen Relationssymbolen und . Wir betrachten den Ausdruck

Bei einer Interpretation in einer Gesamtmenge besagt der linke Ausdruck, dass wenn ein Element zu gehört, dass dann der Funktionswert zu gehört. Das bedeutet also, dass eine Abbildung

vorliegt. Der rechte Ausdruck besagt somit, dass für verschiedene Elemente aus die Bilder verschieden sind, was die Injektivität dieser Abbildung bedeutet.


Aufgabe (5 (3+2) Punkte)

Es sei ein Symbolalphabet und die zugehörige Sprache und die zugehörige Termmenge. Es sei eine Ausdrucksmenge.

  1. Zeige, dass durch

    eine Äquivalenzrelation auf definiert wird.

  2. Wenn man vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?


Lösung

  1. Wegen und der Korrektheit des Ableitungskalküls ist überhaupt für jede Interpretation. Es liegt also eine reflexive Relation vor. Es sei nun . Dann gilt für jede Interpretation mit die Gleichheit und somit auch , also ist auch , was die Symmetrie beweist. Es gelte nun und , und es sei eine Interpretation mit . Dann ist und und somit auch wegen der Transitivität der Gleichheit. Also gilt , was die Transitivität beweist.
  2. Es sei . Wir behaupten, dass die Äquivalenz die Äquivalenz impliziert. Es sei dazu und eine Interpretation mit gegeben. Dann gilt erst recht und somit ist . Somit umfassen die Äquivalenzklassen zu die Äquivalenzklassen zu , die Äquivalenzklassen werden also größer.


Aufgabe (5 (1+1+1+1+1) Punkte)

In einer Wohngemeinschaft leben die Personen . Wir betrachten die folgenden Relationen:

  1. bedeutet, dass und manchmal miteinander Tennis spielen,
  2. bedeutet, dass und manchmal miteinander Skat spielen,
  3. bedeutet, dass und manchmal miteinander Doppelkopf spielen.

In der WG gilt

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


Lösung

  1. ist diejenige Person, die manchmal Tennis spielt und kein Skat spielt.
  2. ist diejenige Person, die manchmal Skat spielt, und zwar nur bei einer Skatrunde beteiligt ist, und die nicht Tennis spielt.
  3. .
  4. .
  5. .


Aufgabe (4 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Quadratzahlen ausdruckt.


Lösung Registermaschine/Alle Quadratzahlen/Druckt/Aufgabe/Lösung


Aufgabe (4 Punkte)

Es seien entscheidbare Mengen. Zeige, dass dann auch die Vereinigung , der Durchschnitt und auch das Komplement entscheidbar sind.


Lösung N/Teilmengen/Entscheidbar/Durchschnitt und Vereinigung/Komplement/Aufgabe/Lösung


Aufgabe (4 Punkte)

Zeige, dass die Abbildung

(wohldefiniert und) arithmetisch repräsentierbar ist.


Lösung

Die Abbildung ist wohldefiniert, da der Ausdruck

für nie negativ wird. Es sei

Für beliebige natürliche Zahlen gilt dann

genau dann, wenn in die Gleichheit

gilt, was genau dann der Fall ist, wenn in die Gleichheit

bzw.

also

gilt. Der Ausdruck repräsentiert also arithmetisch die Funktion .


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 Satz 22.8 (Einführung in die mathematische Logik (Osnabrück 2021)) 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.


Aufgabe (6 (1+1+4) Punkte)

Wir interpretieren den Satz von Sokrates, „Ich weiß, dass ich nichts weiß“, als modallogisches Axiomenschema

Zeige die folgenden Aussagen.

  1. Dieses Axiomenschema ist paradox.
  2. Dieses Axiomenschema ist innerhalb der - Modallogik äquivalent zu
  3. Dieses Axiomenschema ist innerhalb der - Modallogik äquivalent zu

    also zum Leerheitsaxiom.


Lösung

  1. Für die Tauotologie

    ergibt sich, wenn man die Boxen vergisst, der Widerspruch , also ist das Axiomenschema paradox.

  2. Es ist

    Somit gilt die linke Seite für alle genau dann, wenn die rechte Seite für alle gilt, und dies ist in einer -Modallogik äquivalent dazu, dass es für alle gilt.

  3. Das Leerheitsaxiom ist offenbar stärker. Wegen der Widerspruchstautologie gilt

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

    und nach Lemma 24.5 (Einführung in die mathematische Logik (Osnabrück 2021))  (4) gilt

    Mit dem Kettenschluss ergibt sich

    Wir setzen nun für eine Tautologie ein, etwa . Eine doppelte Anwendung der Nezessisierungsregel liefert

    Das Sokratesaxiom liefert

    Damit sind die beiden Voraussetzungen von oben erfüllt und somit gilt


Aufgabe (5 Punkte)

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


Lösung

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

Es sei und und somit

Also ist

und damit

Es sei nun nicht transitiv und seien Punkte mit , , aber nicht . Es sei eine Aussagenvariable und sei die Belegung, bei der in allen von aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

und

da ja , und somit ist

also