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


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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Termmenge zu einer Grundtermmenge .
  2. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge .
  3. Die Multiplikation mit in einem Dedekind-Peano-Modell .
  4. Die Befehle für eine Registermaschine.
  5. Das modallogische Löb-Axiom.
  6. Ein modallogisches Modell.


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Lemma von Zorn.
  2. Der Vollständigkeitssatz für Tautologien (Prädikatenlogik).
  3. Der zweite Gödelsche Unvollständigkeitssatz.


Aufgabe * (2 (1+1) Punkte)

Im Pokal spielt Bayern München gegen den TSV Wildberg. Der Trainer vom TSV Wildberg, Herr Tor Acker, sagt „Wir haben in dem Spiel nichts zu verlieren“. Die Logiklehrerin von Wildberg, Frau Loki Schummele, sagt „Wenn die Wildberger in dem Spiel nichts zu verlieren haben, dann haben auch die Münchner in dem Spiel nichts zu gewinnen“. Der Trainer von Bayern München, Herr Roland Rollrasen, sagt „Wir haben in dem Spiel etwas zu gewinnen“.

  1. Ist die Aussage von Frau Schummele logisch korrekt?
  2. Es sei vorausgesetzt, dass die Aussage des Bayerntrainers wahr ist. Welche Folgerung kann man dann für die Aussage von Herrn Acker ziehen?


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

  1. Löse das folgende Minisudoku
  2. Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
  3. Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?


Aufgabe * (3 Punkte)

Beweise durch Induktion über den rekursiven Aufbau der Sprache , dass in jeder Aussage die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.


Aufgabe * (3 Punkte)

Zeige, dass eine Regel der Form

Wenn , dann gelten kann, ohne dass gilt.


Aufgabe * (4 Punkte)

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


Aufgabe * (7 (3+4) Punkte)

Es sei eine Variablenmenge, eine Konstante und zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck , der durch

gegeben ist.

  1. Zeige, dass bei Interpretation in einem Körper wahr wird, wenn man als und als Subtraktion, Addition und Multiplikation interpretiert.
  2. Welcher wichtige mathematische Satz verbirgt sich dahinter?


Aufgabe * (6 Punkte)

Beweise die Termaussage des Substitutionslemmas.


Aufgabe * (2 Punkte)

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet , dass ein Untervektorraum in einem Vektorraum über einem Körper vorliegt.


Aufgabe * (4 Punkte)

Zeige, dass in einem Peano-Halbring zu die Division mit Rest eindeutig ist.


Aufgabe (4 Punkte)

Beschreibe die wesentlichen Punkte bei der Konstruktion eines Modells, mit dem man die Erfüllbarkeit einer maximal widerspruchsfreien Ausdrucksmenge, die Beispiele enthält, nachweist.


Aufgabe * (3 Punkte)

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


Aufgabe * (6 Punkte)

Es sei eine endliche Teilmenge. Man gebe ein Programm für eine Registermaschine an, das nur auf einen einzigen Register Bezug nimmt, das bei jeder Eingabe (in ) immer anhält und das im Anhaltezustand in genau dann den Wert besitzt, wenn die Eingabe zu gehört.


Aufgabe * (4 Punkte)

Es sei

eine arithmetisch repräsentierbare Abbildung. Zeige, dass zu jedem Punkt die Faser

arithmetisch repräsentierbar ist.


Aufgabe * (5 Punkte)

Zeige, dass eine aufzählbar axiomatisierbare Theorie auch -aufzählbar ist.