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




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein Primzahlzwilling.
  2. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
  3. Eine maximal widerspruchsfreie Teilmenge zu einer Menge an Aussagenvariablen.
  4. Die Interpretation der Terme zu einem Symbolalphabet in einer gegebenen -Interpretation auf einer Grundmenge .
  5. Ein allgemeingültiger prädikatenlogischer Ausdruck .
  6. Die Addition in einem Dedekind-Peano-Modell .


Lösung

  1. Ein Primzahlzwilling ist ein Paar bestehend aus und , wobei diese beiden Zahlen Primzahlen sind.
  2. Unter einer Wahrheitsbelegung versteht man eine Abbildung
  3. Die Teilmenge heißt maximal widerspruchsfrei, wenn widerspruchsfrei ist und jede echt größere Menge widersprüchlich ist.
  4. Die Terminterpretation wird induktiv über den Aufbau der Terme für jeden -Term definiert.
    1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
    2. Wenn Terme mit Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.
  5. Man nennt allgemeingültig, wenn er in jeder -Interpretation gilt.
  6. Die Addition wird über die Addition mit festem definiert, wobei die eindeutig bestimmte Abbildung

    ist, für die

    gilt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Lemma von Zorn.
  2. Der Vollständigkeitssatz der Aussagenlogik.
  3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell .


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 eine Menge an Aussagenvariablen und eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei . Dann ist
  3. Es sei eine Menge mit einem fixierten Element und einer Abbildung . Dann gibt es genau eine Abbildung

    die die beiden Eigenschaften

    erfüllt.


Aufgabe (1 Punkt)

Gehört das leere Wort zur Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ?


Lösung

Das leere Wort gehört nicht zur Sprache der Aussagenlogik, da nur die Aussagenvariablen als Startglieder in der rekursiven Definition der Sprache auftreten und in den Rekursionsschritten die Ausdrücke stets verlängert werden.


Aufgabe (2 Punkte)

Zeichne einen Abstammungsbaum für die Aussage


Lösung Aussage/Abstammungsbaum/3/Aufgabe/Lösung


Aufgabe (1 Punkt)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

w w f
w f w
f w f
f f w


Lösung

.


Aufgabe (3 Punkte)

Zeige, dass der aussagenlogische Ausdruck

allgemeingültig ist


Lösung

Wir müssen zeigen, dass für jede Wahrheitsbelegung der Variablen der Wahrheitswert der Gesamtaussage gleich ist. Bei ist und damit ist der Nachsatz und die Gesamtaussage wahr. Sei also im Folgenden . Dann ist . Bei ist der Vordersatz falsch und somit die Gesamtaussage wahr. Sei also . Dann ist der Vordersatz wahr und wir müssen zeigen, dass auch der Nachsatz wahr ist. Es ist dann und , also ist auch in diesem Fall der Nachsatz und die Gesamtaussage wahr.


Aufgabe (2 Punkte)

Es seien verschiedene Aussagenvariablen. Begründe die (Un)Richtigkeit der beiden folgenden Aussagen.

  1. genau dann, wenn .
  2. .


Lösung

  1. Da ebensowenig wie gilt, ist die Äquivalenz der beiden Ableitungen gegeben.
  2. Der Ausdruck ist nicht ableitbar, da er keine semantische Tautologie ist, wie man sieht, wenn man mit und mit belegt.


Aufgabe (6 Punkte)

Man gebe ein Beispiel für eine mathematische Existenzaussage, die mit dem Lemma von Zorn bewiesen wird, und führe den Beweis durch.


Lösung

Beispielsweise wird der Existenzsatz für maximale Ideale in einem kommutativen Ring mit dem Lemma von Zorn bewiesen. Der Beweis geht so:

Wir betrachten die Menge

Diese Menge enthält das Nullideal und ist somit nicht leer. Wir wollen das Lemma von Zorn auf (mit der Inklusion als Ordnungsrelation) anwenden. Dazu sei eine total geordnete Teilmenge. Wir setzen

