Kurs:Einführung in die mathematische Logik/3/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 2 5 3 3 4 7 6 2 4 4 3 6 4 5 64




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Termmenge zu einer Grundtermmenge .
  2. Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge .
  3. Die Multiplikation mit in einem Dedekind-Peano-Modell .
  4. Die Befehle für eine Registermaschine.
  5. Das modallogische Löb-Axiom.
  6. Ein modallogisches Modell.


Lösung

  1. Die Termmenge ist diejenige Teilmenge der Wörter über dem Termalphabet , die durch die folgenden rekursiven Vorschriften festgelegt wird.
    1. Jede Variable ist ein Term.
    2. Jede Konstante ist ein Term.
    3. Für jedes und Terme ist auch ein Term.
  2. Die Menge heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks die Menge widersprüchlich macht.
  3. Die Multiplikation mit ist diejenige aufgrund von Fakt ***** eindeutig bestimmte Abbildung

    für die

    gilt.

  4. Die Befehle für eine Registermaschine sind (dabei bezeichnen Register und Befehlszeilen).
    1. (erhöhe den Inhalt des Registers um , d.h. um einen Strich).
    2. (reduziere den Inhalt des Registers um , d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
    3. (wenn das -te Register leer ist, so gehe zum Befehl , andernfalls zum nächsten Befehl).
    4. Drucke (drucke den Inhalt des ersten Registers).
    5. Halte an.
  5. Das modallogische Axiomenschema

    nennt man Löb-Axiom.

  6. Unter einem modallogischen Modell versteht man einen gerichteten Graphen zusammen mit einer Wahrheitsbelegung für die Aussagenvariablen für jeden Knotenpunkt .


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Lemma von Zorn.
  2. Der Vollständigkeitssatz für Tautologien (Prädikatenlogik).
  3. Der zweite Gödelsche Unvollständigkeitssatz.


Lösung

  1. Sei eine geordnete Menge mit der Eigenschaft, dass jede total geordnete Teilmenge eine obere Schranke in besitzt. Dann gibt es in maximale Elemente.
  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 entscheidbar sei und die Peano-Arithmetik umfasse. Dann ist die Widerspruchsfreiheit nicht aus ableitbar, d.h. es ist


Aufgabe (2 (1+1) Punkte)

Im Pokal spielt Bayern München gegen den TSV Wildberg. Der Trainer vom TSV Wildberg, Herr Tor Acker, sagt „Wir haben in dem Spiel nichts zu verlieren“. Die Logiklehrerin von Wildberg, Frau Loki Schummele, sagt „Wenn die Wildberger in dem Spiel nichts zu verlieren haben, dann haben auch die Münchner in dem Spiel nichts zu gewinnen“. Der Trainer von Bayern München, Herr Roland Rollrasen, sagt „Wir haben in dem Spiel etwas zu gewinnen“.

  1. Ist die Aussage von Frau Schummele logisch korrekt?
  2. Es sei vorausgesetzt, dass die Aussage des Bayerntrainers wahr ist. Welche Folgerung kann man dann für die Aussage von Herrn Acker ziehen?


Lösung

  1. Die Aussage ist logisch korrekt.
  2. Die Kontraposition der korrekten Aussage aus Teil (1) ist: Wenn die Münchner in dem Spiel etwas zu gewinnen haben, dann haben die Wildberger in dem Spiel etwas zu verlieren. Da der Vordersatz, der die Aussage des Bayerntrainers ist, vorausgesetzt werden soll, so folgt mit Modus Ponens, dass die Wildberger in dem Spiel etwas zu verlieren haben. Dies steht im Widerspruch zur Aussage des Trainers von Wildberg, seine Aussage ist also falsch.


Aufgabe (5 (1+1+3) Punkte)

  1. Löse das folgende Minisudoku
  2. Begründe, dass das Minisudoku aus (1) nur eine Lösung besitzt.
  3. Welche mathematischen Beweisverfahren finden sich als typische Argumentationsschemata beim Lösen eines Sudokus wieder?


Lösung

  1. Wir gehen von

    aus. In der dritten Stelle der zweiten Zeile muss eine sein und somit muss rechts oben eine stehen. Dies ergibt

    An der vierten Stelle der dritten Zeile muss eine stehen. In der vierten Zeile muss an der dritten Stelle eine und somit in der vierten Zeile an der ersten Stelle eine stehen. Dies ergibt

    Dies erzwingt

    An der zweiten Stelle der ersten Zeile muss eine stehen, dies ergibt dann die eindeutige Lösung

    1. Direkter Beweis: Durch Betrachten der schon gefundenen Zahlen erschließt man, welche Zahl in ein bestimmtes Feld gesetzt werden muss.
    2. Beweis durch Fallunterscheidung: Man weiß, dass in einem gewissen Feld nur noch zwei Zahlen, sagen wir oder möglich sind. Wenn man nun in beiden Fällen, dass es sich um oder um handelt, jeweils erschließen kann, dass in einem bestimmten anderen Feld die Zahl stehen muss, so steht diese Zahl fest.
    3. Beweis durch Widerspruch: Man weiß, dass in einem gewissen Feld nur noch zwei Zahlen, sagen wir oder möglich sind. Man nimmt nun an, dass es sich um handelt. Wenn man nun erschließen kann, dass sich daraus an irgendeiner Stelle ein Widerspruch ergibt, so kann die Belegung durch nicht gelten und ist richtig.


Aufgabe (3 Punkte)

Beweise durch Induktion über den rekursiven Aufbau der Sprache , dass in jeder Aussage die Anzahl der linken Klammern mit der Anzahl der rechten Klammern übereinstimmt.


Lösung

Wenn eine Aussagenvariable ist, so kommt darin weder eine linke noch eine rechte Klammer vor und die Anzahl stimmt überein. Zum Beweis der Rekursionsschritte sei zunächst und vorausgesetzt, dass die Anzahl der linken und die Anzahl der rechten Klammern in übereinstimmen. Dann besitzt sowohl eine linke als auch eine rechte Klammer mehr als , so dass die Anzahlen wieder übereinstimmen. Sei nun mit und sei vorausgesetzt, dass linke und auch rechte Klammern und linke und auch rechte Klammern besitzt. Dann besitzt linke und auch rechte Klammern.


Aufgabe (3 Punkte)

Zeige, dass eine Regel der Form

Wenn , dann gelten kann, ohne dass gilt.


Lösung

Es gilt die Regel: Wenn , dann , wobei zwei verschiedene Aussagenvariablen sind, und zwar aus dem einfachen Grund, dass nicht gilt. Dagegen gilt nicht.


Aufgabe (4 Punkte)

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


Lösung

Die Voraussetzung bedeutet, dass es Ausdrücke mit

und mit

gibt. Daraus ergibt sich mit Hilfe (der Regelversion) von Fakt *****  (2)

Es gilt die Tautologie (Axiom *****  (2),)

Aus der Regelversion dieses Axioms ergibt sich

Dies bedeutet .


Aufgabe (7 (3+4) Punkte)

Es sei eine Variablenmenge, eine Konstante und zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck , der durch

gegeben ist.

  1. Zeige, dass bei Interpretation in einem Körper wahr wird, wenn man als und als Subtraktion, Addition und Multiplikation interpretiert.
  2. Welcher wichtige mathematische Satz verbirgt sich dahinter?


Lösung

  1. Sei ein Körper mit Elementen gegeben und sei vorausgesetzt, dass

    ist. Unter Verwendung des Distributivgesetzes (bzw. der zweiten binomischen Formel) bedeutet dies

    Entsprechend ist

    Wenn wir davon zweimal abziehen, und zwar in der oben etablierten Form, so ändert sich der Wert nicht und dies ist gleich

    was insgesamt die Behauptung ist.

  2. Es handelt sich bei um den Satz des Pythagoras. Die sechs Variablen definieren drei Punkte in der Ebene , sagen wir

    Die Verbindungsvektoren sind dann

    und

    Das Skalarprodukt dieser beiden Vektoren ist

    Dass dies gleich ist, bedeutet, dass diese beiden Vektoren aufeinander senkrecht stehen, dass also ein rechtwinkliges Dreieck mit dem rechten Winkel an bilden. Das Quadrat der Länge der Strecke von nach ist

    und entsprechend ist

    und

    Der Nachsatz drückt also die Längenbeziehung im rechtwinkligen Dreieck aus.


Aufgabe (6 Punkte)

Beweise die Termaussage des Substitutionslemmas.


Lösung

Dies wird über den induktiven Aufbau der Terme bewiesen. (1). Für eine Konstante ist die Aussage richtig, da ihre Interpretation unverändert ist. Für eine Variable macht man eine Fallunterscheidung. Wenn

mit einer der an der Substitution beteiligten Variablen ist, so ist

Bei einer an der Substitution nicht beteiligten Variablen ist

Wenn ein -stelliges Funktionssymbol ist und Terme sind, für die die Gleichheit schon bekannt ist, so ist


Aufgabe (2 Punkte)

Formalisiere prädikatenlogisch mit einem geeigneten Symbolalphabet , dass ein Untervektorraum in einem Vektorraum über einem Körper vorliegt.


Lösung

Wir gehen davon aus, dass wir für und schon eine prädikatenlogische Beschreibung wie in Beispiel ***** gefunden haben. Zur prädikatenlogischen Beschreibung eines Untervektorraumes führen wir ein weiteres einstelliges Relationssysmbol ein. Die folgenden Axiome charakterisieren dann einen Untervektorraum.


Aufgabe (4 Punkte)

Zeige, dass in einem Peano-Halbring zu die Division mit Rest eindeutig ist.


Lösung

Es gelte

mit

Ohne Einschränkung können wir annehmen. Dann ist

mit einem und somit ist

Aufgrund der Abziehregel ergibt sich

Bei ist nach Fakt *****. Dann ergibt sich der Widerspruch

wegen der Verträglichkeit der Ordnung mit der Multiplikation. (siehe Fakt *****). Also ist und damit und .


Aufgabe (4 Punkte)

Beschreibe die wesentlichen Punkte bei der Konstruktion eines Modells, mit dem man die Erfüllbarkeit einer maximal widerspruchsfreien Ausdrucksmenge, die Beispiele enthält, nachweist.


Lösung Vollständigkeitssatz/Konstruktion/Aufgabe/Lösung


Aufgabe (3 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe zum Symbolalphabet .


Lösung

Die Äquivalenzklassen sind und . Die in der angegebenen Sprache formulierbare Eigenschaft wird nur durch das neutrale Element erfüllt und ist somit ein charakterisierender Ausdruck für . Nach (dem Zusatz zu) Fakt ***** sind Elemente, die unter einem Automorphismus aufeinander abgebildet werden, zueinander elementar äquivalent. Die Komponentenvertauschung bildet auf ab und die invertierbare Matrix (wir fassen als Vektorraum über auf) ergibt einen Automorphismus, der auf abbildet.


Aufgabe (6 Punkte)

Es sei eine endliche Teilmenge. Man gebe ein Programm für eine Registermaschine an, das nur auf einen einzigen Register Bezug nimmt, das bei jeder Eingabe (in ) immer anhält und das im Anhaltezustand in genau dann den Wert besitzt, wenn die Eingabe zu gehört.


Lösung

Wir ordnen die endlich vielen, sagen wir , Zahlen aus in aufsteigender Reihenfolge, also

Wir setzen

und

für . Die sind also einfach die Differenzen zwischen den aufeinanderfolgenden Zahlen aus , und es ist

Wir erstellen das Programm mit Hilfe von Programmblöcken der Länge der Form

Der Inhalt von wird also abwechselnd um reduziert und abwechselnd wird gefragt, ob der Inhalt leer ist, wobei im leeren Fall auf die Befehlszeile verwiesen, aber die allerletzte Abfrage des Blockes auf die -te Befehlszeile verweist. Bei

besteht der erste Block allein aus . Diese Blöcke werden hintereinander geschrieben, und das Programm wird durch

abgeschlossen.

Die Wirkungsweise des Programms macht man sich folgendermaßen klar. Zu jedez zu testenden Zahl gibt es ein eindeutiges mit

(wobei als zu lesen ist) oder aber

In den ersten Programmblöcken bleibt der Inhalt des Registers positiv, da ja insgesamt nur

von abgezogen wird. Daher gelangt man in den entscheidenden -ten Block. Wenn dieser Block begonnen wird, steht im Register der Wert , und für diesen Wert gilt

Bei

ist

so dass durch das Abziehen in diesem Block die erreicht wird, und zwar vor dem vorletzten Befehl des Blocks, so dass nach umgeleitet wird. Dort wird um erhöht (was nur bei benötigt wird) und das Endergebnis ist nicht , was korrekt ist.

Bei

ist

so dass durch das Abziehen in diesem Block die erreicht wird, und zwar genau im vorletzten Befehl des Blocks. Im nächsten Befehl wird nach umgeleitet und das Programm hält an mit der als Ausgabe, was auch korrekt ist. Bei werden alle Blöcke ohne Umleitung durchlaufen, in wird erhöht und anschließend wird angehalten mit einen positivem Inhalt des ersten Registers.


Aufgabe (4 Punkte)

Es sei

eine arithmetisch repräsentierbare Abbildung. Zeige, dass zu jedem Punkt die Faser

arithmetisch repräsentierbar ist.


Lösung

Nach Voraussetzung gibt es einen -Ausdruck in freien Variablen derart, dass für alle -Tupel die Äquivalenz genau dann, wenn gilt. Es sei

ein Punkt. Dabei gilt insbesondere für beliebige die Gleichheit genau dann, wenn gilt. Diese Gleichung bedeutet, dass zur Faser über gehört. Daher ist der Ausdruck

in den freien Variablen ein Ausdruck, der die Faser über arithmetisch repräsentiert.


Aufgabe (5 Punkte)

Zeige, dass eine aufzählbar axiomatisierbare Theorie auch -aufzählbar ist.


Lösung

Es sei eine -aufzählbare Satzmenge, die axiomatisiert, und es sei , , eine -Aufzählung von . Es sei , , eine -Aufzählung der prädikatenlogischen Tautologien aus . Wenn ein Satz aus ableitbar ist, so gibt es eine endliche Auswahl aus (bzw. aus der gewählten Aufzählung) derart, dass

eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem wächst, das Gewünschte: Für jedes notiert man die Tautologien in der Form

Wenn überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes , ob alle zu gehören. Falls ja, und wenn ein Satz ist, so wird notiert. Danach geht man zum nächsten . Wenn man , erreicht hat, so geht man zu , wobei man aber wieder bei anfängt.