Logik:Klausuren/08.02.2003/2.6 Aufgabe

1. Aufgabenstellung

Wir lassen zum aussagenlogischen Resolutionsverfahren noch die folgende Kontraktionsregel zu:

Sei $ D1\; $ eine Klausel, in der neben den Literalen $ p_1,...,p_n , (n \ge 1)\; $ noch $ q\; $ und $ \neg q\; $ vorkommen. $ D\; $ entstehe aus $ D1\; $ durch Streichen der Literale $ q\; $ und $ \neg q\; $. Ist $ D\; $ durch Anwendung der Kontraktionsregel auf $ D1\; $ entstanden, so nennen wir $ D\; $ eine Kontraktion von $ D1\; $. $ \vdash_{ark} F\; $ bezeichne die Aussage, dass $ F\; $ einen Beweis im aussagenlogischen Resolutionsverfahren unter Hinzunahme der Kontraktionsregel hat.

a) Bleibt das aussagenlogische Resolutionsverfahren korrekt, wenn wir die Kontraktionsregel neben der Resolutionsregel ebenfalls zur Bildung einer Resolutionsableitung zulassen? Beweisen Sie Ihre Antwort.

b) Ist die Aussage "Wenn $ \models F\; $ gilt, dann gilt auch $ \vdash_{ark} F\; $" richtig? Beweisen Sie Ihre Antwort.

2. Lösung

a)

Nein, bleibt nicht korrekt, Gegenbeispiel:

$ F = (s \or (\neg s \and (q \and \neg q)))\; $
$ G = \neg F = (\neg s \and (s \or (\neg q \or q)))\; $

G in Klauselform: $ <[\neg s],[s,q,\neg q]>\; $
$ D_1 = [s,q,\neg q]\; $
$ D = [s]\; $

Das Resolutionsableitung mit Hinzunahme der Kontraktionsregel für $ F\; $ sieht also folgendermaßen aus:

1 $ [\neg s]\; $
2 $ [s,q,\neg q] (= D_1)\; $
---
3 $ [s] (= D)\; $
4 $ [] res(1,3)\; $

F ist demnach Tautologie.

Das Resolutionsableitung ohne Hinzunahme der Kontraktionsregel für $ F\; $:

1 $ [\neg s]\; $
2 $ [s,q,\neg q]\; $
---
3 $ [q,\neg q] res(1,2)\; $
4 keine weiteren Resolutionsableitungen möglich

F ist keine Tautologie.

Widerspruch zwischen beiden Ableitungen.
Formel F ist keine Tautologie, da F widerlegbar mit $ s^I = f\; $

b)

(Diese Aufgabe zielt auf die Vollständigkeit des Resolutionsverfahrens unter Zuhilfenahme der Kontraktionsregel ab.)

Ja, Aussage ist richtig.

Da das Resolutionsverfahren ohne die zusätzliche Kontraktionsregel vollständig ist (Satz 3.42), kann jede Lösung durch die Grundregeln gefunden werden. Es können höchstens weitere Ergebnisse geliefert werden, was Auswirkungen auf die Korrektheit, nicht aber auf die Vollständigkeit haben kann.

3. Lösungsweg

b)

Warum geht es hier um die Vollständigkeit?

Satz 3.42 sagt: "$ \models_a F\; $ gilt genau dann, wenn $ \vdash_{ar} F\; $"
Das läßt sich darstellen als: $ \models_a F \leftrightarrow\ \vdash_{ar} F\; $
Und im Beweis des Satzes: "wenn $ \models_a F\; $ gilt, dann auch $ \vdash_{ar} F\; $ (Vollständigkeit)"

Aufgabenstellung sagt: "Wenn $ \models F\; $ gilt, dann gilt auch $ \vdash_{ark} F\; $"
Das läßt sich darstellen als: $ \models F \rightarrow\ \vdash_{ark} F\; $

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 08.02.2003
Aufgaben-Kategorie AL - ResolutionAufgaben-Kategorie AL - Interpretationen und Modelle