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




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. Das Alphabet einer Sprache erster Stufe.
  3. Ein Nichtstandardmodell zu einem fixierten -Modell .
  4. Die Arithmetische Repräsentierbarkeit einer Abbildung
  5. Eine vollständige Theorie .
  6. Das universelle modallogische Modell zu einem -modallogischen System .


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. Das Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.
    1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
    2. Zu jeder natürlichen Zahl eine Menge von -stelligen Relationssymbolen.
    3. Die aussagenlogischen Junktoren
    4. Das Gleichheitszeichen .
    5. Die Quantoren und .
    6. Klammern, also und .
  3. Man nennt eine weitere -Struktur , die zu elementar äquivalent, aber nicht zu -isomorph ist, ein Nichtstandardmodell von .
  4. Die Abbildung heißt arithmetisch repräsentierbar, wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die Äquivalenz genau dann, wenn gilt.
  5. Die Theorie heißt vollständig, wenn für jeden Satz gilt oder .
  6. Die Menge aller umfassenden, (aussagenlogisch) maximal widerspruchsfreien Teilmengen

    mit der durch

    gegebenen Erreichbarkeitsrelation und der durch , wenn , festgelegten Belegung heißt das -universelle modallogische Modell.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Henkin.
  2. Der Satz über das Halteproblem.
  3. Der Satz über die Unvollständigkeit der Peano-Arithmetik.


Lösung

  1. 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 .
  2. Die Menge

    ist nicht

    -entscheidbar.
  3. Die erststufige Peano-Arithmetik ist unvollständig.


Aufgabe (1 Punkt)

Beurteile die Snookerweisheit „Ein Snookerspiel kann man in der ersten Session nicht gewinnen, aber verlieren“ vom logischen Standpunkt aus.


Lösung

Es spielen zwei Spieler gegeneinander, der eine gewinnt genau dann, wenn der andere verliert. Wenn einer also in der ersten Session verlieren kann, so kann auch einer (nämlich der andere) in der ersten Session gewinnen. Die Weisheit ist also unlogisch.


Aufgabe (14 (2+5+2+5) Punkte)

Es sei , , eine Familie von Aussagenvariablen und die zugehörige aussagenlogische Sprache. Es sei ein Symbolalphabet bestehend aus den Variablen , , und dem einen Konstantensymbol und es sei die zugehörige prädikatenlogische Sprache. Es sei

  1. Definiere rekursiv eine natürliche Abbildung

    die auf abbildet.

  2. Ist injektiv?
  3. Ist surjektiv?
  4. Zeige für alle , dass (im Ableitungskalkül der Aussagenlogik) genau dann gilt, wenn (im Ableitungskalkül der Prädikatenlogik) gilt.


Lösung

  1. Wir definieren die Abbildung rekursiv über den Aufbau von . Für eine Aussagenvariable setzen wir

    Für

    setzen wir

    und für

    setzen wir

    und entsprechend für .

  2. Wir beweisen die Injektivität in der Form, dass sich aus

    die Verschiedenheit

    ergibt, und zwar durch Induktion über den Aufbau von (simultan für alle ).

    Für

    ist entweder eine andere Aussagenvariable, sagen wir mit oder ein Ausdruck, der zumindest einen aussagenlogischen Junktor enthält. Im ersten Fall ist

    und im zweiten Fall enthält mindestens einen Junktor und ist deshalb von verschieden.

    Sei nun

    und dies sei von verschieden. Wenn keine Negation ist, so ist auch keine Negation und damit von verschieden. Wenn hingegen eine Negation ist, so ist und wegen der Verschiedenheit ist . Nach Induktionsvoraussetzung ist

    und dies überträgt sich auf die negierten Ausdrücke.

    Sei nun

    und dies sei von verschieden. Wenn kein konjugierter Ausdruck ist, so ist auch kein konjugierter Ausdruck und damit ist . Wenn hingegen ebenfalls ein konjugierter Ausdruck ist, so ist und wegen der Verschiedenheit ist oder . Sagen wir der erste Fall liegt vor. Nach Induktionsvoraussetzung ist dann

    und dies überträgt sich auf die konjugierten Ausdrücke.

  3. Die Abbildung ist nicht surjektiv, da der Ausdruck nicht zum Bild gehört, da jedes mindestens eine Aussagenvariable und somit mindestens eine Variable enthält.
  4. Es gelte zunächst

    Dann gibt es eine Ableitung im Aussagenkalkül für diesen Ausdruck. Diese Ableitung beruht allein auf aussagenlogischen Grundtautologien und dem Modus Ponens. Wenn man in dieser Ableitung überall die Aussagenvariablen durch ersetzt, so werden aus den aussagenlogischen Grundtautologien prädikatenlogische Grundtautologien und der Modus Ponens bleibt erhalten. Man erhält also durch diese Ersetzung eine prädikatenlogische Ableitung für und somit ist .

    Wenn hingegen

    gilt, so ist nach dem Vollständigkeitssatz der Aussagenlogik nicht allgemeingültig. Es gibt also eine Wahrheitsbelegung für die Aussagenvariablen derart, dass unter der zugehörigen (aussagenlogischen) Interpretation den Wahrheitswert bekommt. Es sei nun eine zweielementige Menge. Wir definieren eine -Interpretation auf durch

    und

    Mit dieser Festlegung ist genau dann, wenn ist. Da die aussagenlogischen Junktoren unter und gleichermaßen interpretiert werden, ist wegen auch . Daher ist nicht allgemeingültig und kann wegen der Korrektheit des Ableitungkalküls für die Prädikatenlogik auch nicht ableitbar sein. Also .