Man zeigt nun, dass ein Ideal ist, das nicht die enthält. Also gehört es zu und es bildet eine obere Schranke für . Das Lemma von Zorn liefert dann maximale Elemente in , und dies sind maximale Ideale.


Aufgabe (7 (1+1+2+3) Punkte)

Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an.

  1. Die -te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch aus diesem Geschlecht besteht.
  2. Die -te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
  3. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt.
  4. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?


Lösung

  1. Wenn die Generation nur aus dem Geschlecht besteht, so sind nur Paarungen innerhalb dieses Geschlechts möglich und das Ergebnis gehört stets diesem Geschlecht an. Mit Induktion folgt, dass dies über alle folgenden Generationen so bleibt.
  2. Die Generation bestehe aus einem Individuum des Geschlechts und aus einem Individuum des Geschlechts . Die Folgegeneration besteht dann ausschließlich aus dem dritten Geschlecht und nach Teil (1) überträgt sich das auf alle folgenden Generationen.
  3. Wenn es nur ein oder kein Individuum gibt, so ist keine Paarung möglich und die nächste Generation ist leer. Wenn es zwei Individuen gibt, so ist nur eine Paarung möglich und es gibt nur einen Nachkommen, der sich allein nicht fortpflanzen kann. Wenn es dagegen mindestens drei Individuen, egal welchen Geschlechts, gibt, so sind auch mindestens drei Paarungen möglich und die nächste Generation besitzt mindestens wieder drei Individuen.
  4. Wenn drei gleichgeschlechtliche Individuen in einer Generation leben, so erzeugen die drei möglichen Paare stets wieder ebendieses Geschlecht. Die Möglichkeiten sind oder oder und die Periodenlänge ist . Wenn drei unterschiedliche Geschlechter vertreten sind, so ist jedes Geschlecht durch genau ein Individuum vertreten, es liegt also vor. Die drei Paarungen führen dann wieder zu und die Periodenlänge ist ebenfalls . Wenn ein Geschlecht durch zwei Individuen vertreten ist und ein zweites Geschlecht durch ein Individuum, sagen wir , so wird daraus und daraus und daraus . Die Periodenlänge ist also . Von diesem Typ gibt es zwei Generationsabfolgen, nämlich die mit (mit und ) und die mit (mit und ).


Aufgabe (2 Punkte)

Es seien Variablen und ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. ,
  8. ,
  9. ,
  10. ,
  11. ,
  12. .


Lösung

Terme sind , die anderen sind keine Terme.


Aufgabe (1 Punkt)

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.


Lösung

Es gibt eine Hochzeit, auf der Lucy Sonnenschein nicht tanzt.


Aufgabe (4 Punkte)

Es sei das arithmetische Alphabet zusammen mit der Variablenmenge gegeben. Interpretiere den Term

unter den folgenden Interpretationen, wobei die Grundmenge der Interpretation bezeichne.

  1. mit der Standardinterpretation und der Variablenbelegung und .
  2. mit der Standardinterpretation

    und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung und .

  3. , mit

    und wo sowohl als auch als Subtraktion interpretiert werden.

  4. Potenzmenge von mit

    und wo als und als interpretiert wird.


Lösung

  1. Es ist
  2. Es ist
  3. Es ist
  4. Es ist


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

Formuliere die Injektivität für eine Abbildung

prädikatenlogisch mit Hilfe der Verwendung von Sorten.


Lösung

Die Symbolmenge bestehe aus einem einstelligen Funktionssymbol und zwei einstelligen Relationssymbolen und . Wir betrachten den Ausdruck

Bei einer Interpretation in einer Gesamtmenge besagt der linke Ausdruck, dass wenn ein Element zu gehört, dass dann der Funktionswert zu gehört. Das bedeutet also, dass eine Abbildung

