Kurs:Einführung in die mathematische Logik/17/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 16 17
Punkte 3 3 2 2 2 2 2 3 0 2 8 0 0 0 0 0 0 29




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge .
  2. Ein topologischer Filter auf einem topologischen Raum .
  3. Die Interpretation der Terme zu einem Symbolalphabet in einer gegebenen -Interpretation auf einer Grundmenge .
  4. Eine funktional abgeschlossene Teilmenge einer -Struktur , wobei ein erststufiges Symbolalphabet bezeichnet.
  5. Eine vollständige Theorie .
  6. Ein modallogisches Modell.


Lösung

  1. Die Menge heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks die Menge widersprüchlich macht.
  2. Ein System aus offenen Teilmengen von heißt Filter, wenn folgende Eigenschaften gelten ( seien offen).
    1. .
    2. Mit und ist auch .
    3. Mit und ist auch .
  3. Die Terminterpretation wird induktiv über den Aufbau der Terme für jeden -Term definiert.
    1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
    2. Wenn Terme mit Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.
  4. Die Teilmenge heißt funktional abgeschlossen, wenn für jede Konstante das Element zu gehört und für jedes -stellige Funktionssymbol und beliebige Elemente auch zu gehört.
  5. Die Theorie heißt vollständig, wenn für jeden Satz gilt oder .
  6. Unter einem modallogischen Modell versteht man einen gerichteten Graphen zusammen mit einer Wahrheitsbelegung für die Aussagenvariablen für jeden Knotenpunkt .


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Henkin.
  2. Der Satz über das Halteproblem.
  3. Die Unentscheidbarkeit der 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 Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht -entscheidbar.


Aufgabe (2 Punkte)

wurde ermordet. Es gelten folgende Sachverhalte.

  1. Der Mörder ist oder oder oder .
  2. Wenn der Mörder ist, dann ist nicht der Mörder oder ist der Mörder.
  3. sind alle verschieden.
  4. Es gibt genau einen Mörder.
  5. Wenn nicht der Mörder ist, dann ist nicht der Mörder.
  6. ist genau dann der Mörder, wenn der Mörder ist.

Wer ist der Mörder?


Lösung

Aus (6), (3) und (4) folgt, dass und beide nicht der Mörder sind, denn sonst wären beide der Mörder. Nach (5) ist somit auch nicht der Mörder. Wegen (1) muss also der Mörder sein. ((2) wird nicht verwendet)


Aufgabe (2 Punkte)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

w w w w
w w f f
w f w w
w f f f
f w w f
f w f w
f f w f
f f f w


Lösung


Aufgabe (2 Punkte)

Erläutere die Beziehung zwischen dem Modus Ponens und


Lösung Modus Ponens/Interne Version/Erläuterung/Aufgabe/Lösung


Aufgabe (2 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Begründe die Widerspruchsregel für die Ableitungsbeziehung: Wenn und , dann ist auch .


Lösung

Es gilt

nach Axiom *****  (5). Nach der Voraussetzung und Fakt *****  (5) ergibt sich daraus .


Aufgabe (2 Punkte)

Es sei ein Symbolalphabet erster Stufe mit der Variablenmenge

gegeben und eine -Interpretation in der Menge mit

Bestimme die Werte von auf .


Lösung

Es ist

Ferner ist dieser Ausdruck von innen nach außen, bzw. von links nach rechts zu lesen, also als

Daher ist


Aufgabe (3 Punkte)

Es seien Variablen (mit der angegebenen Reihenfolge), eine Konstante und ein einstelliges Funktionssymbol.

  1. Bestimme
  2. Bestimme
  3. Bestimme


Lösung

Die zu substituierende Variable kommt im Ausdruck nicht frei vor. Somit ist jedenfalls für den jeweiligen Term

Da die relevante Termmenge leer ist, ist

Also ist


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (2 Punkte)

Zeige, dass in einem kommutativen Halbring die Beziehung gilt.


Lösung

Dies ergibt sich aus


Aufgabe (8 (1+2+3+2) Punkte)

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Es sei eine -Interpretation mit der Grundmenge und es sei mit der zugehörigen Äquivalenzrelation auf der Termmenge .

  1. Zeige, dass genau dann gilt, wenn gilt.
  2. Zeige, dass es eine injektive Abbildung

    mit

    gibt.

  3. Zeige, dass ein -Homomorphismus ist, wenn die Quotientenmenge mit der kanonischen -Struktur versehen wird.
  4. Es sei die kanonische Interpretation auf . Es sei vorausgesetzt, dass die Terminterpretation für surjektiv sei. Zeige, dass genau dann gilt, wenn gilt.


Lösung

  1. Es ist genau dann, wenn ist, und dies ist genau dann der Fall, wenn gilt, was nach Definition bedeutet.
  2. Die Termabbildung

    besitzt nach Teil (1) die Eigenschaft, dass äquivalente Terme auf das gleiche Element abgebildet werden. Dies bedeutet nach Fakt *****, dass es eine Abbildung

    mit gibt. Da nichtäquivalente Terme nach Teil (1) unter auf verschiedene Elemente abgebildet werden, werden verschiedene Klassen unter auf verschiedene Elemente abgebildet und somit ist injektiv.

  3. Sei

    Für eine Konstante ist

    Für ein -stelliges Funktionssymbol und Termklassen ist

    Sei nun eine -stellige Relation und Termklassen gegeben und sei die Gültigkeit von in vorausgesetzt. Dies bedeutet, dass ist. Somit ist , was bedeutet. Somit ist . Es liegt also ein -Homomorphismus vor.

  4. Nach Definition von ist genau dann, wenn gilt. Nach Fakt ***** ist maximal widerspruchsfrei und enthält Beispiele und nach dem Satz von Henkin ist


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


Lösung /Aufgabe/Lösung