Kurs:Einführung in die mathematische Logik/14/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 2 2 2 2 5 2 4 4 12 0 0 0 0 0 2 43




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die zu einer (aussagenlogischen) Wahrheitsbelegung

    auf einer Aussagenvariablenmenge zugehörige Interpretation auf der Sprache .

  2. Eine obere Schranke zu einer Teilmenge in einer geordneten Menge .
  3. Eine -Struktur zu einem Symbolalphabet einer Sprache erster Stufe.
  4. Die Folgerungsbeziehung , wobei eine Menge von - Ausdrücken und ein -Ausdruck ist (und ein Symbolalphabet.)
  5. Die -Aufzählbarkeit einer Teilmenge .
  6. Die Gültigkeit einer modallogischen Ausdrucksmenge .


Lösung

  1. Die zugehörige Interpretation wird rekursiv über den Aufbau der Sprache wie folgt festgelegt.
    1. für jede Aussagenvariable .
    2. Bei ist
    3. Bei ist
    4. Bei ist
    5. Bei ist
    6. Bei ist
  2. Ein Element heißt obere Schranke für , wenn für jedes gilt.
  3. Unter einer -Struktur versteht man eine nichtleere Menge mit den folgenden Festlegungen.
    1. Für jede Konstante ist ein Element festgelegt.
    2. Zu jedem -stelligen Funktionssymbol (aus ) ist eine -stellige Funktion

      festgelegt.

    3. Zu jedem -stelligen Relationssymbol (aus ) ist eine -stellige Relation

      festgelegt.

  4. Man sagt, dass aus folgt, wenn für jede - Interpretation mit auch gilt.
  5. Man sagt, dass -aufzählbar ist, wenn es ein Programm für eine Registermaschine gibt, die bei Eingabe von nach und nach genau die Zahlen aus ausdruckt.
  6. Man sagt, dass eine Menge von modallogischen Ausdrücken in einem modallogischen Modell gilt, wenn

    für alle gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.
  2. Das Koinzidenzlemma.
  3. Der Vollständigkeitssatz der Modallogik.


Lösung

  1. Es seien und Dedekind-Peano-Modelle für die natürlichen Zahlen. Dann gibt es eine eindeutig bestimmte bijektive Abbildung

    mit und

    für alle .
  2. 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. Dann gelten folgende Aussagen.
    1. Es ist .
    2. Es ist genau dann, wenn .
  3. Es sei eine Menge von modallogischen Ausdrücken und ein modallogischer Ausdruck. Dann ist

    genau dann, wenn


Aufgabe (2 Punkte)

Erläutere das Prinzip Beweis durch Widerspruch.


Lösung

Man möchte eine Aussage beweisen. Man nimmt an, dass nicht gilt. Daraus leitet man durch logisch korrektes Schließen einen Widerspruch her. Somit kann nicht gelten und also muss gelten.


Aufgabe (2 Punkte)

Anna kann sich nicht zwischen Heinrich und Konrad entscheiden, deshalb lässt sie sich vom Zufall leiten. Sie wohnt an einer U-Bahn-Station der Linie , die von Heinsheim nach Konsau fährt. Heinrich wohnt in Heinsheim und Konrad in Konsau. Wenn Anna Lust auf ein Date hat, geht sie einfach zu ihrer Station und nimmt die erstbeste U-Bahn, die gerade kommt. Die U-Bahnen fahren in beide Richtungen im Zehn-Minuten-Takt und die U-Bahnen nach Heinsheim fahren etc. Nach einiger Zeit stellt Anna fest, dass sie Konrad viermal so häufig besucht wie Heinrich. Wann fahren die U-Bahnen nach Konsau ab?


Lösung

Die Wahrscheinlichkeit, dass als erstes eine U-Bahn nach Konsau kommt, muss viermal so groß sein wie die Wahrscheinlichkeit, dass zuerst eine U-Bahn nach Heinsheim kommt. Deshalb muss in einem Zehn-Minuten-Intervall acht Minuten lang eine U-Bahn nach Konsau die nächste sein (und zwei Minuten lang eine U-Bahn nach Heinsheim). Die U-Bahnen nach Konsau fahren also etc. ab.


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

Es sei eine endliche Menge. Betrachte die Relation auf der Potenzmenge , die durch

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?


Lösung

Das ist keine Ordnungsrelation, da die Antisymmetrie nicht erfüllt ist. Wenn man zwei verschiedene Teilmengen aus nimmt, sagen wir und , die beide die gleiche Anzahl besitzen (was es gibt, sobald zumindest zwei Elemente besitzt), so gilt und damit

und

aber daraus kann nicht auf geschlossen werden.


