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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine widersprüchliche Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .
  2. Die Produktmenge aus zwei Mengen und .
  3. Die Ableitbarkeit eines Ausdrucks im prädikatenlogischen Kalkül.
  4. Die Repräsentierbarkeit einer Funktion

    in einer Menge von arithmetischen Ausdrücken.

  5. Das modallogische Möglichkeitsaxiom.
  6. Die Nachfolgermenge in einem gerichteten Graphen.


Lösung

  1. Die Ausdrucksmenge heißt widersprüchlich, wenn es einen Ausdruck mit und gibt.
  2. Man nennt die Menge

    die Produktmenge der Mengen und .

  3. Der Ausdruck heißt ableitbar, wenn er sich aus den Grundtautologien, also
      • den aussagenlogischen syntaktischen Tautologien,
      • den Gleichheitsaxiomen,
      • der Existenzeinführung im Sukzedens,

    durch sukzessive Anwendung der Ableitungsregeln Modus Ponens und der Existenzeinführung im Antezedens erhalten lässt.

  4. Die Funktion heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die folgenden Eigenschaften
    1. Wenn , so ist ,
    2. Wenn , so ist ,
    3. ,

    gelten.

  5. Das modallogische Axiomenschema

    nennt man Möglichkeitsaxiom.

  6. Zu einer Teilmenge in einem gerichteten Graphen nennt man

    die Nachfolgermenge zu .


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

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


Lösung

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


Aufgabe (1 Punkt)

In einer psychologischen Längsschnittstudie wird die Entwicklung von Einstellungen und Verhaltensweisen von Personen untersucht. Ein Fallbeispiel: Im Alter von Jahren geht Linda regelmäßig auf Demonstrationen, sie hilft im Eine-Welt-Laden mit, braut ökologisches Bier, kocht Bio-Gemüse und studiert manchmal Soziologie.

Welcher der folgenden Befunde ist nach 10 Jahren am unwahrscheinlichsten?

  1. Linda arbeitet für eine Versicherungsagentur.
  2. Linda engagiert sich bei Attac und arbeitet für eine Versicherungsagentur.
  3. Linda engagiert sich bei Attac.


Lösung

(2) ist am unwahrscheinlichsten. Dass zwei Ereignisse gleichzeitig eintreffen ist stets unwahrscheinlicher als die beiden einzelnen Ereignisse.


Aufgabe (3 Punkte)

Erläutere das Prinzip Beweis durch Widerspruch für eine Aussage der Form „Aus folgt “.


Lösung

Man möchte zeigen, dass aus einer Aussage eine weitere Aussage folgt. Beim Beweis durch Widerspruch nimmt man an, dass gleichzeitig und nicht gelten. Unter diesen Voraussetzungen zeigt man, dass sich ein Widerspruch ergibt. Dies bedeutet, dass und nicht nicht gleichzeitig gelten können, was eben die Implikation bedeutet.


Aufgabe (3 Punkte)

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge und es sei . Es gelte

Zeige, dass dann

widerspruchsfrei ist.


Lösung

Nehmen wir an, dass widersprüchlich ist. Dann ist , da aus einer widersprüchlichen Menge alles ableitbar ist. Nach Aufgabe ***** ist dann . Wegen der Tautologie folgt mit der Fallunterscheidungsregel .


