Logik:Klausuren/07.02.2004/1.8 Aufgabe

1. Aufgabenstellung

Die nachfolgend beschriebenen Regeln sind unter dem Namen "Einerklauselregel" bekannt: Sei $ L\; $ eine beliebige aussagenlogische Variable. Wenn in einer Formel in Klauselform eine Klausel der Form $ [\neg L] $ vorkommt, dann streiche jedes Vorkommen von $ L\; $ in der Formel. Wenn in einer Formel in Klauselform eine Klausel der Form $ [L]\; $ vorkommt, dann streiche jedes Vorkommen von $ \neg L $ in der Formel.

a) Wenden Sie auf die in Klauselform vorliegende Formel $ F = \langle [p], [q, r], [\neg p, \neg q], [\neg p, \neg r]\rangle $ so oft wie möglich die Einerklauselregel an.

b) Das Resultat der Anwendung einer Einerklauselregel auf $ F\; $ sei die Formel $ F^\prime $ . Beweisen Sie: Wenn $ F\; $ erfüllbar ist, dann ist $ F^\prime $ ebenfalls erfüllbar.

2. Lösung

a) Unterstrichen ist jeweils die ausgewählte Variable:

$ \langle [\underline{p}], [q, r], [\neg p, \neg q], [\neg p, \neg r]\rangle $
$ \langle [p], [q, r], [\underline{\neg q}], [\neg r]\rangle $
$ \langle [p], [r], [\neg q], [\underline{\neg r}]\rangle $
$ \langle [p], [], [\neg q], [\neg r]\rangle $

b)

Die Einerklauselregel ist eine Zusammenfassung von endlich vielen Resolutions-Schritten, d.h. es ergibt eine erfüllbare Resolutionsableitung. Durch Weglassen der ursprünglichen Klauseln entsteht eine Teilmenge der erfüllbaren Menge, die wiederum erfüllbar ist.

4. Alternativen/Diskussion/Hinweise etc.

b) Erfüllbarkeit gilt wenn es mindestens eine Interpretation I mit $ F^{I} = w $ und $ F^{'^{I}} = w $ gibt.

$ F = \langle [p], [\neg p, q]\rangle $

$ F^{'} = \langle [p], [q] \rangle $

$ F = (p \wedge (\neg p \vee q)) $

$ F^{'} = (p \wedge q) $

Interpretation I mit $ p^{I}=w, q^{I}=w : $

$ F^{I} = (p^{I} \wedge^{*} (\neg^{*} p^{I} \vee^{*} q^{I})) $

$ F^{I} = (w \wedge^{*} (\neg^{*} w \vee^{*} w)) $

$ F^{I} = (w \wedge^{*} w) $

$ F^{I} = w $

$ F^{'^{I}} = (p^{I} \wedge^{*} q^{I}) $

$ F^{'^{I}} = (w \wedge^{*} w) $

$ F^{'^{I}} = w $

$ F^{'^{I}} = w $ und $ F^{I} = w $

$ F $ und $ F^{'} $ sind erfüllbar.

w.z.b.w.

b)

F enthält keine Einerklausel: Aussage gilt.

F enthält Einerklauseln:

a) Anwendung auf $ [\neg L] $

• $ L^I $ muss f sein, da F sonst nicht erfüllbar
• es existiert eine Klausel der Form $ [L, Rest]\; $, wobei Rest beliebige nichtleere Sequenz von Literalen
• nach Anwendung der Regel wird aus dieser Klausel $ [Rest]\; $
• Klausel ist verallgemeinerte Disjunktion, also

$ (L^I \or * Rest^I) = (f \or * Rest^I) \equiv Rest^I $

• Es hat sich also nichts an der Erfüllbarkeit geändert.

b) Anwendung auf $ [L]\; $

• $ L^I $ muss w sein, da F sonst nicht erfüllbar
• es existiert eine Klausel der Form $ [\neg L, Rest]\; $, wobei Rest beliebige nichtleere Sequenz von Literalen
• nach Anwendung der Regel wird aus dieser Klausel $ [Rest]\; $
• Klausel ist verallgemeinerte Disjunktion, also

$ (\neg * L^I \or * Rest^I) \equiv (\neg * w \or * Rest^I) \equiv (f \or * Rest^I) \equiv Rest^I $

• Es hat sich also nichts an der Erfüllbarkeit geändert.
• Also gilt auch hier die Aussage.

---

zur Klausur 07.02.2004
Aufgaben-Kategorie AL - ResolutionAufgaben-Kategorie Sonstige