Grundlagen der Theoretischen Informatik: Yeti ist ein Dämon.

Question

Bitte geben Sie bei allen Aufgaben alle Zwischenschritte der Rechnungen an!

Aufgabe 1.1

Über den Yeti sind folgende Fakten bekannt:

(i) Wenn der Yeti eine Fälschung ist, dann gibt es keine Beweise für seine Existenz.

(ii) Wenn der Yeti keine Fälschung ist, dann gibt es Beweise für seine Existenz und der
Yeti ist ein Dämon.

(iii) Wenn es keine Beweise gibt oder der Yeti ein Dämon ist, dann ist der Yeti eine
Fälschung und ein Mensch im Kostüm.

(iv) Der Yeti ist ein PR-Gag, wenn er ein Mensch im Kostüm ist.

Darin sind folgende Grundaussagen enthalten:

Der Yeti ist eine Fälschung. (F)
Es gibt Beweise für die Existenz vom Yeti. (B)
Der Yeti ist ein Dämon. (D)
Der Yeti ist ein Mensch im Kostüm. (M)
Der Yeti ist ein PR-Gag. (G)

(a)  Formulieren Sie die Fakten (i) - (iv) in Aussagenlogik um.

(b)  Überführen Sie die Aussagen aus (a) in KNF.

(c) [ Zeigen Sie durch Resolution, dass der Yeti ein PR-Gag ist.

Answer 1

a) (i) ∀x. F(x) → ¬ B(x)

(ii) ∀x. ¬ F(x) →  (B(x) ∧ D(x))

(iii) ∀x. (¬ B(x) ∨ D(x)) →  (F(x) ∧ M(x))

(iv) ∀x. M(x) →  G(x)

b) Du benutzt einfach, dass A → B ⇔ ¬ A ∨ B ist, also:

(i) ∀x. ¬ F(x) ∨ ¬ B(x) (eine Klausel zur Resolution)

(ii) ∀x. F(x) ∨ (B(x) ∧ D(x)) ⇔ ∀x. (F(x) ∨ B(x)) ∧ (F(x) ∨ D(x)) (zwei Klauseln zur Resolution)

(iii) ∀x. (B(x) ∧ ¬ D(x)) ∨ (F(x) ∧ M(x)) Das ist jetzt in DNF, muss also noch in KNF umgewandelt werden. Das überlasse ich mal, da das einfach nur doppelt Negieren und De-Morgan anwenden ist.

Lösung müsste sein: ∀x. (F(x) ∨ B(x)) ∧ (M(x) ∨ B(x)) ∧ (F(x) ∨ ¬D(x)) ∧ (M(x) ∨ ¬D(x)) (also vier Klauseln zur Resolution)

(iv) ∀x. ¬ M(x) ∨ G(x) (eine Klausel zur Resolution)

c) Jetzt einfach die Resolution nach Schema F ausführen. Du müsstest aus den Klauseln von (i) bis (iii) eine Klausel ableiten, die nur noch M(x) beinhaltet. Die kannst du dann mit (iv) kombinieren und erhältst G(x) und bist fertig, da gezeigt ist, dass aus den Aussagen (i) bis (iv) folgt, dass der Yeti ein PR-Gag ist.