Kurs:Einführung in die mathematische Logik/7/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
Punkte 3 3 1 7 7 2 4 0 0 5 3 0 0 4 0 4 43



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. Ein gerichteter Graph.


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)

Negiere die Aussage „Martina findet alle Jungs im Kurs außer Markus zuckersüß“ durch eine Aussage, in der eine Existenzaussage und eine Oder-Verknüpfung vorkommen.


Aufgabe * (7 Punkte)

Beweise den Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen im abzählbaren Fall.


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. Die Tiere gehören einer eindeutigen Generation an.

  1. Die -te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch 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 verschiedene Aussagenvariablen. Begründe die (Un)Richtigkeit der beiden folgenden Aussagen.

  1. genau dann, wenn .
  2. .


Aufgabe * (4 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige, dass für jeden -Satz die Gleichheit

gilt.


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)


Aufgabe * (5 Punkte)

Beweise den Satz über die Division mit Rest in einem Peano-Halbring.


Aufgabe * (3 Punkte)

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


Aufgabe (0 Punkte)


Aufgabe (0 Punkte)


Aufgabe * (4 Punkte)

Es sei eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von in die Potenzmenge geben kann.


Aufgabe (0 Punkte)


Aufgabe * (4 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Möglichkeitsaxiom genau dann gilt, wenn in jeder Punkt einen Nachfolger besitzt.