Kurs:Einführung in die mathematische Logik/16/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 4 0 22 5 0 3 3 0 0 3 0 0 0 0 0 46




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.
  2. Ein Ideal in einem kommutativen Ring .
  3. Die Variablensubstitution für einen -Ausdruck , wobei Variablen und fixierte -Terme seien.
  4. Die Ableitbarkeit eines Ausdrucks im prädikatenlogischen Kalkül.
  5. Die Arithmetische Repräsentierbarkeit einer Abbildung
  6. Eine (formale) Modallogik.


Lösung

  1. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
    1. Wenn und Terme sind, so ist
      ein Ausdruck.
    2. Wenn ein -stelliges Relationssymbol ist und Terme sind, so ist

      ein Ausdruck.

    3. Wenn und Ausdrücke sind, so sind auch

      Ausdrücke.

    4. Wenn ein Ausdruck ist und eine Variable, so sind auch

      Ausdrücke.

  2. Ein Ideal ist eine nichtleere Teilmenge , für die die beiden folgenden Bedingungen erfüllt sind:
    1. Für alle ist auch .
    2. Für alle und ist auch .
  3. Die Variablensubstitution definiert man rekursiv über den Aufbau der -Ausdrücke.
    1. Für Terme setzt man
    2. Für ein -stelliges Relationssymbol und Terme setzt man
    3. Für einen Ausdruck setzt man
    4. Für Ausdrücke und setzt man

      und ebenso für die anderen zweistelligen Junktoren.

    5. Für einen Ausdruck seien diejenigen Variablen (unter den ), die in frei vorkommen. Es sei , falls nicht in vorkommt. Andernfalls sei die erste Variable (in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge), die weder in noch in vorkommt. Dann setzt man

      und ebenso für den Existenzquantor.

  4. 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.

  5. Die Abbildung 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. Eine unter aussagenlogischen Ableitungen abgeschlossene Teilmenge der modallogischen Sprache heißt (formale) Modallogik.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. /Fakt/Name
  2. Der Endlichkeitssatz für die Prädikatenlogik.
  3. /Fakt/Name


Lösung

  1. /Fakt
  2. Es sei ein Symbolalphabet, eine Menge an -Ausdrücken und ein weiterer -Ausdruck. Dann gilt genau dann, wenn es eine endliche Teilmenge gibt mit .
  3. /Fakt


Aufgabe (4 (1+3) Punkte)

In einer Höhle befinden sich im Innern am Ende des Ganges vier Personen. Sie haben eine Taschenlampe bei sich und der Gang ins Freie kann nur mit der Taschenlampe begangen werden. Dabei können höchstens zwei Leute gemeinsam durch den Gang gehen. Die Personen sind unterschiedlich geschickt, die erste Person benötigt eine Stunde, die zweite Person benötigt zwei Stunden, die dritte Person benötigt vier Stunden und die vierte Person benötigt fünf Stunden, um den Gang zu durchlaufen. Wenn zwei Personen gleichzeitig gehen, entscheidet die langsamere Person über die Geschwindigkeit.

  1. Die Batterie für die Taschenlampe reicht für genau Stunden. Können alle vier die Höhle verlassen?
  2. Die Batterie für die Taschenlampe reicht für genau Stunden. Können alle vier die Höhle verlassen?


Lösung Höhle/Taschenlampe/Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe weiter

Es sei eine (nichtleere) Aussagenvariablenmenge und

die Menge aller Wahrheitsbelegungen auf . In dieser Aufgabe untersuchen wir und die Abbildung

Dabei spielen die beiden folgenden Teilmengen eine Rolle.

Es sei die folgendermaßen festgelegte Teilmenge. Eine Abbildung gehört genau dann zu , wenn es eine endliche Teilmenge derart gibt, dass ist (dies ist in Aufgabenteil 2 zu erläutern).

Es sei die durch die folgenden Bedingungen rekursiv festgelegte Teilmenge.

a) Zu gehört

zu .


b) Wenn ist, so gehört auch zu , wobei die Vertauschungsabbildung bezeichnet.


c) Wenn sind, so gehören auch und zu .

  1. Ist injektiv?
  2. Es sei eine Teilmenge. Zeige, dass es eine natürliche surjektive Abbildung

    und eine natürliche injektive Abbildung

  3. Zeige, dass die in (2) beschriebene Abbildung

    die Evaluationen , die Verknüpfung mit und die Minima und Maxima respektiert.

  4. Man gebe bei unendlich ein an, das nicht zu gehört.
  5. Es sei endlich. Zeige
  6. Zeige .
  7. Zeige, dass das Bild von mit übereinstimmt.