Aufgabe (5 Punkte)

Es seien einstellige Relationssymbole. Zeige, dass der Modus Barbara, also die Aussage

im Prädikatenkalkül ableitbar ist.


Lösung

Aus aussagenlogischen Gründen (Transitivität der Implikation) gilt

Aus einer ableitbaren Implikation

ergibt sich mittels der Alleinführung im Antezedens

und dem Kettenschluss

und daraus mit der Alleinführung im Sukzedens, die anwendbar ist, da vorne und in gebunden ist,

Angewendet auf die eingangs aufgeführte Situation ergibt dies

Nach Fakt *****  (2) ist

und so kann man vorne die Allaussage der Konjunktion durch die Konjunktion der Allaussagen ersetzen und erhält die Behauptung.


Aufgabe (8 Punkte)

Beweise den Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .


Lösung

Wir betrachten Teilmengen mit den Eigenschaften

  1. Für jedes  , , gibt es ein mit .
  2. Es gibt eine eindeutig bestimmte Abbildung

    mit und

    für alle mit .

Wir betrachten nun die Menge

Wir zeigen durch Induktion, dass ist. Für können wir

wählen, wobei durch die erste Abbildungseigenschaft eindeutig festgelegt ist. Sei nun vorausgesetzt. Das bedeutet, dass es und eine Abbildung mit den angegebenen Eigenschaften gibt. Bei sind wir fertig, sei also . Wir setzen und wir definieren

Dies erfüllt die Eigenschaften und ist auch die einzige Möglichkeit, da die Einschränkung von auf wegen der Eindeutigkeit mit übereinstimmen muss. Also ist .

Wir zeigen nun durch Induktion über , dass unabhängig von der gewählten Menge ist. Bei ist dies klar, sei diese Aussage für ein gewisses schon bekannt, und sei mit zugehörigen Abbildungen . Aufgrund der zweiten Eigenschaft ist , daher ist nach Induktionsvoraussetzung

Damit erhält man durch

mit einem beliebigen eine wohldefinierte Abbildung auf ganz mit den in der Formulierung des Satzes geforderten Eigenschaften. Die Eindeutigkeit von ergibt sich aus der Eindeutigkeit der Einschränkungen.


Aufgabe (4 Punkte)

Es sei ein Symbolalphabet und eine Ausdrucksmenge. Begründe, warum man im Allgemeinen bei der Hinzunahme von Beispielen (innerhalb des Beweises des Vollständigkeitssatzes) nicht für alle Existenzaussagen mit einer einzigen neuen Variablen arbeiten kann.


Lösung

Es sei derart, dass es eine Aussage gibt, für die sowohl als auch zu gehört. Beispielsweise kann man

mit einer Konstanten nehmen. Eine solche Ausdrucksmenge ist widerspruchsfrei, da sie (über jeder Menge mit mindestens zwei Elementen) erfüllbar ist. Wenn man nur eine neue Variable zur Verfügung hat, so muss man die beiden Aussagen und hinzunehmen. Aus der neuen Ausdrucksmenge würde dann sowohl als auch ableitbar sein, und somit wäre widersprüchlich.


