Kurs:Einführung in die mathematische Logik/2/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
Punkte 3 4 1 4 9 4 6 7 7 2 3 3 12 65



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 -stellige Relation auf einer Menge .
  3. Die Folgerungsbeziehung , wobei eine Menge von -Ausdrücken und ein -Ausdruck ist (und ein Symbolalphabet.)
  4. Die Termsubstitution für -Terme (dabei sei ein Symbolalphabet einer Sprache erster Stufe, paarweise verschiedene Variablen und fixierte -Terme).
  5. Die Addition in einem Dedekind-Peano-Modell .
  6. Die Register-Entscheidbarkeit einer Teilmenge .

Lösung

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

    gilt.

  2. Unter einer - stelligen Relation auf versteht man eine Teilmenge der -fachen Produktmenge .
  3. Man sagt, dass aus folgt, wenn für jede -Interpretation mit auch gilt.
  4. Die Termsubstitution wird rekursiv folgendermaßen definiert.
    1. Für eine Variable ist
    2. Für eine Konstante ist
    3. Für ein -stelliges Funktionssymbol und Terme ist
  5. Die Addition wird über die Addition mit festem definiert, wobei die eindeutig bestimmte Abbildung

    ist, für die

    gilt.

  6. Die Teilmenge heißt Register-entscheidbar, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

    gilt.


 

Aufgabe * (4 Punkte)

Formuliere die folgenden Sätze.

  1. Das Substitutionslemma.
  2. Der Endlichkeitssatz für die Prädikatenlogik.
  3. Der Satz über das Halteproblem.
  4. Der Fixpunktsatz für arithmetische Ausdrücke.

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 ein Symbolalphabet, eine Menge an -Ausdrücken und ein weiterer -Ausdruck. Dann gilt genau dann, wenn es eine endliche Teilmenge gibt mit .
  3. Die Menge

    ist nicht

    -entscheidbar.
  4. Es sei eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem einen Satz mit


 

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 f

Lösung

.


 

Aufgabe * (4 (2+2) Punkte)

Es sei eine unendliche Menge und die Menge, die aus sämtlichen endlichen Teilmengen von besteht.

  1. Ist induktiv geordnet?
  2. Besitzt maximale Elemente?

Lösung

  1. Da unendlich ist, gibt es darin insbesondere verschiedene Elemente zu . Wir betrachten die endlichen Teilmengen

    Diese gehören zu und es liegen die (echten) Inklusionen vor, d.h. diese Mengen bilden eine Kette. Eine obere Schranke für diese Mengen muss aber alle Elemente enthalten, also unendlich sein, und eine solche gibt es nicht in .

  2. Es gibt in keine maximalen Elemente. Ein Element ist eine endliche Menge von . Da unendlich ist, gibt es eine Element mit . Dann ist eine ebenfalls endliche Teilmenge von (gehört also zu ), die echt umfasst, so dass nicht maximal ist.


 

Aufgabe * (9 (1+3+2+1+2) Punkte)

Es sei die prädikatenlogische Sprache, die neben Variablen aus einem zweistelligen Relationssymbol und einem dreistelligen Relationssymbol bestehe. Wir betrachten -Interpretationen , wobei die Grundmenge jeweils aus einem Vektorraum über einem Körper bestehe und als die lineare Unabhängigkeit von zwei und als die lineare Unabhängigkeit von drei Vektoren interpretiert werde.

  1. Zeige
  2. Gilt

    für einen beliebigen Vektorraum?

  3. Gibt es Vektorräume, für die die Aussage in Teil 2 gilt?
  4. Es sei und sei die Standardbasis. Gilt
  5. Es sei als -Vektorraum betrachtet. Gilt

Lösung

  1. Wenn drei Vektoren linear unabhängig sind, so sind insbesondere je zwei davon linear unabhängig.
  2. Dies gilt im Allgemeinen nicht. Dazu sei und wir betrachten die drei Vektoren . Die drei Vektoren sind insgesamt linear abhängig, da in einem zweidimensionalen Vektorraum drei Vektoren immer linear abhängig sind. Dagegen ist jede Auswahl von zwei der Vektoren linear unabhängig, da keiner der Vektoren ein Vielfaches eines anderen ist.
  3. In einem eindimensionalen (oder nulldimensionalen) Vektorraum gilt die Aussage, da es dort keine zwei linear unabhängigen Vektoren gibt und daher der Vordersatz stets falsch ist und somit die Gesamtaussage stimmt.
  4. Die Standardvektoren im sind eine Basis und insbesondere linear unabhängig, daher gilt die Aussage.
  5. Die ist keine rationale Zahl, daher sind die beiden reellen Zahlen und über linear unabhängig, und daher gilt diese Aussage.


 

Aufgabe * (4 Punkte)

Zeige durch ein Beispiel, dass für Terme und eine Variable einer prädikatenlogischen Sprache der Ausdruck

nicht ableitbar sein muss.

Lösung

Wir betrachten , und , wobei Variablen seien und eine Konstante sei. Dann ist und . Die Aussage lautet also in diesem Spezialfall

Dieser Ausdruck ist aber nicht allgemeingültig, da man und durch ein gemeinsames, von verschiedenes Element belegen kann.


 

Aufgabe * (6 (3+1+2) Punkte)

