0 Daumen
499 Aufrufe

Hallo!

Die Aufgabe lautet:

Gegeben ist die Klauselmenge $$ K\quad =\quad \left\{ \left\{ A,B,C \right\} ,\left\{ \neg A,B,\neg C \right\} ,\left\{ \neg A,B,D \right\} ,\left\{ \neg A,\neg C,D \right\} ,\left\{ \neg B,C \right\}  \right\} $$ Bestimmen Sie, ob $$ K\quad \models \quad \neg A $$ gilt, unter Verwendung des Davis-Putnam-Verfahrens.


Leider weiß ich überhaupt nicht, wie ich bei dieser Aufgabe vorgehen soll. Wie funktioniert das Davis-Putnam-Verfahren bezüglich dieser Aufgabe? Im Internet finde ich leider keine guten ausführlichen Erklärungen oder Beispiele. So weit ich das verstehe, kann man mit dem Verfahren Formelmengen reduzieren und damit entscheiden, ob sie erfüllbar oder unerfüllbar sind. (Wie genau?)

Funktioniert das Verfahren ähnlich wie das Resolutionsverfahren? Nehme ich {A} einfach mit zu der Klauselmenge und schaue, ob das unerfüllbar ist? Muss ich dann nach diesem A reduzieren? Oder ist das beliebig?
Das wäre ja dann $$ K\quad =\quad \left\{ \left\{ A,B,C \right\} ,\left\{ \neg A,B,\neg C \right\} ,\left\{ \neg A,B,D \right\} ,\left\{ \neg A,\neg C,D \right\} ,\left\{ \neg B,C \right\} ,\left\{ A \right\}  \right\} $$ (nach meinem Verständnis) reduziert um A: $$ K\quad =\quad \left\{ \left\{ B,\neg C \right\} ,\left\{ B,D \right\} ,\left\{ \neg C,D \right\} ,\left\{ \neg B,C \right\}  \right\} $$
Dann bleibt ja aber was übrig, was mache ich dann damit? Nochmals reduzieren?
Ich weiß leider wirklich überhaupt nicht, ob das der richtige Weg ist. :(
Ich wäre sehr dankbar über jede Hilfe!

von

Jetzt könnte man das B wegnehmen

K\quad =\quad \left\{ \left\{ B,\neg C \right\} ,\left\{ B,D \right\} ,\left\{ \neg C,D \right\} ,\left\{ \neg B,C \right\}  \right\}

neu ordnen

K = {{B,-C}, {-B,C}, {B,D}, {-C,D}}

K = {{-C,C}, {B,D}, {-C,D}}

dann (ich kopiere und färbe neu):

K = {{B,-C}, {-B,C}, {B,D}, {-C,D}}   
K = {{C,-C}, {B,D}, {-C,D}}

nun:  
K = {{-C,D}, {C,D}}

dann

K = {{D,D}} = {D}

Komme gerade nicht auf ◊.

Vielleicht soll es ja gar nicht aufgehen, sondern zu einem Widerspruch führen?

Versuch nach dem Schema hier: https://books.google.ch/books?id=FF55CgAAQBAJ&pg=PA106&lpg=PA106&dq=resolutionsbaum&source=bl&ots=B01LBHIGO_&sig=kBTW5aAkeN6y1YaXBimzo7LxjeQ&hl=sv&sa=X&ved=0ahUKEwjq67iBt7rbAhUIPFAKHRXwCUIQ6AEIWjAJ#v=onepage&q=resolutionsbaum&f=false

Wie hier:

https://www.stacklounge.de/2365/resolution-wie-anwenden

Wenn du weisst, wie es richtig ist, bitte angeben.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community