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


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




Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Ableitbarkeit eines Aussage aus einer Aussagenmenge in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge .
  2. Eine -stellige Relation auf einer Menge .
  3. Die Folgerungsbeziehung , wobei eine Menge von - Ausdrücken und ein -Ausdruck ist (und ein Symbolalphabet.)
  4. Die Termsubstitution für -Terme (dabei sei ein Symbolalphabet einer Sprache erster Stufe, paarweise verschiedene Variablen und fixierte - Terme).
  5. Die Addition in einem Dedekind-Peano-Modell .
  6. Die Register-Entscheidbarkeit einer Teilmenge .



Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Substitutionslemma.
  2. Der Satz über das Halteproblem.
  3. Der Fixpunktsatz für arithmetische Ausdrücke.



Aufgabe * (1 Punkt)

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

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



Aufgabe * (4 (2+2) Punkte)

Es sei eine unendliche Menge und die Menge, die aus sämtlichen endlichen Teilmengen von besteht.

  1. Ist induktiv geordnet?
  2. Besitzt maximale Elemente?



Aufgabe * (9 (1+3+2+1+2) Punkte)

Es sei die prädikatenlogische Sprache, die neben Variablen aus einem zweistelligen Relationssymbol und einem dreistelligen Relationssymbol bestehe. Wir betrachten - Interpretationen , wobei die Grundmenge jeweils aus einem Vektorraum über einem Körper bestehe und als die lineare Unabhängigkeit von zwei und als die lineare Unabhängigkeit von drei Vektoren interpretiert werde.

  1. Zeige
  2. Gilt

    für einen beliebigen Vektorraum?

  3. Gibt es Vektorräume, für die die Aussage in Teil 2 gilt?
  4. Es sei und sei die Standardbasis. Gilt
  5. Es sei als -Vektorraum betrachtet. Gilt



Aufgabe * (4 Punkte)

Zeige durch ein Beispiel, dass für Terme und eine Variable einer prädikatenlogischen Sprache der Ausdruck

nicht ableitbar sein muss.



Aufgabe * (6 (3+1+2) Punkte)

Es seien Variablen und und .

  1. Zeige (ohne Bezug auf den Vollständigkeitssatz) .
  2. Charakterisiere die Modelle mit .
  3. Zeige .



Aufgabe * (7 Punkte)

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



Aufgabe * (7 Punkte)

Es sei ein Symbolalphabet und eine - Interpretation auf einer Menge , wobei die Terminterpretation surjektiv sei. Zeige, dass die Gültigkeitsmenge maximal widerspruchsfrei ist und Beispiele enthält.



Aufgabe (2 Punkte)

Man gebe ein Beispiel für eine mathematische Begriffsbildung, die als - Homomorphismus zu einem geeigneten Symbolalphabet verstanden werden kann.



Aufgabe * (3 Punkte)

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



Aufgabe (3 Punkte)

Erläutere die Churchsche These.



Aufgabe * (12 Punkte)

Es sei eine arithmetische Ausdrucksmenge und eine Relation. Es seien Ausdrücke in einer freien Variablen . Zeige, dass aus

nicht folgt, dass in die Relation genau dann repräsentiert, wenn in die Relation repräsentiert.