Czy można przetłumaczyć wzór B logiczny na równoważną kombinację klauzul Horna? Artykuł w Wikipedii na temat HornSAT wydaje się sugerować, że tak, ale nie byłem w stanie ścigać żadnego odniesienia.
Zauważ, że nie mam na myśli „w czasie wielomianowym”, ale raczej „w ogóle”.
reference-request
lo.logic
sat
Evgenij Thorstensen
źródło
źródło
Odpowiedzi:
Nie. Klauzule Rogu dopuszczają najmniej modeli Herbranda, których nie mają rozróżnienia literałów pozytywnych. Por. Lloyd, 1987, Foundations of Logic Programming .
Najmniejsze modele Herbrand mają tę właściwość, że znajdują się na skrzyżowaniu wszystkich satysfakcji. Modelami Herbrand dla są , który nie zawiera jego przecięcia, tak jak mówi arnab, jest przykładem wzoru, którego nie można wyrazić jako koniunkcję klauzul Horn.{ { a } , { b } , { a , b } } ( a ∨ b(a∨b) {{a},{b},{a,b}} (a∨b)
Niepoprawna odpowiedź nadpisana
źródło
Zgodność można osiągnąć w następujący sposób (redukcja z 2SAT do HornSAT). W ten sposób można również zredukować do formuły Horn. Dzięki Joshua Gorchow za zwrócenie uwagi na tę redukcję.(p∨q)
Dane wejściowe: wzór 2-SAT z klauzulami , ..., na zmiennych , ..., .ϕ C1 Ck x1 xn
Skonstruuj formułę Horn w następujący sposób:Q
Nie będzie 4 ( wybrać ) nowych zmiennych, po jednym dla każdej możliwej ewentualnej 2-cnf klauzuli o zmiennych o co najwyżej 2 literałów ( nie tylko te klauzul ) - jest to łącznie z klauzulami jednostkowymi i pustymi. Nowa zmienna odpowiadająca klauzuli będzie oznaczona przez .× n 2 +2n+1 x Ci ϕ D zD
4 ( wybierz ) wynika z faktu, że każda para daje początek 4 klauzulom 2-cnf. wynika z faktu, że każdy może utworzyć 2 klauzule jednostkowych. I w końcu „jeden” pochodzi z pustej klauzuli. Zatem całkowita liczba możliwych klauzul 2-cnf wynosi 4 ( wybierz ) .n 2 ( x i , x j ) 2 n x i = × n 2× n 2 (xi, xj) 2n xi = × n 2 +2n+1
Jeśli klauzula 2-cnf wynika z dwóch innych klauzul 2-cnf i jednym krokiem rozdzielczości, to dodajemy klauzulę Horn do ... Ponownie, robimy to dla Wszystkie ewentualne 2-CNF klauzule - wszystkie 4 ( wybrać ) z nich - nie tylko .F D E (zD∧zE→zF) Q × n 2 +2n+1 Ci
Następnie dodajemy klauzul jednostka do , dla każdej klauzuli występującego na wejściu ... Na koniec dodamy klauzulę jednostkową do .zCi Q Ci ϕ (¬zempty) Q
Formuła klaksonu jest teraz ukończona. Zauważ, że zmienne użyte w są całkowicie różne od zmiennych używanych w .Q Q ϕ
źródło
Nie sądzę, żeby to było możliwe. Na przykład nie ma sposobu, aby napisać jako połączenie klauzul tubowych, ponieważ zakazuje tylko pojedynczego przypisania prawdy, a mianowicie 0011. Każda klauzula tubowa z mniej niż 4 literałami zakazałoby więcej niż 1 przypisania prawdy, a klauzule rogowe z 4 literałami mogą zakazać przypisania prawdy tylko z jednym 0.ϕϕ=(X1∨X2∨¬X3∨¬X4) ϕ
Edycja: oops nie zauważył, że na to już odpowiedziano
źródło