Prof. Dr. M. Kreuzer Abgabe: 27.10.2003, 12.15 Uhr Peter Ackermann

Logik für Informatiker

Übungsblatt 2

Aufgabe 3: Bauing. für Anfänger Nachdem Hänsel und Gretel die Hexe in den Ofen gestoßen haben, wollen sie sich über das Knusperhäuschen hermachen. Doch wie allgemein bekannt ist, muss man beim Verspeisen eines sochen Hauses sehr vorsichtig sein, da diese Häuser zur Instabilität neigen. Die beiden wenden sich zunächst einer Wand zu, die aus drei Lebkuchen besteht. Da Hänsel erfolgreich Knusperhäuschenarchitektur studiert hat, erkennt er, dass folgende Regeln aus Sicherheitsgründen unbedingt einzuhalten sind:

1. Man darf höchstens einen der beiden ersten Lebkuchen entfernen.

2. Wenn man den dritten entfernt, muss man auch den zweiten entfernen.

3. Wenn man den zweiten entfernt und den ersten nicht, dann darf man den dritten nicht entfernen.

Da Gretel in Logik aufgepasst hat, weiß sie, dass man vom dritten Lebkuchen besser die Finger lässt.

a) Zeigen Sie, dass sich dies beweisen lässt, indem man die Unerfüllbarkeit der folgenden Formel

zeigt:

F = (¬(A ∧ B)) ∧ (C ⇒ B) ∧ ((¬A ∧ B) ⇒ ¬C) ∧ C

b) Bringen Sie F in konjunktive Normalform.

c) Vereinfachen Sie F so, dass Sie die Unerfüllbarkeit von F zeigen können.

d) Bringen Sie F in disjunktive Normalform.

Aufgabe 4:

a) Beweisen Sie die Distributivität in Satz 1.13.

b) Zeigen Sie, dass (A ⇔ B) äquivalent ist zu ((A ⇒ B) ∧ (B ⇒ A)).