Logik:Klausuren/07.02.2004/1.2 Aufgabe

1. Aufgabenstellung

Gegeben sei die ausseagenlogische Formel $ F = ((p \rightarrow q) \or (\neg (r \rightarrow q) \or (p \and \neg r))) $

a) Beweisen Sie mittels Resolution die Allgemeingültigkeit von $ F\; $.

b) Wie ersetzen in $ F\; $ die aussagenlogische Variable $ r\; $ durch eine beliebige unerfüllbare aussagenlogische Formel $ G\; $. Ist die daraus resultierende Formel $ F[r/ G]\; $ ebenfalls noch eine Tautologie? Beweisen Sie Ihre Behauptung.

2. Lösung

a)

Formel negieren und umformen in Klauselform:

$ \langle [ \neg ((p \rightarrow q) \or (\neg (r \rightarrow q) \or (p \and \neg r))) ]\rangle $

$ \langle[ \neg ((p \rightarrow q)], [\neg (\neg (r \rightarrow q) \or (p \and \neg r)) ]\rangle $

$ \langle[p], [\neg q], [\neg (\neg (r \rightarrow q))], [\neg (p \and \neg r) ]\rangle $

$ \langle[p], [\neg q], [\neg r, q], [\neg p, r]\rangle $

Resolution:

1 $ [p]\; $
2 $ [\neg q] $
3 $ [\neg r, q] $
4 $ [\neg p, r] $
____________
5 $ [r]\; $ res(1,4)
6 $ [\neg r] $ res(2,3)
7 $ []\; $res(5,6)

b)

• Ersetzen von $ r\; $ durch $ G\; $ in Klauselform, Ergebnis: $ \langle[p], [\neg q], [\neg G, q], [\neg p, G]\rangle $.
• da $ G\; $ unerfüllbar, $ G^I = f\; $ für alle Interpretationen $ I\; $
• nach resolvieren mit $ G\; $ und $ \neg G\; $ (bzw. über 3. und 4. Klausel): $ \langle[p], [\neg q], [q], [\neg p]\rangle $
• resolvieren über $ p\; $ und $ \neg p\; $: $ []\; $
• Formel ist immer noch unerfüllbar
• Ja, $ F[r/ G]\; $ ist noch eine Tautologie.

4. Alternativen/Diskussion/Hinweise etc.

Beweis über semantische Aquivalenzen und die Definition der Wahrheitsfunktionen:

Da $ r\; $ unerfüllbar: $ r^I = f\; $

$ ((p^I \rightarrow * q^I) \or * (\neg * (r^I \rightarrow * q^I) \or * (p^I \and * \neg * r^I))) $

$ \equiv ((p^I \rightarrow * q^I) \or * (\neg * (f \rightarrow * q^I) \or * (p^I \and * \neg * f))) $

$ \equiv ((p^I \rightarrow * q^I) \or * (\neg * w \or * (p^I \and * w))) $

$ \equiv ((p^I \rightarrow * q^I) \or * (\or * p^I)) $

$ \equiv ((\neg * p^ \or * q^I) \or * p^I) $

$ \equiv ((q^I \or * \neg * p^I) \or * p^I) $

$ \equiv (q^I \or * (\neg * p^I \or * p^I)) $

$ \equiv (q^I \or * w) $

$ \equiv w $

Also $ F[r/ G]\; $ Tautologie.

PS: Eine Wahrheitswertetabelle über alle 4 möglichen Interpretationen mit G=f bzw -G=w wäre sicherlich auch ok gewesen.

---

zur Klausur 07.02.2004
Aufgaben-Kategorie AL - Resolution