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

Aus Wikiversity


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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Ableitbarkeit eines Aussage aus einer Aussagenmenge in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge .
  2. Eine Ordnungsrelation auf einer Menge .
  3. Die Erfüllbarkeit eines -Ausdruckes , wobei ein Symbolalphabet bezeichnet.
  4. Die elementare Äquivalenz für Elemente für eine -Struktur .
  5. Die aufzählbare Axiomatisierbarkeit einer Theorie zu einem Symbolalphabet .
  6. Die Gültigkeit eines modallogischen Ausdrucks in einem modallogischen Rahmen .


Lösung

  1. Man sagt, dass aus ableitbar ist, wenn es endlich viele Ausdrücke derart gibt, dass

    gilt.

  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. Man nennt erfüllbar, wenn es eine - Interpretation mit gibt.
  4. Zwei Elemente heißen elementar äquivalent, wenn für jeden Ausdruck in der einen freien Variablen und jede Variablenbelegung auf die Beziehung

    gilt.

  5. Eine Theorie heißt aufzählbar axiomatisierbar, wenn es eine - aufzählbare Satzmenge mit gibt.
  6. Die Gültigkeit in einem modallogischen Rahmen bedeutet, dass für jede Wahrheitsbelegung

    gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Substitutionslemma.
  2. Der Vollständigkeitssatz der Aussagenlogik.
  3. Der zweite Gödelsche Unvollständigkeitssatz.


Lösung

  1. Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben und es seien paarweise verschiedene Variablen und fixierte -Terme. Es sei eine -Interpretation gegeben. Dann gelten folgende Aussagen.
    1. Für jeden -Term gilt
    2. Für jeden -Ausdruck gilt
  2. Es sei eine Menge an Aussagenvariablen und eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei . Dann ist
  3. Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse. Dann ist die Widerspruchsfreiheit nicht aus ableitbar, d.h. es ist


Aufgabe (1 Punkt)

Formuliere die Kontraposition zu folgender Aussage von Professor Knopfloch: „Wenn Sie mein Schreiben vollständig gelesen und verstanden haben, dann antworten Sie mit Ihrer Uni-email“.


Lösung

Wenn Sie nicht mit Ihrer Uni-email antworten, dann haben Sie mein Schreiben nicht vollständig gelesen oder nicht verstanden.


Aufgabe (1 Punkt)

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

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


Lösung

.


Aufgabe (3 Punkte)

Die Klasse 8c hat an jedem Wochentag eine Stunde mathematische Logik. Der Lehrer sagt am Freitag: „nächste Woche werden wir eine Klassenarbeit schreiben, und das wird eine Überraschung sein“. Begründe, dass der Lehrer lügt.


Lösung Woche/Klassenarbeit/Überraschung/Aufgabe/Lösung


Aufgabe (2 Punkte)

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


Lösung

Es gilt

nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (6). Nach Voraussetzung und Lemma 4.2 (Einführung in die mathematische Logik (Osnabrück 2021))  (5) ergibt sich daraus .


