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

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe. Bei 3.-7. bedeutet ein Symbolalphabet einer prädikatenlogischen Sprache erster Stufe.

  1. Ein Primzahlzwilling.
  2. Die Bestandteile einer Grundtermmenge.
  3. Eine -Struktur zu einem Symbolalphabet einer Sprache erster Stufe.
  4. Ein allgemeingültiger prädikatenlogischer Ausdruck .
  5. Ein -Homomorphismus

    zwischen zwei -Strukturen und .

  6. Eine arithmetisch repräsentierbare Relation .


Aufgabe * (4 Punkte)

Formuliere die folgenden Sätze.

  1. Der Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.
  2. Der Vollständigkeitssatz der Prädikatenlogik.
  3. Die Unentscheidbarkeit der Arithmetik.
  4. Der erste Gödelsche Unvollständigkeitssatz.


Aufgabe * (1 Punkt)

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

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


Aufgabe * (3 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge und es seien . Zeige, dass

zu

äquivalent ist.


Aufgabe * (6 Punkte)

Man gebe ein Beispiel für eine mathematische Existenzaussage, die mit dem Lemma von Zorn bewiesen wird, und führe den Beweis durch.


Aufgabe * (1 Punkt)

Erstelle einen prädikatenlogischen Ausdruck , der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau Elemente besitzt.


Aufgabe * (4 Punkte)

Es sei das arithmetische Alphabet zusammen mit der Variablenmenge gegeben. Interpretiere den Term

unter den folgenden Interpretationen, wobei die Grundmenge der Interpretation bezeichne.

  1. mit der Standardinterpretation und der Variablenbelegung und .
  2. mit der Standardinterpretation

    und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung und .

  3. , mit

    und wo sowohl als auch als Subtraktion interpretiert werden.

  4. Potenzmenge von mit

    und wo als und als interpretiert wird.


Aufgabe * (12 (1+1+4+2+4) Punkte)

Es sei ein dreistelliges Relationssymbol und die zugehörige prädikatenlogische Sprache. Es sei die Interpretation, bei der die Grundmenge die euklidische Ebene ist und durch die dreistellige Relation interpretiert wird, bei der zutrifft, wenn die Punkte auf einer Geraden liegen.

  1. Zeige .
  2. Zeige, dass im Allgemeinen nicht gelten muss.
  3. Es sei . Erstelle eine Ableitung für .
  4. Zeige, dass der Ausdruck bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.
  5. Formuliere einen Ausdruck aus in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.


Aufgabe (3 Punkte)

Erläutere den Begriff Sortenprädikat an einem mathematischen Beispiel.


Aufgabe * (2 Punkte)

Man gebe ein Beispiel für einen kommutativen Halbring, der kein Peano-Halbring ist.


Aufgabe (6 (3+3) Punkte)

  1. Entwerfe ein Programm für eine Registermaschine, das die Potenz berechnet, wobei und die Inhalte im -ten bzw. -ten Register sind.
  2. Entwerfe ein Programm für eine Registermaschine, das entscheidet, ob der Registerinhalt des Registers die echte Potenz einer natürlichen Zahl ist.


Aufgabe * (5 Punkte)

Es sei eine Teilmenge von natürlichen Zahlen. Zeige, dass genau dann -entscheidbar ist, wenn sowohl als auch das Komplement -aufzählbar ist.


Aufgabe * (6 Punkte)

Man gebe für die Abbildung

mit

einen Ausdruck an, der arithmetisch repräsentiert.


Aufgabe * (7 Punkte)

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

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