Kurs:Einführung in die mathematische Logik/2/Test/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 3 4 3 3 3 1 4 4 12 5 3 4 12 64



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Mersennesche Primzahl.
  2. Eine widersprüchliche Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .
  3. Die Produktmenge aus zwei Mengen und .
  4. Die Bestandteile einer Grundtermmenge.
  5. Ein allgemeingültiger prädikatenlogischer Ausdruck .
  6. Die Ableitbarkeit eines Ausdrucks im prädikatenlogischen Kalkül.


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Lemma von Zorn.
  2. Der Satz über die Division mit Rest in einem Peano-Halbring.
  3. Der Endlichkeitssatz für die Prädikatenlogik.


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

Bei einem Zwei-Personen-Regel-Spiel (wie Schach) spielen zwei Personen ( und ) nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für ist, da ist am Zug und kann schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge aller Stellungen eine Gewinnstellung für (mit am Zug) ist.


Aufgabe (3 Punkte)

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.


Aufgabe * (3 Punkte)

Beweise durch Induktion über den rekursiven Aufbau der Sprache , dass in jeder Aussage die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.


Aufgabe * (1 Punkt)

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

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


Aufgabe * (4 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Begründe die Kettenschlussregel für die Ableitungsbeziehung: Wenn und , dann auch .


Aufgabe * (4 (2+2) Punkte)

Es sei eine unendliche Menge und die Menge, die aus sämtlichen endlichen Teilmengen von besteht.

  1. Ist induktiv geordnet?
  2. Besitzt maximale Elemente?


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

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben.

  1. Zeige, dass die Substitution für die Terme die Identität ist.
  2. Zeige, dass die Substitution für die Ausdrücke die Identität ist.


Aufgabe * (3 Punkte)

Zeige


Aufgabe * (4 Punkte)

Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.


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

Es sei

  1. Zeige, dass ein kommutativer Halbring ist.
  2. Zeige, dass in die Relationen

    und

    zueinander äquivalent sind.

  3. Zeige, dass nicht irreduzibel in ist.
  4. Zeige, dass es in keine irreduziblen Elemente gibt.
  5. Es sei die Aussage

    Zeige, dass in die Aussage

    wahr ist.

  6. Zeige, dass kein Peano-Halbring ist.