Frage:
Text erkannt:
Aufgabe 2.3 [Streichalgorithmus]
25 Punkte
Definition: Eine aussagenlogische Formel \( \varphi \) ist zu einer Horn-Klauselmenge \( \mathcal{K} \) äquivalent, falls für jede zu \( \varphi \) und \( \mathcal{K} \) passende Belegung \( \alpha \) gilt:
\( \alpha \models \varphi \Longleftrightarrow \alpha \models \mathcal{K} \)
a) Gegeben sei die Formel
\( \varphi=((\neg A \vee F) \rightarrow((A \wedge C) \vee(A \wedge \neg D))) \wedge B \wedge(\neg C \vee(D \wedge B)) \wedge E \wedge(\neg B \vee E \vee \neg D) \wedge((A \wedge B) \rightarrow F) \)
Geben Sie eine zu \( \varphi \) äquivalente Horn-Klauselmenge \( \mathcal{K} \) an.
(7 Punkte)
b) Ist die in Teilaufgabe (a) angegebene Formel erfüllbar?
Wenden Sie den Streichalgorithmus an, um herauszufinden, ob die Formel erfüllbar ist. Geben Sie dabei für jeden Schritt \( i \) die verwendete Tatsachenklausel und die Klauselmenge \( \mathcal{K}_{i} \) an.
(10 Punkte)
c) Geben Sie eine Formel an, die zu keiner Hornformel äquivalent ist. Beweisen Sie, dass Ihre Antwort korrekt ist.
(8 Punkte)
Code:
