Prof. Dr. M. Kreuzer Abgabe: 17.01.2003, 14h

Logik für Informatiker

Übungsblatt 12

Aufgabe 28: Ein Tag zum Vergessen Als Alice den Wald des Vergessens betrat, vergaß sie nicht alles, nur bestimmte Dinge. Sie vergaß oft ihren Namen, und die Sache, die sie mit der größten Wahrscheinlichkeit vergaß, war der Wochentag. Nun waren der Löwe und das Einhorn häufige Besucher des Waldes. Jedoch sind diese zwei gar seltsame Gesellen. Der Löwe lügt Montags, Dienstags und Mittwochs und sagt an den anderen Wochentagen die Wahrheit. Das Einhorn lügt an Donnerstagen, Freitagen und Samstagen und sagt die Wahrheit an den anderen Tagen. Eines Tages traf Alice die beiden unter einem Baum. Der Löwe sagte: ”Gestern war einer meiner Lügentage.“ Das Einhorn sagte: ”Gestern war einer meiner Lügentage.“ Alice, die früher immer die Logik-Vorlesung nachgearbeitet und alle Übungsaufgaben bearbeitet hatte, konnte anhand dieser Aussagen ableiten, welcher Wochentag war.

a) Man formuliere das Problem aussagenlogisch.

b) Man wandle diese Formulierung in ein System von Gleichungen in IF_{2} um und löse das Problem, indem man das Gleichungssystem löst.

Dabei ist IF_{2} = {0, 1} der zweielementige Ring, dessen Verknüpfungen definiert sind durch:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0
0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1.

Man kann nachrechnen, dass die Axiome aus Aufgabe 26 (mit e = 0) in IF_{2} gelten. Jeder atomaren aussagenlogischen Formel ordne man eine Variable in IF_{2} zu. Ein Wahrheitswert von 0 bzw. 1 entspreche einer Belegung der zugehörigen Variable mit dem entsprechenden Wert. Sind A, B atomare aussagenlogische Formeln und A′, B′ die zugehörigen Variablen in IF_{2}, ergeben sich die folgenden Entsprechungen:

¬A ˆ= A′ + 1
A ∨ B ˆ= A′ + B′ + (A′ · B′)
A ∧ B ˆ= A′ · B′
A XOR B := ((A ∧ ¬B) ∨ (B ∧ ¬A)) ˆ= A′ + B′.

Klausuranmeldung: Die erste Klausur findet am 08.02.2003 von 13.15 Uhr bis 16.15 Uhr statt, die Nachklausur am 10.05.2003 von 9.15 Uhr bis 12.15 Uhr. Eine Teilnahme an der Nachklausur ist auch ohne Teilnahme an der ersten Klausur möglich, jedoch wird dringend empfohlen, den ersten Termin wahrzunehmen. Für die Nachklausur ist nicht zugelassen, wer bereits die erste Klausur bestanden hat. Eine Anmeldung zu den Klausuren ist erforderlich und erfolgt bitte durch eine E-Mail mit Name, Vorname (in der Reihenfolge) und Matrikelnummer an die Adresse

peter.ackermann@mathematik.uni-dortmund.de mit der Betreffzeile ”Klausuranmeldung“

für die erste Klausur bis spätestens 04.02.2003, für die Nachklausur in der Zeit vom Tag des Aushangs der Klausurergebnisse bis 06.05.2003. Anhand der Anmeldungen erfolgen die Zuteilungen der Hörsäle, welche auf der Homepage der Vorlesung veröffentlicht und an den Hörsälen ausgehängt werden. Diese sind: Audimax, HG II HS 3, 5 und 6.