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

Aus Wikiversity


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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Primzahl.
  2. Die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .
  3. Die Uminterpretation zu einer - Interpretation in einer Menge , wobei eine Variable und ein Element der Grundmenge ist.
  4. Der Rang eines prädikatenlogischen Ausdrucks .
  5. Eine -berechenbare Funktion
  6. Eine -Modallogik.


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

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


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

Folgende Aussagen seien bekannt.

  1. Der frühe Vogel fängt den Wurm.
  2. Doro wird nicht von Lilly gefangen.
  3. Lilly ist ein Vogel oder ein Igel.
  4. Für Igel ist 5 Uhr am Morgen spät.
  5. Doro ist ein Wurm.
  6. Für Vögel ist 5 Uhr am Morgen früh.
  7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

  1. Ist Lilly ein Vogel oder ein Igel?
  2. Ist sie ein frühes oder ein spätes Tier?
  3. Fängt der späte Igel den Wurm?


Aufgabe * (8 Punkte)

Es sei eine aussagenlogische Aussage und es seien die darin vorkommenden Aussagenvariablen. Es sei

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Zeige, dass dann

gilt.


Aufgabe * (2 Punkte)

Es sei eine Konstantenmenge, ein einstelliges Funktionssymbol und ein zweistelliges Funktionssymbol. Es sei die Interpretation mit als Grundmenge, bei der als Quadrieren, als Multiplikation und die Konstanten als und interpretiert wird. Ist der Ausdruck

unter dieser Interpretation gültig?


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

  1. Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
  2. Beschreibe die Bedingung (und zwar so, dass die Bedingung erkennbar ist) aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck (also mit dem Symbolalphabet und Variablen) in der einen freien Variablen .
  3. Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen .


Aufgabe * (3 Punkte)

Formuliere die Injektivität für eine Abbildung

prädikatenlogisch mit Hilfe der Verwendung von Sorten.


Aufgabe * (5 (3+2) Punkte)

Es sei ein Symbolalphabet und die zugehörige Sprache und die zugehörige Termmenge. Es sei eine Ausdrucksmenge.

  1. Zeige, dass durch

    eine Äquivalenzrelation auf definiert wird.

  2. Wenn man vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?


Aufgabe * (5 (1+1+1+1+1) Punkte)

In einer Wohngemeinschaft leben die Personen . Wir betrachten die folgenden Relationen:

  1. bedeutet, dass und manchmal miteinander Tennis spielen,
  2. bedeutet, dass und manchmal miteinander Skat spielen,
  3. bedeutet, dass und manchmal miteinander Doppelkopf spielen.

In der WG gilt

  1. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Spielrelationen.
  2. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Spielrelationen.
  3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .
  4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .
  5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .


Aufgabe (4 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Quadratzahlen ausdruckt.


Aufgabe (4 Punkte)

Es seien entscheidbare Mengen. Zeige, dass dann auch die Vereinigung , der Durchschnitt und auch das Komplement entscheidbar sind.


Aufgabe * (4 Punkte)

Zeige, dass die Abbildung

(wohldefiniert und) arithmetisch repräsentierbar ist.


Aufgabe * (4 Punkte)

Beweise das Unvollständigkeitslemma.


Aufgabe * (6 (1+1+4) Punkte)

Wir interpretieren den Satz von Sokrates, „Ich weiß, dass ich nichts weiß“, als modallogisches Axiomenschema

Zeige die folgenden Aussagen.

  1. Dieses Axiomenschema ist paradox.
  2. Dieses Axiomenschema ist innerhalb der - Modallogik äquivalent zu
  3. Dieses Axiomenschema ist innerhalb der - Modallogik äquivalent zu

    also zum Leerheitsaxiom.


Aufgabe * (5 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Transitivitätsaxiom genau dann gilt, wenn transitiv ist.