Kurs:Einführung in die mathematische Logik/13/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 15 16 17
Punkte 3 3 3 3 2 4 3 0 2 0 0 0 11 0 0 0 0 34




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
  2. Eine induktiv geordnete Menge .
  3. Das Alphabet einer Sprache erster Stufe.
  4. Die Eigenschaft einer Ausdrucksmenge , Beispiele zu enthalten.
  5. Die Addition in einem Dedekind-Peano-Modell .
  6. Der modallogische Folgerungsbegriff.


Lösung

  1. Unter einer Wahrheitsbelegung versteht man eine Abbildung
  2. Eine geordnete Menge heißt induktiv geordnet, wenn jede total geordnete Teilmenge eine obere Schranke in besitzt.
  3. Das Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.
    1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
    2. Zu jeder natürlichen Zahl eine Menge von -stelligen Relationssymbolen.
    3. Die aussagenlogischen Junktoren
    4. Das Gleichheitszeichen .
    5. Die Quantoren und .
    6. Klammern, also und .
  4. Man sagt, dass Beispiele enthält, wenn es für jeden Ausdruck der Form aus einen -Term derart gibt, dass

    zu gehört.

  5. Die Addition wird über die Addition mit festem definiert, wobei die eindeutig bestimmte Abbildung

    ist, für die

    gilt.

  6. Es sei eine Menge von modallogischen Ausdrücken und ein modallogischer Ausdruck. Man sagt, dass aus folgt, wenn für jedes modallogische Modell mit

    auch

    gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. /Fakt/Name
  2. Das Isomorphielemma.
  3. /Fakt/Name


Lösung

  1. /Fakt
  2. Es seien und isomorphe -Strukturen über einem Symbolalphabet . Dann sind und elementar äquivalent.
  3. /Fakt


Aufgabe (3 Punkte)

In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit (vordere Tafel), (mittlere Tafel) und (hintere Tafel) bezeichnet. Aufgrund der Höhe des Gestells sind nur (maximal) zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge (alle Möglichkeiten!) muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll.


Lösung

Die Tafeln und sind nicht gleichzeitig sichtbar, da (mindestens) eine davon durch verdeckt wird. Dagegen sind sowohl und ( wird hinter geschoben) als auch und gleichzeitig einsehbar. Eine Beschreibungsreihenfolge erfüllt also genau dann die angegebene Bedingung, wenn und nicht direkt hintereinander beschrieben werden. Dies wird genau dann erreicht, wenn als zweite Tafel beschrieben wird. Erlaubt sind also die beiden Reihenfolgen und .


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.


Lösung

Wir definieren

und rekursiv

Eine Gewinnstellung ist dann


Aufgabe (2 Punkte)

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

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


Lösung


Aufgabe (4 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Zeige


Lösung

Die Inklusion

ist wegen klar. Sei also . Dies bedeutet, dass es Ausdrücke mit

gibt. Für die einzelnen gibt es mit

für jedes . Daraus ergibt sich mit Hilfe (der Regelversion) von Fakt *****  (2)

Mit der Kettenschlussregel ergibt sich daraus

was bedeutet.


Aufgabe (3 Punkte)

Es seien Variablen, Terme und ein Ausdruck in einer prädikatenlogischen Sprache. Zeige, dass

im Allgemeinen nicht allgemeingültig ist.


Lösung

Für betrachten wir den Ausdruck und wir setzen und . Dann ist einerseits (wir schreiben für die Gleichheit von Ausdrücken)

was allgemeingültig ist, und andererseits

was nicht allgemeingültig ist. Somit ist

nicht allgemeingültig.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (2 (0.5+0.5+0.5+0.5) Punkte)

Wir zählen

  1. Was ist die Mama der Urururoma?
  2. Was ist die Uroma der Uroma?
  3. Was ist die Oma der Oma der Oma?
  4. Was ist das ich der Uroma der Ururoma?


Lösung

  1. Ururururoma.
  2. Ururururoma.
  3. Ururururoma.
  4. Urururururoma.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


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

Wir betrachten die Identität

und den Ausdruck , den wir mit bezeichnen. Es sei die Ausdrucksmenge, die die Kommutativität und die Assoziativität der Addition besagt sowie, dass das neutrale Element der Addition ist.

  1. Zeige, dass der Graph der Identität durch schwach repräsentierbar in ist.
  2. Zeige, dass der Graph der Identität nicht repräsentierbar in ist.
  3. Zeige, dass der Graph der Identität repräsentierbar in der Peano-Arithmetik ist.
  4. Ist die Identität als Abbildung repräsentierbar in der Peano-Arithmetik?
  5. Gilt

    für jedes (dabei werde durch eine -fache Summe der mit sich in beliebiger Klammerung wiedergegeben)?


Lösung

  1. Wenn eine Gleichheit

    von natürlichen Zahlen vorliegt, so wird diese eine Zahl durch den einen Term in dargestellt. Wegen Axiom ***** gilt

    Wenn hingegen und verschiedene natürliche Zahlen sind, so ist die Gleichheit nicht aus ableitbar, da andernfalls wegen die Gleichheit auch in gelten würde.

  2. Seien

    verschiedene natürliche Zahlen. Wir behaupten

    Wäre das nämlich doch ableitbar, so müsste diese Ungleichheit in jedem Modell von gelten. Die Gültigkeit von in einem Modell bedeutet aber lediglich, dass ein kommutatives Monoid vorliegt. Da es auch das triviale Monoid gibt, in dem alle Elemente gleich sind, erhalten wir einen Widerspruch.

  3. Bei gleichen Zahlen folgt die Ableitbarkeit nach Teil (1) sogar aus , also erst recht aus der Peano-Arithmetik. Seien also

    verschiedene natürliche Zahlen. Es ist

    zu zeigen. Wegen der (ableitbaren) Symmetrie des Gleichheitszeichens können wir

    annehmen. Es sei

    mit . Nach Axiom *****  (1) ist

    Die Kontraposition zu Axiom *****  (2) liefert der Reihe nach

    bis man schließlich bei

    anlangt.

  4. Die folgt aus Teil (5).
  5. Das gilt, es ist

    für jedes zu zeigen. Dies ergibt sich aber einfach aus der (ableitbaren) Symmetrie und der Transitivität des Gleichheitszeichens.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung