Ist es möglich, eine Boolesche Formel B in eine äquivalente Konjunktion von Horn-Klauseln zu übersetzen? Der Wikipedia-Artikel über HornSAT scheint zu implizieren, dass dies der Fall ist, aber ich konnte keine Referenz aufspüren.
Beachten Sie, dass ich nicht "in polynomialer Zeit" meine, sondern "überhaupt".
reference-request
lo.logic
sat
Evgenij Thorstensen
quelle
quelle
Antworten:
Nein. Konjunktionen von Horn-Klauseln lassen zumindest Herbrand-Modelle zu, was bei Disjunktionen von positiven Literalen nicht der Fall ist. Vgl. Lloyd, 1987, Grundlagen der Logikprogrammierung .
Least Herbrand-Modelle haben die Eigenschaft, dass sie sich an den Schnittpunkten aller Befriedigenden befinden. Die Herbrand-Modelle für sind { { a } , { b } , { a , b } } , die keine Schnittmenge enthalten, wie Arnab sagt, ( a ∨ b ) ist ein Beispiel für eine Formel das kann nicht als eine Konjunktion von Horn-Klauseln ausgedrückt werden.( a ∨ b ) { { a } , { b } , { a , b } } ( a ∨ b )
Falsche Antwort überschrieben
quelle
Die Erfüllbarkeit kann auf folgende Weise erreicht werden (Reduktion von 2SAT auf HornSAT). Auf diese Weise kann also auch zu einer Hornformel reduziert werden. Vielen Dank an Joshua Gorchow für diesen Hinweis.(p∨q)
quelle
Edit: oops hat nicht bemerkt, dass dies bereits beantwortet wurde
quelle