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



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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein Primzahlzwilling.
  2. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
  3. Eine maximal widerspruchsfreie Teilmenge zu einer Menge an Aussagenvariablen.
  4. Die Interpretation der Terme zu einem Symbolalphabet in einer gegebenen - Interpretation auf einer Grundmenge .
  5. Ein allgemeingültiger prädikatenlogischer Ausdruck .
  6. Die Addition in einem Dedekind-Peano-Modell .


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Lemma von Zorn.
  2. Der Vollständigkeitssatz der Aussagenlogik.
  3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .


Aufgabe * (1 Punkt)

Gehört das leere Wort zur Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ?


Aufgabe (2 Punkte)

Zeichne einen Abstammungsbaum für die Aussage


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)

Zeige, dass der aussagenlogische Ausdruck

allgemeingültig ist


Aufgabe * (2 Punkte)

Es seien verschiedene Aussagenvariablen. Begründe die (Un)Richtigkeit der beiden folgenden Aussagen.

  1. genau dann, wenn .
  2. .


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 * (7 (1+1+2+3) Punkte)

Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an.

  1. Die -te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
  2. Die -te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
  3. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt.
  4. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?


Aufgabe * (2 Punkte)

Es seien Variablen und ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. ,
  8. ,
  9. ,
  10. ,
  11. ,
  12. .


Aufgabe * (1 Punkt)

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.


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 * (7 (3+4) Punkte)

Es sei eine Variablenmenge, eine Konstante und zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck , der durch

gegeben ist.

  1. Zeige, dass bei Interpretation in einem Körper wahr wird, wenn man als und als Subtraktion, Addition und Multiplikation interpretiert.
  2. Welcher wichtige mathematische Satz verbirgt sich dahinter?


Aufgabe * (3 Punkte)

Formuliere die Injektivität für eine Abbildung

prädikatenlogisch mit Hilfe der Verwendung von Sorten.


Aufgabe * (8 (3+5) Punkte)

Es sei ein Symbolalphabet erster Stufe und eine Teilmenge. Es sei ein - Term und ein - Ausdruck. Es seien zwei - Interpretationen und in einer gemeinsamen Grundmenge gegeben, die auf identisch seien. Beweise die folgenden Aussagen.

  1. Es ist .
  2. Es ist genau dann, wenn (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus und auf den in frei vorkommenden Variablen identisch sind).


Aufgabe * (3 Punkte)

Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung die Gleichheit folgt (dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden).


Aufgabe * (2 Punkte)

Formalisiere in der arithmetischen Sprache die (wahre) Aussage, dass es unendlich viele Primzahlen gibt.


Aufgabe * (6 (3+3) Punkte)

Es sei ein Modell für die Peano-Axiome für den Nachfolger.

  1. Zeige, dass fixpunktfrei ist, d.h. dass

    für alle .

  2. Zeige, dass periodenfrei ist. D.h. für jedes ist

    wobei

    die -fache Hintereinanderschaltung von bedeutet.