Kurs:Einführung in die mathematische Logik/11/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
Punkte 3 3 1 1 3 2 1 3 5 6 4 3 0 0 35




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 *****  (6). Nach Voraussetzung und Fakt *****  (5) ergibt sich daraus .


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 ***** ist

also

Daher folgt aus

mittels Modus Ponens direkt


Sei umgekehrt gegeben. Es sei ein beliebiger Ausdruck, in dem nicht vorkomme. Nach Axiom *****  (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)

Tred-G.svg

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


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung