Übungen zur Vorlesung Logik für Informatiker WS 2008/09, Blatt 5

Abgabe: Mittwoch, 3. Dezember 2008, vor der Vorlesung

Schreiben Sie bitte den Namen Ihres Tutors auf Ihr Lösungsblatt! Allgemeiner Hinweis: Es besteht Anwesenheitspflicht bei den Übungen!

Aufgabe 1. Zeigen Sie mit Hilfe der Resolutionsmethode, daß

{{A_{4}, A_{3}}, {A_{4}, A_{2}, ¬A_{3}}, {¬A_{4}, A_{1}}, {A_{4}, ¬A_{2}, ¬A_{3}}, {¬A_{1}}}

nicht erfüllbar ist.

Aufgabe 2. Sei 𝔸 ein endliches Alphabet und W ⊆ 𝔸^{∗} in NP. Argumentieren Sie, daß W entscheidbar ist, wenn auch nicht in polynomialer Zeit.

Aufgabe 3. a) C sei eine Menge von n Klauseln, wobei jede Klausel höchstens 2 Elemente besitzte. Wie viele Klauseln kann man aus C durch sukzessives Bilden von Resultanten höchstens erhalten? Begründen Sie Ihre Antwort.

b) Folgern Sie aus Teil a, daß 2 − SAT ∈ P.

Aufgabe 4. Sei n eine natürliche Zahl und B_{n} die Menge aller Folgen f = (f(i))_{i<n} in {0, 1} der Länge n.

Zeigen Sie, daß

⋁_{i<n}(A_{i,0} ∧ A_{i,1}) ≡ ⋀_{f∈B_{n}} ⋁_{i<n} A_{i,f(i)} .

Zusatz (Bearbeitung freiwillig). Zeigen Sie, daß jede Formel in KNF, die zu

F = ⋁_{i<n}(A_{i,0} ∧ A_{i,1})

äquivalent ist, mindestens 2^{n} viele Klauseln der Länge mindestens n hat. Sie können wie folgt vorgehen.

1. G sei in KNF mit G ≡ F. Die Formel G′ entstehe aus G durch Streichen aller negativen Literale. Dann ist G′ ≡ G.

2. Wir nennen eine Formel in KNF irredundant, wenn keine Klausel echt in einer anderen Klausel enthalten ist. Zeigen Sie, daß je zwei äquivalente Formeln in KNF, die beide irredundant sind und nur positive Literale enthalten, gleich sind.

3. Folgern Sie die Behauptung mit Hilfe der Äquivalenz

F ≡ ⋀_{f∈B_{n}} ⋁_{i<n} A_{i,f(i)} .

Man kann also nicht zu jeder Formel in polynomialer Zeit eine äquivalente Formel in KNF angeben.