Komplette Resorierungsregel für 1-in-K SAT

Question

In CNF SAT, jede Klausel (A oder B oder C oder ...) muss mindestens ein echte Literal enthalten.Die Auflösungsregel gilt für Paare von Klauseln, die genau ein entgegengesetztes Literal haben.

(a oder b oder c) und (! A oder D oder E)=> (B oder C oder D oder E)

Ich sage, dass diese Regel abgeschlossen ist, in dem Sinne, dass, wenn eine Formel unzufrieden ist, dass ich es beweisen kann, indem ich die Regel ausführlich (auf harten Instanzen, einer exponentiellen Menge an Zeiten) anwenden kann, bis eine leere Klausel erzeugt wird.Wenn eine Formel eine einzigartige Lösung hat, kann ich die Regel anwenden, bis jede Anteilsklausel erzeugt wird.

1-in-k SAT ist eine NP-vollständige Variante, in der genau eine Variable pro Klausel (A, B, C, ....)= 1 trifft.Angesichts eines Klauselpaares mit einem gegenüberliegenden Literal und einem gemeinsamen Literal kann ich auch einen dritten produzieren:

(a, b, c)= 1 und (! a, d, e)= 1=> (b, c, d, e)= 1

Frage : ist diese Regel für unzufriedene und einzigartig befriedigende 1-in-K-Formeln?

Answer 1

Sie behandeln die Auflösung, als wäre es eine rein syntaktische Regel.Es funktioniert so mit traditionellen CNF-Klauseln, da dies mit der zugrunde liegenden Regelungsregel entspricht.Eine CNF-Klausel mit der zusätzlichen Beschränkung von nur einem Literal, der zutreffend ist, entspricht jedoch nicht mehr, was die Auflösungsregel gültig anwendbar ist.

der boolesche Ausdruck $ (a \ lor b) \ land (\ lnot {a} \ ln \ lnot {b}) \ land (\ lnot {a} \ lor B) $ ist nicht zufriedenstellbar als 1-in-k-sat-SAT- -formel, aber naiv Anwenden der Auflösungsregel erzeugt $ a= false, B= TRUE$ als (falsche) Lösung.