Kurs:Einführung in die mathematische Logik/15/Klausur mit Lösungen

Aus Wikiversity


Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Punkte 3 3 2 2 3 5 4 3 0 0 0 2 0 0 0 4 0 31




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein Wort über einem Alphabet .
  2. Eine Ordnungsrelation auf einer Menge .
  3. Die (rekursiv definierte) Gültigkeit eines prädikatenlogischen -Ausdruckes bei einer - Interpretation auf einer Menge .
  4. Ein -Homomorphismus

    zwischen zwei - Strukturen und .

  5. Die Multiplikation mit in einem Dedekind-Peano-Modell .
  6. Die Ableitbarkeit eines modallogischen Ausdrucks im -System.


Lösung

  1. Ein Wort über dem Alphabet ist eine beliebige endliche Zeichenkette, wobei sämtliche Einzelzeichen zu gehören.
  2. Die Relation heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.
    1. Es ist für alle .
    2. Aus und folgt stets .
    3. Aus und folgt .
  3. Die - Ausdrücke werden folgendermaßen als gültig charakterisiert (dabei seien Terme und Ausdrücke).
    1. , wenn .
    2. , wenn .
    3. , wenn nicht gilt.
    4. , wenn und gilt.
    5. , wenn die Gültigkeit die Gültigkeit impliziert.
    6. , wenn es ein gibt mit .
    7. , wenn für alle die Beziehung gilt.
  4. Die Abbildung

    heißt -Homomorphismus, wenn folgende Eigenschaften gelten.

    1. Für jede Konstante ist
    2. Für jedes -stellige Funktionssymbol ist

      für alle .

    3. Für jedes -stellige Relationsymbol impliziert die Gültigkeit von

      die Gültigkeit von

  5. Die Multiplikation mit ist diejenige aufgrund von Satz 12.2 (Einführung in die mathematische Logik (Osnabrück 2021)) eindeutig bestimmte Abbildung

    für die

    gilt.

  6. Man sagt, dass ein modallogischer Ausdruck aus dem - System ableitbar ist, wenn sich aus aussagenlogischen Tautologien und aus Instanzen des - Axioms mit Hilfe des Modus ponens oder der Nezessisierungsregel ergibt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Wiles (Großer Fermat).
  2. Der Vollständigkeitssatz für Tautologien (Prädikatenlogik).
  3. Der erste Gödelsche Unvollständigkeitssatz.


Lösung

  1. Die diophantische Gleichung

    besitzt für kein

    eine ganzzahlige nichttriviale Lösung.
  2. Es sei ein Symbolalphabet und ein -Ausdruck. Dann ist genau dann eine ableitbare Tautologie, wenn allgemeingültig ist.
  3. Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube. Dann ist unvollständig.


Aufgabe (2 Punkte)

Wenn Karl an Susanne denkt, bekommt er feuchte Hände, einen Kloß im Hals und einen roten Kopf. Einen roten Kopf bekommt er genau dann, wenn er an Susanne denkt oder wenn er das leere Tor nicht trifft. Wenn Karl das leere Tor trifft, bekommt er feuchte Hände. Karl bekommt den Ball vor dem leeren Tor. Kurz darauf bekommt er feuchte Hände, einen roten Kopf, aber keinen Kloß im Hals. Hat er an Susanne gedacht? Hat er das leere Tor getroffen?


Lösung

Karl hat nicht an Susanne gedacht, da er sonst einen Kloß im Hals bekommen hätte, was er nicht hat. Andererseits bekommt er einen roten Kopf, was bedeutet, dass er das leere Tor nicht getroffen hat oder an Susanne gedacht hat. Da letzteres nicht der Fall ist, hat er das leere Tor nicht getroffen.


Aufgabe (2 Punkte)

Erläutere das Beweisprinzip der vollständigen Induktion.


Lösung

Mit dem Beweisprinzip der vollständigen Induktion werden Aussagen bewiesen, die von den natürlichen Zahlen abhängen. Man beweist zuerst die Aussage . Ferner zeigt man, dass man für alle aus der Gültigkeit von auf die Gültigkeit von schließen kann. Daraus folgt die Gültigkeit von für alle .