Es seien Variablen und und .

  1. Zeige (ohne Bezug auf den Vollständigkeitssatz) .
  2. Charakterisiere die Modelle mit .
  3. Zeige .

Lösung

  1. Nach der Allversion zu Axiom ***** ist

    eine Tautologie. Der Nachsatz ist . Aus dem gleichen Grund ist

    eine Tautologie. Der Nachsatz ist . Mit Modus Ponens gilt daher

    und

  2. Das bedeutet, dass die Grundmenge der Struktur einelementig sein muss, da alle Elemente gleich sind.
  3. Um die Nichtableitbarkeit zu zeigen, genügt es aufgrund des Korrektheitssatzes, eine Interpretation mit , aber anzugeben. Dazu sei eine zweielementige Menge und die Variablenbelegung sei durch und

    festgelegt.


 

Aufgabe * (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.

Lösung

Es sei allgemeingültig, d.h.

für jede -Interpretation . Wir müssen zeigen, dass dann auch allgemeingültig ist (unter den gegebenen Voraussetzungen). Sei dazu eine Interpretation mit

Aufgrund der Modellbeziehung bedeutet dies, dass es ein (aus der Grundmenge der Interpretation) mit

gibt. Die Variable kommt nach Voraussetzung in nicht frei vor, d.h. bei , dass in nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten

Diese Aussage gilt trivialerweise auch bei . Damit gilt auch

Wir schreiben dies (etwas künstlich) als

Darauf können wir das Substitutionslemma (für die Interpretation und den Term ) anwenden und erhalten

Wegen der vorausgesetzten Allgemeingültigkeit von folgt

Da in nicht frei vorkommt, liefert das Koinzidenzlemma


 

Aufgabe * (7 Punkte)

Es sei ein Symbolalphabet und eine -Interpretation auf einer Menge , wobei die Terminterpretation surjektiv sei. Zeige, dass die Gültigkeitsmenge maximal widerspruchsfrei ist und Beispiele enthält.

Lösung

Zunächst ist aufgrund des Korrektheitssatzes abgeschlossen unter Ableitungen. Für jeden -Ausdruck gilt die Alternative: Entweder oder . Insbesondere ist widerspruchsfrei. Wenn ist, so ist und daher ist widersprüchlich. Also ist maximal widerspruchsfrei.
Wir betrachten nun einen Ausdruck der Form . Wenn gilt, so gilt in für jeden Term , da ja der Vordersatz nicht gilt. Wenn hingegen gilt, so gibt es aufgrund des semantischen Aufbaus der Gültigkeitbeziehung ein derart, dass gilt. Wegen der vorausgesetzten Surjektivität der Belegung gibt es einen Term , der durch interpretiert wird. Daher gilt nach dem Substitutionslemma in . Also gilt in .


 

Aufgabe (2 Punkte)

Man gebe ein Beispiel für eine mathematische Begriffsbildung, die als -Homomorphismus zu einem geeigneten Symbolalphabet verstanden werden kann.

Lösung

S-Homomorphismus/Mathematisches Beispiel/Aufgabe/Lösung

 

Aufgabe * (3 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Primzahlen ausdruckt.

Lösung

Load #10 Store 5 Load #91 Store 6 Load #2 Store 1

Again: Load #2 Store 2 Load #0 Store 3 Store 4

Next: Load 1 Div 2 Store 3 Load 1 Sub #1 Div 2 Store 4 Load 3 Sub 4 JNZero Check2 JZero Prep

Prep: Load 2 Add #1 Store 2 Goto Next

Check2: Load 1 Sub 2 JZero True JNZero False

True: Load 1 Store *5 Load 5 Add #1 Store 5 Load 1 Add #1 Store 1 Load 6 Sub 5 JZero End JNZero Again

False: Load 1 Add #1 Store 1 Goto Again

End: END

 

Aufgabe (3 Punkte)

Erläutere die Churchsche These.

Lösung

Churchsche These/Erläutere/Aufgabe/Lösung

 

Aufgabe * (12 Punkte)

Es sei eine arithmetische Ausdrucksmenge und eine Relation. Es seien Ausdrücke in einer freien Variablen . Zeige, dass aus

nicht folgt, dass in die Relation genau dann repräsentiert, wenn in die Relation repräsentiert.

Lösung

Es sei , und . Wir setzen

Der Ausdruck repräsentiert in die volle Relation , da ja für jedes gilt , aber auch . Ferner gilt . Wir behaupten, dass nicht die Relation in repräsentiert, wobei wir nachweisen wollen. Um diese Nichtableitbarkeit zu zeigen, müssen wir aufgrund des Korrektheitssatzes eine Interpretation angeben, für die gilt, aber nicht gilt. Dazu wählen wir als Grundmenge , wobei wir die und die Multiplikation (die keine Rolle spielt) natürlich interpretieren, und wo wir die Addition auf natürlich interpretieren und setzen, sobald ein Summand negativ ist. Die Variable wird als interpretiert. Bei dieser Interpretation gilt dann weder noch , da überhaupt nicht als Wert der gewählten Addition auftaucht. Daher gilt wiederum die Äquivalenz bei dieser Interpretation. Die Ausdrücke für gelten bei der Interpretation, der Ausdruck bedeutet und gilt hingegen nicht, da bei der Wert von größer als ist und bei der Wert nach Definition gleich ist.