Kurs:Einführung in die mathematische Logik/1/Klausur mit Lösungen

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 .

Lösung

  1. Ein Primzahlzwilling ist ein Paar bestehend aus und , wobei diese beiden Zahlen Primzahlen sind.
  2. Die Bestandteile einer Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.
    1. eine Variablenmenge ,
    2. eine Konstantenmenge ,
    3. zu jedem eine Menge von Funktionssymbolen.
  3. Unter einer -Struktur versteht man eine nichtleere Menge mit den folgenden Festlegungen.
    1. Für jede Konstante ist ein Element festgelegt.
    2. Zu jedem -stelligen Funktionssymbol (aus ) ist eine -stellige Funktion

      festgelegt.

    3. Zu jedem -stelligen Relationssymbol (aus ) ist eine -stellige Relation

      festgelegt.

  4. Man nennt allgemeingültig, wenn er in jeder -Interpretation gilt.
  5. Die Abbildung

    heißt -Homomorphismus, wenn folgende Eigenschaften gelten.

    1. Für jede Konstante ist
    2. Für jedes -stellige Funktionssymbol ist

      für alle .

    3. Für jedes -stellige Relationsymbol impliziert die Gültigkeit von

      die Gültigkeit von

  6. Die Relation heißt arithmetisch repräsentierbar, wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die Äquivalenz genau dann, wenn gilt.


 

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.

Lösung

  1. Es seien und Dedekind-Peano-Modelle für die natürlichen Zahlen. Dann gibt es eine eindeutig bestimmte bijektive Abbildung

    mit und

    für alle .
  2. Es sei ein Symbolalphabet, eine Menge an -Ausdrücken und ein weiterer -Ausdruck. Dann gilt genau dann, wenn gilt.
  3. Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht -entscheidbar.
  4. Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube. Dann ist unvollständig.


 

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

Lösung

.


 

Aufgabe * (3 Punkte)

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

zu

äquivalent ist.

Lösung

Die Ableitungsbeziehung

bedeutet, dass es Ausdrücke mit

gibt. Aufgrund der aussagenlogischen Tautologie

ist dies äquivalent zu

Dies bedeutet gerade


 

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.

Lösung

Beispielsweise wird der Existenzsatz für maximale Ideale in einem kommutativen Ring mit dem Lemma von Zorn bewiesen. Der Beweis geht so:

Wir betrachten die Menge

Diese Menge enthält das Nullideal und ist somit nicht leer. Wir wollen das Lemma von Zorn auf (mit der Inklusion als Ordnungsrelation) anwenden. Dazu sei eine total geordnete Teilmenge. Wir setzen

Man zeigt nun, dass ein Ideal ist, das nicht die enthält. Also gehört es zu und es bildet eine obere Schranke für . Das Lemma von Zorn liefert dann maximale Elemente in , und dies sind maximale Ideale.


 

Aufgabe * (1 Punkt)

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

Lösung


 

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.

Lösung

  1. Es ist
  2. Es ist
  3. Es ist
  4. Es ist


 

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.

Lösung

  1. Die Eigenschaft, ob drei Punkte auf einer Geraden liegen, hängt nicht von der Reihenfolge der Punkte ab.
  2. Es seien verschiedene Punkte der Ebene, ein beliebiger Punkt auf der durch definierten Geraden und ein Punkt, der nicht auf dieser Geraden liegt. Dann ist der Vordersatz erfüllt, aber nicht der Nachsatz, und daher gilt die Implikation bei dieser Interpretation nicht.
  3. Aufgrund der Alleinführung im Antezedens gilt für beliebige Variablen die Ableitbarkeit

    Daher gilt mit Modus Ponens

    für beliebige Variablen. Insbesondere gilt

    Ebenso kann man auf

    schließen. Die Transitivität der Äquivalenz liefert

  4. Wenn und durch den gleichen Punkt interpretiert werden und durch einen Punkt und durch einen Punkt , derart, dass diese Punkte nicht auf einer Geraden liegen, so liegen dennoch und auf einer Geraden. Bei einer solchen Belegung sind und wahr, ohne dass alle Punkte auf einer Geraden liegen.
  5. Man nimmt . Die Variablen seien durch die Punkte belegt. Wenn diese Punkte auf einer gemeinsamen Geraden liegen, so liegen insbesondere je drei von ihnen auf einer (nämlich dieser) Geraden und daher gilt bei dieser Belegung. Zum Beweis der Umkehrung sei . Dies bedeutet, dass sowohl als auch als auch jeweils auf einer Geraden liegen. Wenn unter den Punkten nur zwei verschiedene Punkte vorkommen, so liegen alle Punkte auf einer Geraden. Wir können uns also auf den Fall beschränken, wo maximal zwei Punkte identisch sind. Wenn ist, so definiert dies eine eindeutige Gerade, und auf dieser Geraden müssen wegen der Gültigkeit von bzw. sowohl als auch liegen. In diesem Fall liegen alle Punkte auf einer Geraden. Sei nun . Wegen liegen auf einer Geraden.


 