vorliegt. Der rechte Ausdruck besagt somit, dass für verschiedene Elemente aus die Bilder verschieden sind, was die Injektivität dieser Abbildung bedeutet.


Aufgabe (8 (3+5) Punkte)

Es sei ein Symbolalphabet erster Stufe und eine Teilmenge. Es sei ein -Term und ein -Ausdruck. Es seien zwei -Interpretationen und in einer gemeinsamen Grundmenge gegeben, die auf identisch seien. Beweise die folgenden Aussagen.

  1. Es ist .
  2. Es ist genau dann, wenn (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus und auf den in frei vorkommenden Variablen identisch sind).


Lösung

(1). Wir führen Induktion über den Aufbau der -Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus betrachten. Für eine Variable (oder eine Konstante) aus ist nach Voraussetzung . Im Induktionsschritt können wir annehmen, dass ein -stelliges Funktionssymbol aus gegeben ist sowie -Terme , für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird in beiden Interpretationen durch die gleiche Funktion interpretiert. Daher ist


(2). Wir führen Induktion über den Aufbau der -Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol aus folgt die Aussage unmittelbar aus (1), da ja in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form aufgrund der Modellbeziehung unmittelbar klar. Sei nun ein -Ausdruck der Form gegeben, und es gelte . Dies bedeutet aufgrund der Modellbeziehung, dass es ein derart gibt, dass gilt. Die beiden umbelegten Interpretationen und stimmen auf den Symbolen aus und den in frei vorkommenden Variablen überein: Die Variable wird so oder so als interpretiert und die anderen freien Variablen aus sind auch in frei. Nach Induktionsvoraussetzung gilt und daher wiederum .


Aufgabe (3 Punkte)

Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung die Gleichheit folgt (dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden).


Lösung

Wir führen Induktion über (für die Aussage für beliebige ). Für

folgt die Aussage daraus, dass das neutrale Element der Addition ist. Die Aussage gelte nun für ein bestimmtes . Wir müssen zeigen, dass sie auch für den Nachfolger gilt. Sei also

Aufgrund von Lemma 12.6 (Einführung in die mathematische Logik (Osnabrück 2021))  (2) bedeutet dies

woraus nach Induktionsvoraussetzung

folgt. Aufgrund der Injektivität der Nachfolgerabbildung ergibt sich


Aufgabe (2 Punkte)

Formalisiere in der arithmetischen Sprache die (wahre) Aussage, dass es unendlich viele Primzahlen gibt.


Lösung

Wir arbeiten mit und setzen

was die Primeigenschaft von bedeutet. Eine Formalisierung für die Unendlichkeit der Primzahlen ist

da dieser Ausdruck besagt, dass es oberhalb jeder Zahl eine Primzahl gibt.


Aufgabe (6 (3+3) Punkte)

Es sei ein Modell für die Peano-Axiome für den Nachfolger.

  1. Zeige, dass fixpunktfrei ist, d.h. dass

    für alle .

  2. Zeige, dass periodenfrei ist. D.h. für jedes ist

    wobei

    die -fache Hintereinanderschaltung von bedeutet.


Lösung

  1. Wir zeigen die Aussage

    durch Induktion über . Bei

    ergibt sich unmittelbar aus dem Axiom, dass kein Nachfolger ist. Sei die Aussage für richtig, also

    Die Gleichheit

    wäre in Verbindung mit der Induktionsvoraussetzung ein direkter Widerspruch zur Injektivität der Nachfolgerabbildung. Also ist

    und die Aussage ist bewiesen.

  2. Sei nun und

    fixiert. Wir zeigen

    durch Induktion über . Bei ergibt sich

    da sonst der Nachfolger von wäre. Sei die Aussage nun für richtig, also

    Nehmen wir an, dass die Gleichheit

    gilt. Wegen

    folgt aus der Injektivität der Nachfolgerabbildung direkt

    im Widerspruch zur Induktionsvoraussetzung. Also ist

    und die Aussage ist bewiesen.