Aufgabe (3 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge und es seien . Zeige, dass

zu

äquivalent ist.


Lösung

Die Ableitungsbeziehung

bedeutet, dass es Ausdrücke mit

gibt. Aufgrund der aussagenlogischen Tautologie

ist dies äquivalent zu

Dies bedeutet gerade


Aufgabe (7 Punkte)

Beweise den Satz von Hamel mit dem Lemma von Zorn.


Lösung

Es sei ein Vektorraum über einem Körper . Es sei

Die leere Menge gehört zu , also ist nicht leer. Es sei eine total geordnete Teilmenge. Wir behaupten, dass

ebenfalls linear unabhängig ist und daher eine obere Schranke von in bildet. Andernfalls gäbe es nämlich eine endliche Teilmenge , deren Elemente linear abhängig sind, und es gäbe auch ein , das umfasst und daher selbst linear abhängig wäre. Nach dem Lemma von Zorn besitzt also maximale Elemente, d.h. es gibt eine Teilmenge , die linear unabhängig ist und derart, dass es keine echt größere linear unabhängige Teilmenge von gibt. Wir behaupten, dass auch ein Erzeugendensystem von ist. Es sei dazu . Bei sind wir fertig. Bei ist linear abhängig, d.h. es gibt eine Linearkombination

mit Elementen und Koeffizienten , die nicht alle sind. Dabei kann nicht sein, da sonst eine lineare Abhängigkeit zwischen Elementen aus vorliegen würde. Also kann man als Linearkombination der ausdrücken.


Aufgabe (1 Punkt)

Wir betrachten den Satz „Kein Mensch ist illegal“. Negiere diesen Satz durch eine Existenzaussage.


Lösung

Es gibt einen Menschen, der nicht legal ist.


Aufgabe (3 Punkte)

Erläutere Vor- und Nachteile des axiomatischen Aufbaus der Mathematik.


Lösung Axiomatischer Aufbau/Vor- und Nachteile/Aufgabe/Lösung


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.


Lösung

  1. Wir beweisen die Aussage durch Induktion über den Aufbau der Terme. Für Variablen ist bei direkt und ferner . Konstanten bleiben bei jeder Substitution unverändert. Für ein -stelliges Funktionssymbol und Terme ist

    nach Induktionsvoraussetzung.

  2. Wir beweisen die Aussage durch Induktion über den Aufbau der Sprache für alle Variablen gleichzeitig. Wenn eine Identität von Termen oder eine Relationsaussage ist, so ergibt sich die Behauptung unmittelbar aus Teil (1). Der Induktionsschritt für die aussagenlogischen Junktoren ergibt sich unmittelbar aus der Definition der Substitution. Bei mit kommt nicht im substituierenden Term vor, und daher ist und

    nach Induktionsvoraussetzung. Bei ist nicht frei in und somit ist die relevante Termmenge leer und , also

    nach Induktionsvoraussetzung.


Aufgabe (6 Punkte)

Es sei ein Symbolalphabet erster Stufe, ein - Ausdruck und eine Variable. Zeige, dass genau dann gilt, wenn gilt.


Lösung

Nach der Allquantorversion von Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) ist

also

Daher folgt aus

mittels Modus ponens direkt


Es sei umgekehrt gegeben. Es sei ein beliebiger Ausdruck, in dem nicht vorkomme. Nach Axiom 3.8 (Einführung in die mathematische Logik (Osnabrück 2021))   (1) und Modus ponens ergibt sich

und

Auf diese beiden abgeleiteten Ausdrücke wird nun die Allquantorversion der Existenzeinführung im Antezedens (also die Alleinführung im Sukzedens) angewendet. Dies ist möglich, da in überhaupt nicht und in nicht frei vorkommt. Man erhält

und

Daraus ergibt sich mit der Fallunterscheidungsregel



Aufgabe (4 (2+2) Punkte)

Es sei ein kommutativer Halbring und . Es sei

  1. Zeige, dass die folgenden drei Eigenschaften erfüllt.
    1. .
    2. Wenn sind, so ist auch .
    3. Wenn und ist, so ist auch .
  2. erfülle nun die Abziehregel. Zeige, dass aus mit auch folgt.


Lösung

Es sei ein kommutativer Halbring und . Es sei

    1. Die Zugehörigkeit ergibt sich aus .
    2. Sei und . Dann ist durch Addition der beiden Gleichungen direkt
    3. Sei . Durch Multiplikation mit ergibt sich direkt
  1. Sei und und . Durch Addition der beiden Gleichungen über Kreuz erhält man

    Aufgrund der Abziehregel gilt

    was die Zugehörigkeit bedeutet.


Aufgabe (3 Punkte)

Charakterisiere den Punkt im skizzierten Graphen mit einem Ausdruck in einer freien Variablen über dem Symbolalphabet, das neben Variablen aus einem einzigen zweistelligen Relationssymbol besteht, das im angegebenen Modell durch einen Pfeil wiedergegeben wird.


Lösung

Den Ausdruck

erfüllen genau die beiden Punkte und , da diese für drei Pfeile die Endpunkte sind. Ein Unterschied zwischen und ist, dass bei nur Pfeile von Punkten ankommen, an denen jeweils höchstens ein Pfeil ankommt, während in ein Pfeil, nämlich der von ankommt, auf dem mehr als ein Pfeil ankommt. Daher ist