Naryxus
Grünschnabel
Dabei seit: 16.09.2010
Beiträge: 5
|
|
Formeln äquivalent zu Konjunktion von Hornklauseln |
|
Hallo,
wir sollen bei folgenden Formeln überprüfen, ob es eine äquivalente Form in Konjunktionenen von Hornklauseln gibt.
1.
(p -> (q | r)) & (p | s)
Dazu habe ich die folgende KNF:
(p | q | r | s) & (p | q | !r | s) & (p | !q | r | s) & (p | !q | !r | s) & (!p | q | r | s) & (!p | q | r | !s)
Diese lässt sich meines Erachtens nicht mehr weiter umformen, sodass daraus Hornklauseln entstehen.
2.
(p & q) <-> r
Mit der folgenden KNF:
(p | q | !r) & (p | !q | !r) & (!p | q | !r) & (!p | !q | r)
Das habe ich weiter umgeformt bis ich letztendlich auf folgende Form gekommen bin:
(p | !r) & (!p | q | !r) & (!p | !q | r)
Das heißt ich habe nun eine Hornklauselmenge. Aber trotzdem lässt sich hier nicht der Algorithmus zur Berechnung der minimalen Belegung anwenden, da ich kein alleinstehendes Literal habe.
Kann mir jemand sagen, ob meine Gedankengänge richtig sind?
Grüße, Naryxus
|
|