Aufgabe (5 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 die Beziehungen

  1. Für welche Personen ist die Äquivalenzklasse zur elementaren Äquivalenz einelementig, für welche nicht?
  2. Bestimme die Automorphismengruppe des Zugabteils.
  3. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Relationen.
  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 diejenigen Äquivalenzklassen, die aus mindestens zwei Personen bestehen.


Lösung

  1. Für sind die Äquivalenzklassen einelementig, die Teilmenge bilden eine Äquivalenzklasse.
  2. Die Automorphismengruppe ist eine zyklische Gruppe der Ordnung , da man und miteinander vertauschen kann und die anderen Personen nicht.
  3. ist diejenige Person, die am Fenster sitzt und eine Fahrkarte klaut.
  4. .
  5. .


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

Die Registerabteilung des VW-Konzerns hat - ohne Wissen des Vorstandes und am Aufsichtsrat vorbei - in jedes real existierende Registerprogramm an einer willkürlich gewählten Stelle die aufeinanderfolgenden Befehlszeilen eingebaut (und dabei die Zeilennummern und die Sprungbefehlsnummern angepasst, ist die Nummer eines in nicht verwendeten Registers und ist die neue Haltebefehlsnummer)

  1. Ändert sich durch diese Manipulation die Halteeigenschaft des Programms?
  2. Ändert sich durch diese Manipulation die Programmabbildung?
  3. Nachdem der Skandal herauskommt und die Öffentlichkeit eine Erklärung fordert, diskutieren Vorstand, Aufsichtsrat und Abteilungsleiter die folgenden möglichen Stellungsnahmen für die anstehende Pressekonferenz:
    a) Man wollte Speicherplatz sparen.

    b) Man wollte aus Werbezwecken erreichen, dass jedes Registerprogramm mindestens einmal „VW“ ausdruckt.

    c) Man wollte einen Beitrag zur Entschleunigung leisten, indem man manche Programme etwas langsamer macht.

    d) Man wollte einen Beitrag zur Entschleunigung leisten, indem man alle Programme etwas langsamer macht.
    Welche dieser Erklärungen passen inhaltlich zu den Manipulationen?


Lösung

  1. Nein. Da die Zeilennummern angepasst werden, wird der neue Programmabschnitt (wenn überhaupt) von Anfang an durchlaufen und wenn der Befehl abgearbeitet wird ist das -te Register nicht leer, also wird nicht zum Haltebefehl gewechselt, und das Programm läuft einfach weiter.
  2. Ja, und zwar schon deshalb, da sich die Anzahl der Programmzeilen ändert.
  3. Da ein Register mehr verwendet wird, wird kein Speicherplatz gespart und da der zusätzliche Befehl den Inhalt des ersten Registers ausdruckt, dessen Inhalt aber eine Zahl und nicht „VW“ ist, sind a) und b) inhaltlich unpassend. Da das neue Programm zusätzliche Befehle abarbeitet, wird das Programm langsamer, allerdings nur, wenn der neue Programmabschnitt auch durchlaufen wird. Es kann aber durch Sprungbefehle sein, dass der neue Programmabschnitt übersprungen wird. Daher ist nur c) richtig.


Aufgabe (4 Punkte)

Erläutere die Unentscheidbarkeit der Arithmetik und skizziere in Grundzügen, wie man sie beweisen kann.


Lösung Unentscheidbarkeit der Arithmetik/Erläuterung/Aufgabe/Lösung


Aufgabe (4 Punkte)

Es sei eine fixierte natürliche Zahl und

wobei durch die -fache Summe der mit sich selbst realisiert werde. Zeige direkt, dass es Sätze mit

und mit

gibt.


Lösung

Es gibt unendlich viele arithmetische Sätze, die bei der Interpretation in gültig sind und unendlich viele arithmetische Sätze, die bei der Interpretation in ungültig sind. Insbesondere gibt es solche Sätze, deren Gödelnummer nicht ist. Sei nun ein in ungültiger Satz, dessen Gödelnummer nicht ist. Dann ist

also

Wenn hingegen ein in gültiger Satz ist, dessen Gödelnummer nicht ist, so ist

also


Aufgabe (3 Punkte)

Zeige, dass im -System der Ausdruck

ableitbar ist.


Lösung

Das Distributionsaxiom liefert

Dabei ist aufgrund der Kontraposition und Fakt *****  (1) der Vordersatz äquivalent zu

Nach Kontraposition ist der Nachsatz äquivalent zu

was gerade

bedeutet. Es ergibt sich also die Ableitung


Aufgabe (7 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Löb-Axiom genau dann gilt, wenn transitiv ist und es in keine unendlichen Ketten gibt.


Lösung

Wir arbeiten mit der Kontraposition des Löb-Axioms, also mit

Sei zunächst vorausgesetzt, dass die graphentheoretischen Eigenschaften besitzt. Sei und

Dann gibt es eine Welt mit und mit

Wir betrachten Ketten mit . Da es keine unendliche Kette gibt, bricht eine solche Kette ab, sagen wir in . In gilt dann

Wegen der Transitivität ist von aus erreichbar und somit ist

Sei nun vorausgesetzt, dass nicht die Eigenschaften erfüllt. Wenn nicht transitiv ist, so ist nach Fakt ***** in Verbindung mit Fakt ***** die Gültigkeit des Löb-Axioms ausgeschlossen. Es sei also eine unendlich lange Kette der Form gegeben. Wir belegen für alle und für alle anderen Welten. Dann gilt

da außerhalb der Kette stets gilt und innerhalb der Kette stets gilt.