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

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die zu einer (aussagenlogischen) Wahrheitsbelegung

    auf einer Aussagenvariablenmenge zugehörige Interpretation auf der Sprache .

  2. Das Alphabet einer Sprache erster Stufe.
  3. Ein Nichtstandardmodell zu einem fixierten -Modell .
  4. Die Arithmetische Repräsentierbarkeit einer Abbildung
  5. Eine vollständige Theorie .
  6. Das universelle modallogische Modell zu einem -modallogischen System .


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Henkin.
  2. Der Satz über das Halteproblem.
  3. Der Satz über die Unvollständigkeit der Peano-Arithmetik.


Aufgabe * (1 Punkt)

Beurteile die Snookerweisheit „Ein Snookerspiel kann man in der ersten Session nicht gewinnen, aber verlieren“ vom logischen Standpunkt aus.


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

Es sei , , eine Familie von Aussagenvariablen und die zugehörige aussagenlogische Sprache. Es sei ein Symbolalphabet bestehend aus den Variablen , , und dem einen Konstantensymbol und es sei die zugehörige prädikatenlogische Sprache. Es sei

  1. Definiere rekursiv eine natürliche Abbildung

    die auf abbildet.

  2. Ist injektiv?
  3. Ist surjektiv?
  4. Zeige für alle , dass (im Ableitungskalkül der Aussagenlogik) genau dann gilt, wenn (im Ableitungskalkül der Prädikatenlogik) gilt.


Aufgabe * (5 Punkte)

Es seien einstellige Relationssymbole. Zeige, dass der Modus Barbara, also die Aussage

im Prädikatenkalkül ableitbar ist.


Aufgabe * (8 Punkte)

Beweise den Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .


Aufgabe * (4 Punkte)

Es sei ein Symbolalphabet und eine Ausdrucksmenge. Begründe, warum man im Allgemeinen bei der Hinzunahme von Beispielen (innerhalb des Beweises des Vollständigkeitssatzes) nicht für alle Existenzaussagen mit einer einzigen neuen Variablen arbeiten kann.


Aufgabe * (5 Punkte)

In einem Zugabteil sitzen die sechs Personen . Wir betrachten die folgenden Relationen:

  1. bedeutet, dass über die deutsche Bahn motzt.
  2. bedeutet, dass einen Fensterplatz hat.
  3. bedeutet, dass der Person die Fahrkarte klaut.

Es gelten die Beziehungen

  1. Für welche Personen ist die Äquivalenzklasse zur elementaren Äquivalenz einelementig, für welche nicht?
  2. Bestimme die Automorphismengruppe des Zugabteils.
  3. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Relationen.
  4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .
  5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen diejenigen Äquivalenzklassen, die aus mindestens zwei Personen bestehen.


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

Die Registerabteilung des VW-Konzerns hat - ohne Wissen des Vorstandes und am Aufsichtsrat vorbei - in jedes real existierende Registerprogramm an einer willkürlich gewählten Stelle die aufeinanderfolgenden Befehlszeilen eingebaut (und dabei die Zeilennummern und die Sprungbefehlsnummern angepasst, ist die Nummer eines in nicht verwendeten Registers und ist die neue Haltebefehlsnummer)

  1. Ändert sich durch diese Manipulation die Halteeigenschaft des Programms?
  2. Ändert sich durch diese Manipulation die Programmabbildung?
  3. Nachdem der Skandal herauskommt und die Öffentlichkeit eine Erklärung fordert, diskutieren Vorstand, Aufsichtsrat und Abteilungsleiter die folgenden möglichen Stellungsnahmen für die anstehende Pressekonferenz:
    a) Man wollte Speicherplatz sparen.

    b) Man wollte aus Werbezwecken erreichen, dass jedes Registerprogramm mindestens einmal „VW“ ausdruckt.

    c) Man wollte einen Beitrag zur Entschleunigung leisten, indem man manche Programme etwas langsamer macht.

    d) Man wollte einen Beitrag zur Entschleunigung leisten, indem man alle Programme etwas langsamer macht.
    Welche dieser Erklärungen passen inhaltlich zu den Manipulationen?


Aufgabe (4 Punkte)

Erläutere die Unentscheidbarkeit der Arithmetik und skizziere in Grundzügen, wie man sie beweisen kann.


Aufgabe * (4 Punkte)

Es sei eine fixierte natürliche Zahl und

wobei durch die -fache Summe der mit sich selbst realisiert werde. Zeige direkt, dass es Sätze mit

und mit

gibt.


Aufgabe * (3 Punkte)

Zeige, dass im -System der Ausdruck

ableitbar ist.


Aufgabe * (7 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Löb-Axiom genau dann gilt, wenn transitiv ist und es in keine unendlichen Ketten gibt.