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



Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Eine Mersennesche Primzahl.
  2. Eine widersprüchliche Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .
  3. Die Produktmenge aus zwei Mengen und .
  4. Die Bestandteile einer Grundtermmenge.
  5. Ein allgemeingültiger prädikatenlogischer Ausdruck .
  6. Die Ableitbarkeit eines Ausdrucks im prädikatenlogischen Kalkül.

Lösung

  1. Eine Primzahl der Form heißt Mersennesche Primzahl.
  2. Die Ausdrucksmenge heißt widersprüchlich, wenn es einen Ausdruck mit und gibt.
  3. Man nennt die Menge

    die Produktmenge der Mengen und .

  4. Die Bestandteile einer Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.
    1. eine Variablenmenge ,
    2. eine Konstantenmenge ,
    3. zu jedem eine Menge von Funktionssymbolen.
  5. Man nennt allgemeingültig, wenn er in jeder -Interpretation gilt.
  6. 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.


 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Lemma von Zorn.
  2. Der Satz über die Division mit Rest in einem Peano-Halbring.
  3. Der Endlichkeitssatz für die Prädikatenlogik.

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. Sei ein Peano-Halbring und . Dann gibt es zu jedem eindeutig bestimmte mit , , und mit
  3. Es sei ein Symbolalphabet, eine Menge an -Ausdrücken und ein weiterer -Ausdruck. Dann gilt genau dann, wenn es eine endliche Teilmenge gibt mit .


 

Aufgabe * (4 (2+1+1) Punkte)

Folgende Aussagen seien bekannt.

  1. Der frühe Vogel fängt den Wurm.
  2. Doro wird nicht von Lilly gefangen.
  3. Lilly ist ein Vogel oder ein Igel.
  4. Für Igel ist 5 Uhr am Morgen spät.
  5. Doro ist ein Wurm.
  6. Für Vögel ist 5 Uhr am Morgen früh.
  7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

  1. Ist Lilly ein Vogel oder ein Igel?
  2. Ist sie ein frühes oder ein spätes Tier?
  3. Fängt der späte Igel den Wurm?

Lösung

  1. Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2).
  2. Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier.
  3. Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm.


 

Aufgabe * (3 Punkte)

Bei einem Zwei-Personen-Regel-Spiel (wie Schach) spielen zwei Personen ( und ) nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für ist, da ist am Zug und kann schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge aller Stellungen eine Gewinnstellung für (mit am Zug) ist.

Lösung

Wir definieren

und rekursiv

Eine Gewinnstellung ist dann


 

Aufgabe (3 Punkte)

Erläutere das Konzept der Wohldefiniertheit anhand eines typischen Beispiels.

Lösung

Wohldefiniertheit/Typisches Beispiel/Aufgabe/Lösung

 

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 * (1 Punkt)

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

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

Lösung