Aufgabe (2 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben, und eine Interpretation mit . Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit unter einer Substitution folgt.


Lösung

Die Sprache enthalte Konstanten und es sei eine Interpretation mit gegeben. Die Variable sei bei der Interpretation durch belegt. Dann gilt . Die Substitution führt den Ausdruck in über, und dieser gilt nicht unter der Interpretation.


Aufgabe (4 Punkte)

Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen

eindeutig bestimmt ist.


Lösung

Die Addition erfüllt nach Fakt *****  (1, 2) diese Eigenschaften.

Es seien zwei Verknüpfungen und auf gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit

für alle beweisen. Dies machen wir durch Induktion über (für beliebige ). Bei

ist wegen

die Aussage richtig. Sei die Aussage nun für ein bestimmtes schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung


Aufgabe (4 (1+1+1+1) Punkte)

Es sei eine nichtleere geordnete Menge. Wir betrachten die Relation auf , die durch , falls und gilt, definiert ist.

  1. Ist transitiv?
  2. Ist reflexiv?
  3. Charakterisiere, wann symmetrisch ist.
  4. Ist antisymmetrisch?


Lösung

  1. Sei und . Das bedeutet und und somit ist wegen der Transitivität von auch . Wäre , so wäre wegen der Antisymmetrie von auch , was den Voraussetzungen widerspricht.
  2. Die Relation ist nicht reflexiv, da die Verschiedenheit von und beinhaltet.
  3. Die Relation ist nicht symmetrisch, außer wenn die Identität ist. In diesem Fall ist nämlich die leere Relation, und diese ist symmetrisch. Wenn es hingegen ein Paar mit gibt, so ist , aber nicht umgekehrt.
  4. Die Relation ist antisymmetrisch. Sei und . Dann ist insbesondere und und die Antisymmetrie der Ordnungsrelation impliziert . Doch dies ist ein Widerspruch zur Voraussetzung. D.h. die Voraussetzung in der Eigenschaft Antisymmetrie kann gar nicht erfüllt sein und daher ist die Antisymmetrie erfüllt.


Aufgabe (8 Punkte)

Beweise den Satz von Henkin.


Lösung

Es sei das konstruierte Modell zu und die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

für alle Ausdrücke , durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von gleich , also atomar. D.h. ist entweder von der Form oder . Im ersten Fall ist äquivalent zu bzw. in . Dies ist nach Fakt ***** äquivalent zu und das bedeutet .

Im zweiten Fall ist - nach Konstruktion von und - äquivalent zu , und dies ist äquivalent zu .

Sei nun die Aussage für alle Ausdrücke vom Rang bewiesen und sei ein Ausdruck vom Rang . Wir betrachten die mögliche Struktur von gemäß Definition *****. Bei

ergibt sich die Äquivalenz aus der Induktionsvoraussetzung ( hat kleineren Rang als ) und Fakt *****  (1). Bei

besitzen die beiden Bestandteile kleineren Rang als . Die Zugehörigkeit ist nach Fakt *****  (3) äquivalent zur gemeinsamen Zugehörigkeit . Nach Induktionsvoraussetzung bedeutet dies und . Dies bedeutet wiederum aufgrund der Modellbeziehung. Bei

besitzt wieder einen kleineren Rang. Die Zugehörigkeit ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom ***** äquivalent zur Existenz eines Terms und der Zugehörigkeit . Die Substitution von nach verändert nach Aufgabe ***** nicht den Rang. Wir können also auf die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu . Nach dem Substitutionslemma ist dies äquivalent zu bzw. wegen Fakt *****. Dies ist äquivalent zu aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.


Aufgabe (2 Punkte)

Zeige, dass mit

auch

gilt.


Lösung

Aus der ableitbaren Implikation

ergibt sich mittels der Alleinführung im Antezedens

und dem Kettenschluss

und daraus mit der Alleinführung im Sukzedens, die anwendbar ist, da vorne und in gebunden ist,


Aufgabe (2 Punkte)

Zeige


Lösung

Es ist

aufgrund einer aussagenlogischen Tautologie. Nach Aufgabe ***** ergibt sich

und ebenso

Dies zusammengenommen ergibt


Aufgabe (4 Punkte)

Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.


Lösung

Aufgrund von Fakt *****, angewendet auf und die Nachfolgerabbildung auf , gibt es genau eine Abbildung

mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung

mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung

Diese erfüllt ebenfalls diese Eigenschaften. Da aber die Identität auf auch diese Eigenschaften erfüllt, folgt aus der Eindeutigkeitsaussage aus Fakt *****, dass ist. Ebenso ist und somit sind und invers zueinander.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (6 (4+2) Punkte)

Es sei

das Symbolalphabet für einen angeordneten Körper und es sei die -Struktur mit der Standardinterpretation.

  1. Zeige, dass die Äquivalenzklassen zur elementaren Äquivalenz einelementig sind.
  2. Zeige, dass es für die Elemente im Allgemeinen keinen charakterisierenden Ausdruck gibt.


Lösung

  1. Es seien verschiedene reelle Zahlen. Für müssen zeigen, dass es einen -Ausdruck in einer freien Variablen gibt, der gilt, wenn man durch interpretiert, aber nicht, wenn man ihn durch interpretiert. Ohne Einschränkung sei . Wegen der Dichtheit der rationalen Zahlen in gibt es eine rationale Zahl mit

    Sei . Dann bedeuten diese Ungleichungen und . Somit ist der Ausdruck , der durch

    mit Summanden links und Summanden rechts realisiert wird, ein Ausdruck, der bei Interpretation von durch gilt, bei Interpretation durch aber nicht.

  2. Da das Symbolalphabet abzählbar ist, gibt es überhaupt nur abzählbar viele Ausdrücke in der Sprache . Da die reellen Zahlen überabzählbar sind, kann es also aus Anzahlgründen gar nicht für jede reelle Zahl einen charakterisierenden Ausdruck geben.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (5 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische euklidische Axiom genau dann gilt, wenn euklidisch ist.


Lösung

Es sei gegeben. Sei zunächst euklidisch und sei

Somit gibt es eine Welt mit und mit

Es sei eine Welt mit . Nach der euklidischen Eigenschaft ist dann auch , daher ist

Somit ist

Es sei nun nicht euklidisch und seien Punkte mit , , aber nicht . Es sei eine Aussagenvariable und sei die Belegung, bei der in allen von aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

und somit

In gilt hingegen , also

Somit gilt

und damit