Aufgabe (5 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Es sei widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable gelte oder . Zeige, dass dann maximal widerspruchsfrei ist.


Lösung

Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes die Alternative oder gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für eine Aussagenvariable ist dies Teil der Voraussetzung. Bei folgt wegen die Aussage aus der Induktionsvoraussetzung, da abgeschlossen unter Ableitungen ist. Es sei nun . Bei und ist wegen der Ableitungsabgeschlossenheit auch . Wenn hingegen ist, so folgt nach der Induktionsvoraussetzung . Aufgrund der Tautologie ergibt sich . Der Beweis für die Implikation verläuft ähnlich, siehe Aufgabe 4.16 (Einführung in die mathematische Logik (Osnabrück 2021)).

Zum Nachweis, dass maximal widerspruchsfrei ist, sei angenommen. Nach dem, was wir eben bewiesen haben, gilt dann . Dann ist aber und somit ist diese erweiterte Menge widersprüchlich.


Aufgabe (2 (1+1) Punkte)

Wir betrachten den Satz „Nachts sind alle Katzen grau“.

  1. Negiere diesen Satz durch eine Existenzausssage, wenn der Satz sich auf eine bestimmte Nacht bezieht.
  2. Negiere diesen Satz durch eine Existenzausssage, wenn der Satz sich auf jede Nacht bezieht.


Lösung

  1. In dieser Nacht gibt es eine Katze, die nicht grau ist.
  2. Es gibt eine Nacht und eine Katze, die in dieser besagten Nacht nicht grau ist.


Aufgabe (4 Punkte)

Es seien Variablen, Terme und ein Ausdruck in einer prädikatenlogischen Sprache . Zeige, dass

allgemeingültig ist.


Lösung

Es sei eine Interpretation mit

also

und

Nach dem Substitutionslemma bedeutet dies

Wegen der Gleichheiten kann man dies genauso gut als

schreiben. Mit dem Substitutionslemma ergibt sich hieraus wiederum


Aufgabe (4 Punkte)

Zeige, dass

im Kalkül der Prädikatenlogik ableitbar ist.


Lösung

Durch Existenzeinführung im Sukzedenz haben wir

und

und daraus

Dabei ist hinten gebunden und somit kann man mit der Existenzeinführung im Antezedens auf

schließen. Da auch hinten gebunden ist, ergibt sich


Aufgabe weiter

Es sei

  1. Zeige, dass ein kommutativer Halbring ist.
  2. Zeige, dass in die Relationen

    und

    zueinander äquivalent sind.

  3. Zeige, dass nicht irreduzibel in ist.
  4. Zeige, dass es in keine irreduziblen Elemente gibt.
  5. Es sei die Aussage

    Zeige, dass in die Aussage

    wahr ist.

  6. Zeige, dass kein Peano-Halbring ist.


Lösung

  1. Es ist lediglich zu zeigen, dass unter der Addition und der Multiplikation abgeschlossen sind. Dies ist für die Addition mit und der Multiplikation mit klar. Ferner ist die Summe (bzw. das Produkt) von zwei rationalen Zahlen, die beide sind, selbst wieder .
  2. Wenn ist, so ist wegen automatisch auch die rechte Seite erfüllt, und wenn ist, so ist wegen

    auch die linke Seite erfüllt. Wir können also und auf den Fall beschränken. Wenn das Element teilt, so bedeutet dies, dass es ein mit

    gibt. Dies bedeutet einfach, dass der in genommene Quoient zu gehört, also ist. Doch dies ist äquivalent zu .

  3. Es ist

    eine Darstellung in Faktoren, die beide keine Einheit sind.

  4. Die und die (einzige) Einheit sind nach Definition nicht irreduzibel. Für mit ist

    und wegen ist auch

    also gehören die beiden Faktoren zu .

  5. Der erste Teil der Konjunktion, also , ist unmittelbar wegen des ersten Teils der Disjunktion wahr. Es sei also wahr für ein bestimmtes . Der Nachfolger davon, also , steht bereits in der Form des zweiten Teils der Disjunktion da.
  6. Wir betrachten das Induktionsaxiom für die Aussage aus Teil (5). Die Voraussetzungen, also Induktionsanfang und Induktionsschritt, gelten wie in Teil (5) gezeigt. Hingegen gilt die Aussage nicht für alle , beispielsweise gilt sie für nicht.


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

Zeige durch Angabe eines modallogischen Modelles, dass im - System der Ausdruck

nicht ableitbar ist (dabei seien Aussagenvariablen).


Lösung

Es bestehe aus zwei Welten und mit der vollen Relation. Es gelte

Damit gilt

und somit

Dagegen gilt in weder noch .