Aufgabe (3 Punkte)

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

Lösung

Sortenprädikat/Mathematisches Beispiel/Erläutere/Aufgabe/Lösung

 

Aufgabe * (2 Punkte)

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

Lösung

Die ganzen Zahlen sind ein kommutativer Ring und insbesondere ein kommutativer Halbring. Sie bilden aber keinen Peano-Halbring, da das erste Axiom , also dass die keinen Vorgänger hat, in nicht gilt.


 

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.

Lösung

Registermaschine/Potenzen und Potenztest/Programm/Aufgabe/Lösung

 

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.

Lösung

Wenn ein Programm ist, das entscheidet, so kann man einfach ein aufzählendes Programm konstruieren. Man lässt der Reihe nach jede natürliche Zahl mittels auf ihre Zugehörigkeit zu überprüfen und druckt sie aus, falls sie dazu gehört (dazu muss man den Haltebefehl von zu einer Druckausgabe modifizieren). Entsprechend konstruiert man ein Aufzählungsprogramm für das Komplement.

Es seien nun als auch aufzählbar, und es seien und Programme, die dies leisten. Dann liefert die folgende Kombination der beiden Programme ein Entscheidungsverfahren: Man schreibt die Programme und hintereinander (wobei man natürlich die adressierten Register und Programmzeilen umnummerieren muss) und lässt sie abwechselnd bis zu einer Druckausgabe laufen. Sobald eine Druckausgabe eines Programmteils mit der zu überprüfenden Zahl übereinstimmt, weiß man, ob zu gehört oder nicht. Da entweder zu oder zum Komplement gehört, muss einer dieser Fälle eintreten.


 

Aufgabe * (6 Punkte)

Man gebe für die Abbildung

mit

einen Ausdruck an, der arithmetisch repräsentiert.

Lösung

Wir setzen

und müssen zeigen, dass genau dann gilt, wenn gilt. Diese Äquivalenz beweisen wir durch eine doppelte Fallunterscheidung.

1.1. ist eine Quadratzahl und ist die Quadratwurzel aus . Dann ist einerseits . Andererseits ist . Daher gilt auch bei dieser Belegung.

1.2. ist eine Quadratzahl und ist nicht die Quadratwurzel aus . Dann ist einerseits . Andererseits ist . Da eine Quadratzahl ist, gilt die Aussage in nicht. Daher gelten beide durch verbundenen Teilaussagen von nicht und somit gilt nicht.

2.1. ist keine Quadratzahl und ist . Dann ist einerseits . Andererseits gelten die Aussagen und und somit gilt in .

2.2. ist keine Quadratzahl und ist nicht . Dann ist einerseits . Andererseits gilt in die Aussage und die Aussage nicht. Somit gilt auch ihre -Verknüpfung nicht und daher .


 

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.

Lösung

Es sei und es sei vorausgesetzt, dass die Relation repräsentiert. Wir müssen zeigen, dass auch die Relation repräsentiert. Sei zunächst . Dann ist

wegen der Repräsentierbarkeit von durch . Nach Voraussetzung ist

Aus der Alleinführung im Sukzedens (die anwendbar ist, da in nur gebundene Variablen vorkommen) folgt

Das Einsetzungsaxiom sichert

was

bedeutet. Also gilt

und somit

Bei gilt

und

Mit dem gleichen Schluss wie oben ergibt sich

und somit