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

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein maximales Element in einer geordneten Menge .
  2. Die Termsubstitution für -Terme (dabei sei ein Symbolalphabet einer Sprache erster Stufe, paarweise verschiedene Variablen und fixierte -Terme).
  3. Der Rang eines prädikatenlogischen Ausdrucks .
  4. Die elementare Äquivalenz von zwei -Strukturen und über einem erststufigen Symbolalphabet .
  5. Eine -berechenbare Funktion
  6. Die -Funktion .


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Euklid über Primzahlen.
  2. Das Substitutionslemma.
  3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .


Aufgabe * (4 Punkte)

Hanny, Nanny, Fanny und Sanny leben auf dem Ponyhof. Heute machen sie einen Ausflug mit den Ponies Pona, Pone, Pono und Ponu. Jedes der Mädchen sitzt dabei genau auf einem Pony, und sie reiten hintereinander. Folgende Fakten sind bekannt.

  1. Fanny sitzt nicht auf Pona.
  2. Pone und Ponu vertragen sich nicht so gut und laufen daher nicht direkt hintereinander.
  3. Nanny sitzt auf Pone oder auf Pono.
  4. Sanny reitet auf Pona oder auf Pone.
  5. Nanny reitet direkt hinter Sanny.
  6. Auf Ponu sitzt nicht Sanny.
  7. Pona läuft direkt zwischen Pone und Pono.
  8. Auf Pono sitzt weder Fanny noch Hanny.
  9. Sanny reitet weiter vorne als Hanny.

Wer sitzt auf welchem Pony und in welcher Reihenfolge laufen sie?


Aufgabe (2 Punkte)

Man gebe signifikante Beispiele zum Stichwort „Fortsetzung einer Abbildung“ aus der Mathematik und aus der mathematischen Logik.


Aufgabe * (4 (1+3) Punkte)

Wir betrachten Wörter über dem Alphabet und den Prozess , der in einem solchen Wort jedes Vorkommen von durch das Wort ersetzt.

  1. Bestimme das Ergebnis von unter diesem Prozess.
  2. Diesen Prozess kann man iterieren. Mit bezeichnen wir das Ergebnis, wenn man den Prozess -mal hintereinander auf das Startwort anwendet. Bestimme die Anzahl der Buchstaben in zum Startwort .


Aufgabe * (3 Punkte)

Es sei die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge und es sei eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation . Zeige, dass maximal widerspruchsfrei ist.


Aufgabe * (4 Punkte)

Es seien einstellige Relationssymbole. Erstelle eine Ableitung im Prädikatenkalkül für den Modus Disamis, also die Aussage


Aufgabe * (3 Punkte)

In einem angeordneten Körper ist durch

eine zweistellige Relation gegeben. Drücke diese Relation mit den üblichen Symbolen , Variablen und aussagenlogischen Junktoren aus.


Aufgabe * (8 Punkte)

Beweise den Satz von Henkin.


Aufgabe * weiter

Es sei das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol besteht. Wir betrachten die KO-Runden (also ab dem Achtelfinale) der Fußballweltmeisterschaften von 2014 und von 2018, ohne das Spiel um Platz , als -Modelle, wobei wir als die Gewinnrelation interpretieren, d.h. besagt, dass gegen (gespielt und) gewonnen hat.

  1. Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
  2. Ist eine Charakterisierung des Weltmeisters?
  3. Charakterisiere durch einen -Ausdruck in der einen freien Variablen , dass eine Mannschaft mindestens das Halbfinale erreicht hat.
  4. Charakterisiere durch einen -Ausdruck in der einen freien Variablen , dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
  5. Betrachte Schweden bei der WM 2018. Man gebe einen -Ausdruck in der einen freien Variablen , der Schweden charakterisiert.
  6. Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den -Ausdruck, der Schweden bei der WM 2018 charakterisiert?
  7. Definiere einen -Isomorphismus zwischen der WM 2014 und der WM 2018.
  8. Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz mitberücksichtigt?


Aufgabe * (5 Punkte)

Schreibe einen Programmabschnitt für eine Registermaschine, das zum Befehl wechselt, wenn im -ten Register der Wert steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.


Aufgabe (3 Punkte)

Es seien aufzählbar axiomatisierbare Theorien. Zeige, dass dann auch aufzählbar ist.


Aufgabe * (6 Punkte)

Es sei

die Menge der geraden natürlichen Zahlen. Es sei die Ausdrucksmenge, die besagt, dass eine assoziative, kommutative Verknüpfung mit als neutralem Element ist. Es sei

Zeige, dass durch in schwach repräsentiert wird, aber nicht stark.


Aufgabe * (2 Punkte)

Es sei eine arithmetische Ausdrucksmenge und ein einstelliges Prädikat mit

für alle . Zeige, dass es einen Satz mit

gibt.


Aufgabe * (4 Punkte)

Beweise das Unvollständigkeitslemma.