Kurs:Einführung in die mathematische Logik/16/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 16 17
Punkte 3 3 4 0 22 5 0 3 3 0 0 3 0 0 0 0 0 46



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.
  2. Ein Ideal in einem kommutativen Ring .
  3. Die Variablensubstitution für einen -Ausdruck , wobei Variablen und fixierte -Terme seien.
  4. Die Ableitbarkeit eines Ausdrucks im prädikatenlogischen Kalkül.
  5. Die Arithmetische Repräsentierbarkeit einer Abbildung
  6. Eine (formale) Modallogik.


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. /Fakt/Name
  2. Der Endlichkeitssatz für die Prädikatenlogik.
  3. /Fakt/Name


Aufgabe (4 (1+3) Punkte)

In einer Höhle befinden sich im Innern am Ende des Ganges vier Personen. Sie haben eine Taschenlampe bei sich und der Gang ins Freie kann nur mit der Taschenlampe begangen werden. Dabei können höchstens zwei Leute gemeinsam durch den Gang gehen. Die Personen sind unterschiedlich geschickt, die erste Person benötigt eine Stunde, die zweite Person benötigt zwei Stunden, die dritte Person benötigt vier Stunden und die vierte Person benötigt fünf Stunden, um den Gang zu durchlaufen. Wenn zwei Personen gleichzeitig gehen, entscheidet die langsamere Person über die Geschwindigkeit.

  1. Die Batterie für die Taschenlampe reicht für genau Stunden. Können alle vier die Höhle verlassen?
  2. Die Batterie für die Taschenlampe reicht für genau Stunden. Können alle vier die Höhle verlassen?


Aufgabe (0 Punkte)


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

Es sei eine (nichtleere) Aussagenvariablenmenge und

die Menge aller Wahrheitsbelegungen auf . In dieser Aufgabe untersuchen wir und die Abbildung

Dabei spielen die beiden folgenden Teilmengen eine Rolle.

Es sei die folgendermaßen festgelegte Teilmenge. Eine Abbildung gehört genau dann zu , wenn es eine endliche Teilmenge derart gibt, dass ist (dies ist in Aufgabenteil 2 zu erläutern).

Es sei die durch die folgenden Bedingungen rekursiv festgelegte Teilmenge.

a) Zu gehört

zu .


b) Wenn ist, so gehört auch zu , wobei die Vertauschungsabbildung bezeichnet.


c) Wenn sind, so gehören auch und zu .

  1. Ist injektiv?
  2. Es sei eine Teilmenge. Zeige, dass es eine natürliche surjektive Abbildung

    und eine natürliche injektive Abbildung

  3. Zeige, dass die in (2) beschriebene Abbildung

    die Evaluationen , die Verknüpfung mit und die Minima und Maxima respektiert.

  4. Man gebe bei unendlich ein an, das nicht zu gehört.
  5. Es sei endlich. Zeige
  6. Zeige .
  7. Zeige, dass das Bild von mit übereinstimmt.


Aufgabe * (5 Punkte)

Es sei eine endliche Menge an Aussagen. Skizziere ein Entscheidungsverfahren, mit dem man feststellen kann, ob widersprüchlich ist oder nicht.


Aufgabe (0 Punkte)


Aufgabe (3 Punkte)

Es sei eine Aussage(nform), in die man eine natürliche Zahl einsetzen kann. Diskutiere den Unterschied zwischen den beiden Aussagen

Was ist die mathematische Relevanz der beiden Aussagen?


Aufgabe * (3 Punkte)

Wir rechnen mit den Zahlen nach den folgenden Verknüpfungstabellen.

und


Zeige, dass es sich dabei um einen kommutativen Halbring handelt. Gilt für diesen die Abziehregel?


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)


Aufgabe * (3 Punkte)

Erstelle ein Programm für eine Registermaschine, das abwechselnd und ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Sprungbefehl verwendet.


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)