Kurs:Einführung in die mathematische Logik/17/Klausur



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



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.


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Henkin.
  2. Der Satz über das Halteproblem.
  3. Die Unentscheidbarkeit der Arithmetik.


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?


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


Aufgabe (2 Punkte)

Erläutere die Beziehung zwischen dem Modus ponens und


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 .


Aufgabe * (5 (2+2+1) Punkte)

Es sei ein einstelliges Funktionssymbol, und seien zweistellige Funktionssymbole und seien Variablen.

Wir betrachten die folgenden Modelle (wobei die Grundmenge bezeichnet).

a) , ist die Quadrierung, die Addition und die Multiplikation.


b) , ist das Differenzieren von Funktionen, die Multiplikation und die Addition von Funktionen. Bestimme, ob in diesen Modellen die folgenden Aussagen wahr werden.


Aufgabe * (2 Punkte)

Es sei ein Symbolalphabet erster Stufe mit der Variablenmenge

gegeben und eine - Interpretation in der Menge mit

Bestimme die Werte von bei der Interpretation auf .


Aufgabe * (3 Punkte)

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

  1. Bestimme
  2. Bestimme
  3. Bestimme


Aufgabe * (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.


Aufgabe * (2 Punkte)

Zeige, dass in einem kommutativen Halbring die Beziehung gilt.


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.


Aufgabe * (4 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe zum Symbolalphabet .


Aufgabe (5 Punkte)

Man entwerfe ein Programm für eine Registermaschine, das bei der Eingabe im ersten Register den Rest bei der Division mit Rest von durch ausgibt.


Aufgabe * (3 (2+1) Punkte)

  1. Zeige, dass die Teilmenge der natürlichen Zahlen, die man als Summe von drei Quadraten schreiben kann, arithmetisch repräsentierbar ist.
  2. Formuliere in der arithmetischen Sprache, dass die keine Summe von drei Quadraten ist.


Aufgabe * (3 Punkte)

Beweise den ersten Gödelschen Unvollständigkeitssatz mit dem Unvollständigkeitslemma.


Aufgabe * (2 Punkte)

Zeige, dass in der - Modallogik das Schema

ableitbar ist.


Aufgabe * (2 Punkte)

Wir arbeiten mit den Aussagenvariablen . Im Weltpunkt gelte

und im Weltpunkt gelte

Bestimme die Wahrheitswerte von in den beiden Weltpunkten.


Aufgabe * (4 Punkte)

Beweise den Vollständigkeitssatz der Modallogik.