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

Korrigierte Fassung vom 22. November 2008: Aufgabe 4 b) wurde geändert.

Hinweis: Die Bearbeitung der korrigierten Fassung statt der ursprünglichen ist freiwillig, falls Sie die korrigierte Fassung bearbeiten, müssen Sie die ursprüngliche also nicht bearbeiten und umgekehrt.

Abgabe: Mittwoch, 26. November 2008, vor der Vorlesung

Aufgabe 1. Nehmen Sie an, Ihnen stehen die Apparaturen zur Verfügung, um die folgenden chemischen Reaktionen durchzuführen:

MgO + H_{2} ⟶ Mg + H_{2}O
C + O_{2} ⟶ CO_{2}
H_{2}O + CO_{2} ⟶ H_{2}CO_{3}

Ferner sollen in unserem Labor die Grundstoffe MgO, H_{2}, O_{2} und C vorhanden sein. Zeigen Sie, daß es unter diesen Voraussetzungen möglich ist, H_{2}CO_{3} herzustellen.

Aufgabe 2. Zeigen Sie mit Hilfe der Resolutionsmethode, daß die Formel

((¬A_{1} ∧ ¬A_{2} ∧ A_{3}) ∨ (¬A_{1} ∧ ¬A_{3}) ∨ (A_{2} ∧ A_{3}) ∨ A_{1})

eine Tautologie ist.

Aufgabe 3. Zeigen Sie mit Hilfe der Resolutionsmethode, daß A_{1} ∧ A_{2} ∧ A_{3} eine Folgerung aus der Klauselmenge

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

ist.

Aufgabe 4. a) Zeigen Sie, daß DNF − SAT ∈ P. Genauer: Geben Sie einen Algorithmus an, welcher bei Eingabe einer aussagenlogichen Formel F in DNF in polynomialer Zeit entscheidet, ob F erfüllbar ist oder nicht.

b) Zeigen Sie unter der Annahme P ≠ NP, daß es nicht in polynomialer Zeit möglich ist, eine beliebige Formel F in eine Formel G in DNF derart zu überführen, daß F erfüllbar ist genau dann, wenn G erfüllbar ist.