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

Logik für Informatiker

Übungsblatt 14: Wiederholungsblatt

Aufgabe 1: Herr X hat drei Projekte A, B, C zu erledigen. Er schafft es nicht, alle drei bis Ende der Woche fertigzustellen, B oder C müssen aber bis dahin fertig sein. Um B fertigstellen zu können, muss A fertig sein, um C fertigstellen zu können, muss B fertig sein. Welche Projekte muss Herr X bis Ende der Woche erledigen?

a) Stellen Sie eine aussagenlogische Formel auf, so dass obige Frage dadurch gelöst wird, dass man ein Modell für diese Formel findet.

b) Lösen Sie das Problem mit der Wahrheitstafelmethode.

Aufgabe 2: Bauer Horst besitzt einen kleinen Acker, einen Wolf und das Schwein Borsti. Wenn der Händler ehrlich ist, ist das Saatgut, das Horst von ihm kauft, gut. Wenn das Saatgut und das Wetter im Sommer gut sind, verdient Horst ausreichend Geld. Wenn er ausreichend Geld hat, füttert er den Wolf. Wenn er den Wolf gefüttert hat und in der Stadt Kirmes ist, geht er in die Stadt und lässt Wolf und Borsti allein. Wenn der Wolf gefüttert worden ist, ist er satt. Wenn der Wolf satt ist oder der Bauer anwesend ist, wird Borsti nicht gefressen.

a) Zeigen Sie, dass diese Situation durch die folgende Hornklauselmenge beschrieben wird:

{{¬H, S}, {¬S, ¬W_{1}, G}, {¬G, W_{2}}, {¬W_{2}, ¬K, A}{¬W_{2}, W_{3}}, {¬W_{3}, ¬B}, {A, ¬B}}

b) Angenommen, in der Stadt ist Kirmes. Wird Borsti nicht gefressen, wenn das Wetter im Sommer gut und der Händler ehrlich waren? Formulieren Sie diese Frage als Unerfüllbarkeitsproblem einer Menge von Hornklauseln und lösen Sie sie mit Hilfe des Markierungsalgorithmus. Geben Sie dabei an, in welchem Schritt Sie welche Aussagen markieren.

Aufgabe 3:

a) Bringen Sie folgende prädikatenlogische Formel in Skolemform:

¬(∀x : (P (x, y) ⇒ Q(f(x)))) ∧ ∀x : ∀y : P (x, f(y))

b) Geben Sie eine prädikatenlogische Struktur an, in der die ursprüngliche Formel aus Teil a) gilt, und eine, in der sie nicht gilt.

Aufgabe 4: Gegeben sei eine Menge von Spielkarten. Man ordne die Karten in einem Kreis so an, dass gilt:

1. Ist eine Karte weder Bild noch Karo, so ist ihr linker Nachbar Karo.

2. Ist eine Karte Karo, so ist ihr rechter Nachbar ein Bild.

a) Zeigen Sie, dass sich die Legeregeln durch folgende Klauselmenge ausdrücken lassen: {{P (x), P (f(x)), Q(x)}, {¬P (f(y)), Q(y)}

b) Beweisen Sie durch prädikatenlogische Resolution, dass es unmöglich ist, obige Aufgabe zu erfüllen, sobald die Menge von Spielkarten eine Karte enthält, die weder Karo noch Bild ist.

Aufgabe 5: Sei M ein Monoid, in dem alle Quadrate eins sind, das heißt M sei eine Menge zusammen mit einer Verknüpfung ∘ : M × M ⟶ M, so dass Folgendes gilt:

(i) (x ∘ y) ∘ z = x ∘ (y ∘ z) für alle x, y, z ∈ M (ii) Es gibt ein e ∈ M mit e ∘ x = x ∘ e = x für alle x ∈ M (iii) x ∘ x = e für alle x ∈ M

a) Übersetzen Sie die Gesetze (i) bis (iii) in gleichungslogische Formeln.

b) Zeigen Sie, dass aus diesen Gesetzen das Kommutativgesetz folgt, dass also gilt x ∘ y = y ∘ x für alle x, y ∈ M

Aufgabe 6: In einem Computerprogramm kommen die vier Integer-Variablen w, x, y, z vor. Ab einem gewissen Zeitpunkt im Programm gilt:

1. Wenn z > 0 ist, ist y > 0.

2. Wenn w ≤ 0 ist, ist x ≤ 0.

3. Wenn w > 0 ist, ist y ≤ 0.

4. Es ist immer z > 0.

a) Übersetzen Sie diese Aussagen in modallogische Formeln.

b) Das Programm endet genau dann, wenn x > 0 ist. Zeigen Sie, dass das Programm nie endet.