Lösung

  1. ist nicht injektiv, da beispielsweise und Tautologien sind und daher beide auf die konstante Abbildung geschickt werden, die jeder Belegung den Wert zuordnet.
  2. Es sei eine Teilmenge. Es gibt die natürliche Abbildung

    die jeder Belegung auf die eingeschränkte Belegung auf der Teilmenge zuordnet. Diese Abbildung ist surjektiv, da man jede Belegung auf zu einer Belegung auf fortsetzen kann, indem man auf willkürlich Wahrheitswerte festlegt (beispielsweise konstant gleich ). Mit Hilfe dieser Abbildung ist durch

    eine Abbildung festgelegt. Diese ist injektiv: wenn zwei Abbildungen verschieden sind, so gibt es eine Belegung mit . Dann gilt dies auch für eine Fortsetzung von auf ganz , und somit sind die Bilder von und von in verschieden.

  3. Sei . Dann ist für jede Belegung

    also ist

    Für ist

    Für ist

    und ebenso für das Minimum.

  4. Wir betrachten die Abbildung , die die konstante Nullbelegung auf und jede andere Belegung auf abbildet. Wir müssen zeigen, dass diese Abbildung nicht von einer Abbildung aus zu einer endlichen Teilmenge herrührt. Sei also endlich gegeben. Da unendlich ist, gibt es ein , . Es sei die Belegung auf , die auf der Teilmenge den Wert hat und an den Wert (und an den anderen Variablen einen beliebigen Wert) und die konstante Nullbewertung auf . Dann ist und . Wegen

    besitzen aber die beiden auf eingeschränkten Belegungen unter jedem den gleichen Wert und somit ist

  5. Es sei endlich. Die Belegungen auf entsprechen den Teilmengen aus , indem man mit identifiziert. Zu jeder Belegung gibt es eine Abbildung , die diese Belegung auf und alle anderen Belegungen auf abbildet. Dabei gilt

    da der zweite Ausdruck für eine Belegung genau dann den Wert liefert, wenn für alle die Beziehung

    genau dann gilt, wenn ist, was genau bei der Fall ist. Da die zu gehören und unter der Verknüpfung mit und unter den Minima von (endlich vielen) Abbildungen abgeschlossen ist, gehören die zu .

    Ein Abbildung ist dadurch festgelegt, für welche Belegungen sie den Wert ergibt. Wenn , , diese Belegungen sind, so ist

    Da unter den Maxima von (endlich vielen) Abbildungen abgeschlossen ist, gehört zu .

  6. Sei zuerst . Dann gibt es eine endliche Teilmenge mit . Nach Teil (5), angewendet auf , gehört zu der in mit den gleichen Rekursionsvorschriften erzeugten Menge und damit zu . Wenn umgekehrt ist, so wird rekursiv erzeugt. Dabei gehen nur endlich viele Startglieder ein. Den Konstruktionsprozess, der zu führt, kann man daher auch über der endlichen Menge durchführen, und somit ist nach Teil (3).
  7. Den Nachweis, dass zu jedem das Bild zu gehört, führen wir rekursiv über den Aufbau von . Zu einer Aussagenvariablen ist

    Zu ist

    wenn also nach abgebildet wird, so auch die Negation. Wegen

    und

    werden mit und auch die Konjunktion und die Disjunktion nach abgebildet. Da man die Implikation und die Äquivalenz durch die anderen Junktoren ausdrücken kann, und für semantisch äquivalente Ausdrücke der Wert unter gleich bleibt, werden mit den Bestandteilen auch und nach abgebildet.

    Zum Nachweis, dass jede Abbildung zum Bild gehört, gehen wir rekursiv über den Aufbau von vor. Für die Evaluationen gilt

    Wenn zum Bild gehört, sagen wir

    so gehört wegen

    auch zum Bild. Wenn und zum Bild gehören, sagen wir

    und

    so gehören wegen

    und

    auch das Minimum und das Maximum dazu.


Aufgabe (5 Punkte)

Es sei eine endliche Menge an Aussagen. Skizziere ein Entscheidungsverfahren, mit dem man feststellen kann, ob widersprüchlich ist oder nicht.


Lösung

In den endlich vielen Ausdrücken von kommen insgesamt nur endlich viele Aussagenvariablen vor, sagen wir . Für jede -Kombination

untersucht man, ob widersprüchlich ist. Da durch jede Aussagenvariable entweder positiv oder in ihrer Negation aus ableitbar ist, kann man für jedes überprüfen, ob aus ableitbar ist. Wenn die durch gegebene Belegung sämtliche erfüllt, so hat man eine Belegung gefunden, die zeigt, dass erfüllbar und damit widerspruchsfrei ist. Im andern Fall stellt sich heraus, dass zu jedem mindestens ein die Belegung falsch bekommt. Nach Fakt ***** ist oder ableitbar, wobei im gegebenen Fall nur die zweite Möglichkeit

verbleibt. Wegen erhält man also

Da dies für jede Kombination gilt, kann man mit mehrfacher Anwendung der Fallunterscheidungsregel

zeigen. In diesem Fall ist also widersprüchlich.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (3 Punkte)

Es sei eine Aussage(nform), in die man eine natürliche Zahl einsetzen kann. Diskutiere den Unterschied zwischen den beiden Aussagen

Was ist die mathematische Relevanz der beiden Aussagen?


Lösung Vollständige Induktion/Allquantor/Aufgabe/Lösung


Aufgabe (3 Punkte)

Wir rechnen mit den Zahlen nach den folgenden Verknüpfungstabellen.

und


Zeige, dass es sich dabei um einen kommutativen Halbring handelt. Gilt für diesen die Abziehregel?


Lösung

Es sei die in Frage stehende Struktur mit der angegebenen Addition und Multiplikation. Die Abbildung

die auf , auf , auf und jede weitere Zahl auf abbildet, ist surjektiv und sie respektiert, wie eine direkte Durchsicht zeigt, die Addition und die Multiplikation. Somit übertragen sich die Gesetze eines kommutativen Halbringes von nach . Die Abziehregel gilt in nicht, da

ist, aber


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (3 Punkte)

Erstelle ein Programm für eine Registermaschine, das abwechselnd und ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Sprungbefehl verwendet.


Lösung

Die Register und seien zu Beginn leer.

Am Anfang wird der erste Register auf erhöht und dies wird im zweiten Befehl ausgedruckt. Im dritten Befehl wird dieser Registerinhalt auf reduziert und dies im vierten Befehl ausgedruckt. Mit dem fünften Befehl wird auf den ersten Befehl umgeleitet, da der zweite Register stets auf bleibt, so dass sich alles wiederholt.


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 (0 Punkte)


Lösung /Aufgabe/Lösung