.


 

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 * (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 * (12 (1+1+4+2+4) Punkte)

Es sei ein dreistelliges Relationssymbol und die zugehörige prädikatenlogische Sprache. Es sei die Interpretation, bei der die Grundmenge die euklidische Ebene ist und durch die dreistellige Relation interpretiert wird, bei der zutrifft, wenn die Punkte auf einer Geraden liegen.

  1. Zeige .
  2. Zeige, dass im Allgemeinen nicht gelten muss.
  3. Es sei . Erstelle eine Ableitung für .
  4. Zeige, dass der Ausdruck bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.
  5. Formuliere einen Ausdruck aus in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.

Lösung

  1. Die Eigenschaft, ob drei Punkte auf einer Geraden liegen, hängt nicht von der Reihenfolge der Punkte ab.
  2. Es seien verschiedene Punkte der Ebene, ein beliebiger Punkt auf der durch definierten Geraden und ein Punkt, der nicht auf dieser Geraden liegt. Dann ist der Vordersatz erfüllt, aber nicht der Nachsatz, und daher gilt die Implikation bei dieser Interpretation nicht.
  3. Aufgrund der Alleinführung im Antezedens gilt für beliebige Variablen die Ableitbarkeit

    Daher gilt mit Modus Ponens

    für beliebige Variablen. Insbesondere gilt

    Ebenso kann man auf

    schließen. Die Transitivität der Äquivalenz liefert

  4. Wenn und durch den gleichen Punkt interpretiert werden und durch einen Punkt und durch einen Punkt , derart, dass diese Punkte nicht auf einer Geraden liegen, so liegen dennoch und auf einer Geraden. Bei einer solchen Belegung sind und wahr, ohne dass alle Punkte auf einer Geraden liegen.
  5. Man nimmt . Die Variablen seien durch die Punkte belegt. Wenn diese Punkte auf einer gemeinsamen Geraden liegen, so liegen insbesondere je drei von ihnen auf einer (nämlich dieser) Geraden und daher gilt bei dieser Belegung. Zum Beweis der Umkehrung sei . Dies bedeutet, dass sowohl als auch als auch jeweils auf einer Geraden liegen. Wenn unter den Punkten nur zwei verschiedene Punkte vorkommen, so liegen alle Punkte auf einer Geraden. Wir können uns also auf den Fall beschränken, wo maximal zwei Punkte identisch sind. Wenn ist, so definiert dies eine eindeutige Gerade, und auf dieser Geraden müssen wegen der Gültigkeit von bzw. sowohl als auch liegen. In diesem Fall liegen alle Punkte auf einer Geraden. Sei nun . Wegen liegen auf einer Geraden.


 

Aufgabe * (5 (2+3) Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben.

  1. Zeige, dass die Substitution für die Terme die Identität ist.
  2. Zeige, dass die Substitution für die Ausdrücke die Identität ist.

Lösung

  1. Wir beweisen die Aussage durch Induktion über den Aufbau der Terme. Für Variablen ist bei direkt und ferner . Konstanten bleiben bei jeder Substitution unverändert. Für ein -stelliges Funktionssymbol und Terme ist

    nach Induktionsvoraussetzung.

  2. Wir beweisen die Aussage durch Induktion über den Aufbau der Sprache für alle Variablen gleichzeitig. Wenn eine Identität von Termen oder eine Relationsaussage ist, so ergibt sich die Behauptung unmittelbar aus Teil (1). Der Induktionsschritt für die aussagenlogischen Junktoren ergibt sich unmittelbar aus der Definition der Substitution. Bei mit kommt nicht im substituierenden Term vor, und daher ist und

    nach Induktionsvoraussetzung. Bei ist nicht frei in und somit ist die relevante Termmenge leer und , also

    nach Induktionsvoraussetzung.


 

Aufgabe * (3 Punkte)

Zeige

Lösung

Die Alleinführung im Antezedens ergibt

und

und daraus zusammen mit Fakt *****  (2)

Die Variable ist sowohl vorne als auch in gebunden. Daher ergibt die Alleinführung im Sukzedens


 

Aufgabe * (4 Punkte)

Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.

Lösung

Aufgrund von Fakt *****, angewendet auf und die Nachfolgerabbildung auf , gibt es genau eine Abbildung

mit den angegebenen Eigenschaften. Wenn man die Rollen vertauscht, so erhält man eine eindeutige Abbildung

mit den gleichen Eigenschaften. Wir betrachten nun die Verknüpfung

Diese erfüllt ebenfalls diese Eigenschaften. Da aber die Identität auf auch diese Eigenschaften erfüllt, folgt aus der Eindeutigkeitsaussage aus Fakt *****, dass ist. Ebenso ist und somit sind und invers zueinander.


 

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

Es sei

  1. Zeige, dass ein kommutativer Halbring ist.
  2. Zeige, dass in die Relationen

    und

    zueinander äquivalent sind.

  3. Zeige, dass nicht irreduzibel in ist.
  4. Zeige, dass es in keine irreduziblen Elemente gibt.
  5. Es sei die Aussage

    Zeige, dass in die Aussage

    wahr ist.

  6. Zeige, dass kein Peano-Halbring ist.

Lösung

  1. Es ist lediglich zu zeigen, dass unter der Addition und der Multiplikation abgeschlossen sind. Dies ist für die Addition mit und der Multiplikation mit klar. Ferner ist die Summe (bzw. das Produkt) von zwei rationalen Zahlen, die beide sind, selbst wieder .
  2. Wenn ist, so ist wegen automatisch auch die rechte Seite erfüllt, und wenn ist, so ist wegen

    auch die linke Seite erfüllt. Wir können also und auf den Fall beschränken. Wenn das Element teilt, so bedeutet dies, dass es ein mit

    gibt. Dies bedeutet einfach, dass der in genommene Quoient zu gehört, also ist. Doch dies ist äquivalent zu .

  3. Es ist

    eine Darstellung in Faktoren, die beide keine Einheit sind.

  4. Die und die (einzige) Einheit sind nach Definition nicht irreduzibel. Für mit ist

    und wegen ist auch

    also gehören die beiden Faktoren zu .

  5. Der erste Teil der Konjunktion, also , ist unmittelbar wegen des ersten Teils der Disjunktion wahr. Sei also wahr für ein bestimmtes . Der Nachfolger davon, also , steht bereits in der Form des zweiten Teils der Disjunktion da.
  6. Wir betrachten das Induktionsaxiom für die Aussage aus Teil (5). Die Voraussetzungen, also Induktionsanfang und Induktionsschritt, gelten wie in Teil (5) gezeigt. Hingegen gilt die Aussage nicht für alle , beispielsweise gilt sie für nicht.