Kurs:Einführung in die mathematische Logik/20/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 2 2 3 6 3 0 2 3 0 2 0 0 0 0 4 33




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .
  2. Ein maximales Ideal in einem kommutativen Ring .
  3. Die Uminterpretation zu einer -Interpretation in einer Menge , wobei eine Variable und ein Element der Grundmenge ist.
  4. Ein Nichtstandardmodell zu einem fixierten -Modell .
  5. Eine arithmetisch repräsentierbare Relation .
  6. Die Gültigkeit eines modallogischen Ausdrucks .


Lösung

  1. Die Sprache der Aussagenlogik wird rekursiv durch folgende Regeln definiert.
    1. Jedes gehört zu .
    2. Wenn , so ist auch .
    3. Wenn , so sind auch .
  2. Das Ideal heißt maximal, wenn ist und wenn es zwischen und keine weiteren Ideale gibt.
  3. Unter der Uminterpretation versteht man diejenige Interpretation von in , die strukturgleich zu ist und für deren Variablenbelegung

    gilt.

  4. Man nennt eine weitere -Struktur , die zu elementar äquivalent, aber nicht zu -isomorph ist, ein Nichtstandardmodell von .
  5. Die Relation heißt arithmetisch repräsentierbar, wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die Äquivalenz genau dann, wenn gilt.
  6. Man sagt, dass ein modallogischer Ausdruck in einem modallogischen Modell gilt, wenn

    für alle gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. /Fakt/Name
  2. Der Satz über die Vorgängereigenschaft in einem Peano-Halbring.
  3. Der Satz über das Halteproblem.


Lösung

  1. /Fakt
  2. In einem Peano-Halbring gilt für jedes die Eigenschaft: Entweder ist oder es gibt ein mit .
  3. Die Menge

    ist nicht

    -entscheidbar.


Aufgabe (2 Punkte)

Betrachte die beiden Aussagen „Alkohol ist keine Lösung“ und „Kein Alkohol ist auch keine Lösung“. Formalisiere die beiden Aussagen. Man nehme an, dass beide Aussagen wahr sind. Mit welcher aussagenlogischen Regel kann man daraus auf eine Aussage schließen, in der Alkohol nicht vorkommt?


Lösung

Die erste Aussage kann man als

und die zweite Aussage als

formalisieren. Aus der Fallunterscheidungsregel ergibt sich die Gültikeit von

dass es also keine Lösung gibt.


Aufgabe (2 Punkte)

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

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


Lösung


Aufgabe (3 Punkte)

Skizziere ein Verfahren, wie man (bei abzählbar) eine Auflistung sämtlicher syntaktischer Tautologien aus erhalten kann.


Lösung Aussagenlogik/Ableitungskalkül/Skizziere vollständige Auflistung/Aufgabe/Lösung


Aufgabe (6 Punkte)

Es sei eine aussagenlogische Ausdrucksmenge und es sei mit . Zeige mit dem Lemma von Zorn, dass es eine maximal widerspruchsfreie Ausdrucksmenge mit gibt.


Lösung

Zunächst ist auch

da andernfalls

gelten würde, woraus man mit Hilfe von und der Fallunterscheidungsregel erhalten würde. Wir können also im Folgenden davon ausgehen, dass zu gehört.

Wir betrachten die Menge

mit der durch Inklusion gegebenen Ordnung. Wegen ist diese Menge nicht leer. Es sei eine nichtleere total geordnete Teilmenge. Die Vereinigung

besitzt ebenfalls die Eigenschaft, dass man aus ihr nicht ableiten kann. Eine solche Ableitung nimmt nämlich nur Bezug auf endlich viele Voraussetzungen, und wäre dann schon aus einem der ableitbar. Also besitzt die Kette in eine obere Schranke. Nach dem Lemma von Zorn gibt es also in maximale Elemente. Ein solches ist maximal widerspruchsfrei. Wenn man nämlich zu einem solchen maximalen einen neuen Ausdruck hinzunimmt, so gilt

Doch wegen ist widersprüchlich.


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

Es sei ein zweistelliges Funktionssymbol und sei der Ausdruck gleich . Wir setzen

Dann ist einerseits (wir schreiben für die Gleichheit von Ausdrücken)

was allgemeingültig ist, und andererseits

was nicht allgemeingültig ist (beispielsweise bei Interpretation in ). Somit ist die Implikation nicht allgemeingültig.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (2 Punkte)

Man bringe die Aussage

in disjunktive Normalform.


Lösung

Der Ausdruck

ist äquivalent zum Ausdruck

und der Ausdruck

ist äquivalent zu

Der Gesamtausdruck ist somit äquivalent zu

der disjunktive Normalform besizt.


Aufgabe (3 Punkte)

Es sei die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge und es sei eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation . Zeige, dass maximal widerspruchsfrei ist.


Lösung

Sei . Da der Ableitungskalkül korrekt ist, ist abgeschlossen unter Ableitungen. Aufgrund der rekursiv definierten Wahrheitsbelegung gilt für jedes entweder oder . Somit ist widerspruchsfrei. Sobald man zu einen Ausdruck hinzunimmt, hat man und daraus kann man einen Widerspruch ableiten. Die Menge ist also maximal widerspruchsfrei.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (2 Punkte)

Es sei eine Variable, ein Term und ein Ausdruck. Zeige


Lösung

Die Variable ist in nicht frei. Daher ist die Menge der relevanten zu substituierenden Variablen leer und somit auch die Menge der substituierenden Terme. Also ist und daher


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


Aufgabe (4 Punkte)

Formuliere den Vollständigkeitssatz der Modallogik und skizziere in Grundzügen, wie man ihn beweist.


Lösung Modallogik/Vollständigkeitssatz/Skizziere/Aufgabe/Lösung