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




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. Ein gerichteter Graph.


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. Ein gerichteter Graph ist eine Menge versehen mit einer fixierten Relation .


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)

Negiere die Aussage „Martina findet alle Jungs im Kurs außer Markus zuckersüß“ durch eine Aussage, in der eine Existenzaussage und eine Oder-Verknüpfung vorkommen.


Lösung

Martina findet Markus zuckersüß oder es gibt im Kurs einen von Markus verschiedenen Jungen, den sie nicht zuckersüß findet.


Aufgabe (7 Punkte)

Beweise den Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen im abzählbaren Fall.


Lösung

Es sei , , eine (surjektive, aber nicht notwendigerweise injektive) Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass keinen Widerspruch enthält. Wir konstruieren eine (endliche oder abzählbar unendliche) Folge von aufsteigenden widerspruchsfreien Teilmengen , wobei in für jede Variable , , die Alternative entweder oder gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über . Für ist dies richtig. Sei schon konstruiert. Bei oder setzen wir

Wegen der Widerspruchsfreiheit von können nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so setzen wir

(man könnte genauso gut hinzunehmen). Nach Konstruktion ist abgeschlossen unter der Ableitungsbeziehung und erfüllt die (Oder)-Alternative für alle Variablen , . Wenn widersprüchlich wäre, so gelte insbesondere . Dann würde aber auch gelten und somit nach der Fallunterscheidungsregel auch , also im Widerspruch zu dem Fall, in dem wir uns befinden. Daher liegt für die Aussagenvariablen auch die Entweder-Oder-Alternative vor.

Mit dieser induktiven Definition setzen wir

Diese Menge ist widerspruchsfrei, da andernfalls schon eines der einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes die Alternative oder . Damit sind die Voraussetzungen von Fakt ***** erfüllt und ist maximal widerspruchsfrei.


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. Die 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 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 (4 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige, dass für jeden -Satz die Gleichheit

gilt.


Lösung

Für Sätze gibt es mi rekursiven Aufbau grundsätzlich zwei Möglichkeiten. Entweder sind sie von der Form oder , wobei in höchstens die Variable frei vorkommt, oder sie entstehen durch aussagenlogische Verknüpfungen aus Sätzen.

Im ersten Fall ergibt sich aus der Voraussetzung , dass in keine Variable frei vorkommt. Somit ist die relevante Variablenmenge und entsprechend die relevante Termmenge leer. Daher ist als „Hilfsvariable“

zu wählen, und es ist

Bei aussagenlogisch zusammengesetzten Sätzen ergibt sich die Behauptung unmittelbar.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (5 Punkte)

Beweise den Satz über die Division mit Rest in einem Peano-Halbring.


Lösung

Wir betrachten zum Nachweis der Existenz die erststufige Aussage

die als einzige freie Variable besitzt. Für ist die Aussage mit und

richtig. Zum Beweis des Induktionsschritts sei

mit den angegebenen Eigenschaften. Daher ist

Wenn kleiner als ist, so erfüllen die geforderten Eigenschaften. Bei muss gelten. Dann ist

so dass das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe *****.


Aufgabe (3 Punkte)

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


Lösung

Der Register sei zu Beginn leer.

Am Anfang wird ausgedruckt. Wenn im Befehl 2 eine ausgedruckt wird, so steht im ersten Register eine und im Befehl 3 wird nicht auf Befehl 1 umgeleitet, sondern nach Befehl 4 weitergeleitet. Danach steht im ersten Register eine und Befehl 5 leitet nach Befehl 2 um, wo die gedruckt wird. Wenn im Befehl 2 eine ausgedruckt wird, so steht im ersten Register eine und im Befehl 3 wird auf Befehl 1 umgeleitet. Dort wird der erste Register auf erhöht und dies wird im Befehl 2 ausgedruckt.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Es sei eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von in die Potenzmenge geben kann.


Lösung

Wir nehmen an, dass es eine surjektive Abbildung

gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir
Da dies eine Teilmenge von ist, muss es wegen der Surjektivität ein geben mit
Es gibt nun zwei Fälle, nämlich oder . Im ersten Fall ist also , und damit, nach der Definition von , auch , Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von , , und das ist ebenfalls ein Widerspruch.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Zeige, dass in einem gerichteten Graphen das modallogische Möglichkeitsaxiom genau dann gilt, wenn in jeder Punkt einen Nachfolger besitzt.


Lösung

Es sei gegeben. Sei zunächst vorausgesetzt, dass in jedes Element einen Nachfolger besitzt und sei

für eine Welt . Es sei mit . Dann ist

und somit

also

Sei umgekehrt angenommen, dass eine Sackgassenwelt besitzt. Dann ist für eine beliebige Aussagenvariable

aber

und das Möglichkeitsaxiom kann nicht gelten.