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

Logik für Informatiker

Übungsblatt 8

Aufgabe 18: Warum so viele Bewohner von Transsylvanien geisteskrank sind Inspektor Craig findet heraus, dass der Beginn des Auftretens der Geisteskrankheit in Transsylvanien mit der Ersterscheinung eines Kartenlegespiels zusammenfällt. Die Karten ähneln einem herkömmlichen Skatspiel mit der Ausnahme, dass es nur Bilder in der Farbe Kreuz gibt. (Bube, Dame und König fehlen also in den Farben Karo, Herz und Pik:) Die Karten sind so in in einer Reihe liegende Stapel anzuordnen, dass gilt

1. Eine Karte muss ein As sein, wenn alle Karten im Stapel unmittelbar rechts von dieser Karte Kreuz sind oder in diesem Stapel eine Karte kein Bild ist.

2. Eine Karte muss ein Bild sein, wenn es im Stapel unmittelbar rechts von dieser Karte ein Bild gibt.

Durch eine Unachtsamkeit wurden bei der Produktion des Spiels die Asse vergessen. Inspektor Craig vermutet, dass dadurch die Legeregeln nicht zu erfüllen sind und viele Bewohner Transsylvaniens bei dem Versuch, das Spiel zu spielen, in den Wahnsinn getrieben wurden.

a) Formulieren Sie obige Situation als prädikatenlogische Formel.

b) Beweisen Sie mit Hilfe des Resolutionssatzes der Prädikatenlogik, dass es unmöglich ist, das Spiel zu spielen.

Aufgabe 17: Wenden Sie den Unifikationsalgorithmus auf die Literalmenge

L = {P (f(x), w, f(a)), P (f(w), w, f(z)), P (f(g(z)), x, y)}

an.