Aufgabe (3 Punkte)

Es sei ein Alphabet mit Symbolen. Wie viele Wörter über der Länge gibt es, wenn man nicht zwischen den Leserichtungen unterscheiden kann?


Lösung

Es gibt Wörter der Länge über einem Alphabet mit Symbolen. Bei einem solchen Wort kommt es auf die Leserichtung genau dann nicht an, wenn der erste mit dem fünften und der zweite mit dem vierten Symbol übereinstimmt. Dafür gibt es Möglichkeiten. Somit gibt es

Wörter, bei denen es auf die Leserichtung ankommt. Diese sind mit ihrer umgekehrten Reihenfolge zu identifizieren, wenn man die Leserichtungen nicht unterscheiden kann. Somit gibt es

Worttypen, wenn man die Leserichtung nicht unterscheiden kann.


Aufgabe (5 Punkte)

Es sei . Man gebe ein Beispiel für eine aussagenlogische widersprüchliche Ausdrucksmenge

derart, dass jede echte Teilmenge davon widerspruchsfrei ist.


Lösung

Bei kann man für jede widersprüchliche Aussage, beispielsweise nehmen. Es sei also . Es seien (verschiedene) Aussagenvariablen. Wir setzen

für und

Die Menge ist widersprüchlich, da man aus durch mehrfache Anwendung der Kettenschlussregel und des Modus ponens

erhält, was ein Widerspruch zu ist. Es sei nun

Wir müssen zeigen, dass widerspruchsfrei ist, wofür es genügt, eine erfüllende Wahrheitsbelegung anzugeben. Es sei fixiert. Dann erfüllt die Wahrheitsbelegung, bei der jede Variable mit als wahr und jede Variable mit als falsch belegt wird, die Menge , da für die mit Vorder-und Nachsatz wahr belegt sind und da für die mit der Vordersatz falsch belegt ist.


Aufgabe (4 Punkte)

Es sei eine Menge an Aussagenvariablen und eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Zeige, dass für jedes entweder oder gilt.


Lösung

Wegen der Widerspruchsfreiheit können nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so ist entweder oder widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck sowohl

als auch

gelten. Dies bedeutet nach Aufgabe 4.9 (Einführung in die mathematische Logik (Osnabrück 2021))

und

woraus aufgrund der Fallunterscheidungsregel

folgt. Dies bedeutet aber, dass widersprüchlich ist.


Aufgabe (3 Punkte)

Man erläutere durch Beispiele, dass der Aufbau der Prädikatenlogik nicht immer der mathematischen Intuition entspricht.


Lösung Prädikatenlogik/Intuitiv oder nicht/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 (2 (1+1) Punkte)

Wir betrachten das Symbolalphabet , das neben Variablen aus einem einzigen zweistelligen Relationssymbol besteht, wobei in der abgebildeten Punktemenge das Relationssymbol als „(echt) rechts von“ interpretiert wird. Für zwei Punkte bedeutet also , dass sich rechts von befindet.

  1. Welche(r) Punkt(e) erfüllt(en)
  2. Charakterisiere den Punkt mit einem - Ausdruck in der einen freien Variablen .


Lösung

  1. Die Aussage trifft für genau dann zu, wenn es rechts von genau einen Punkt gibt. Dies gilt nur für .
  2. Der Punkt besitzt genau drei Punkte rechts von ihm. Also ist

    ein charakterisierender Ausdruck.


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)

Zeige, dass ein gerichteter Graph genau dann symmetrisch ist, wenn für jede Teilmenge die Beziehung

gilt.


Lösung

Wir zeigen, dass die Negationen der beiden Eigenschaften zueinander äquivalent sind.

Es sei zuerst die Relation nicht symmetrisch. Dann gibt es mit , aber gilt nicht. Dann ist kein Vorgänger von und daher ist . Es ist somit und also . Daher gilt die Vorgängereigenschaft für

nicht.

Es sei nun die Vorgängereigenschaft nicht erfüllt, es gebe also eine Teilmenge mit

Dann gibt es ein mit . Dies bedeutet, dass es ein mit gibt. Wegen ist insbesondere nicht , also ist die Relation nicht symmetrisch.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung