Полное разрешение правило для 1-in-k SAT

Question

в SAT CNF, каждая оговорка (A или B или C или ...) должна содержать хотя бы один истинный буквальный.Правило разрешения распространяется на пару пунктов, которые имеют ровно один противоположный буквальный.

(a или b или c) и (! a или d или e)=> (b или c или d или e)

Я говорю, что это правило полное, в том смысле, что если формула неудовлетворяема, я могу доказать это, нанесение правила, исчерпывающе (на жесткие экземпляры, экспоненциальное количество времени) до получения одного пустого пункта.Если формула имеет уникальное решение, я могу применить правило, пока не будет производиться каждый пункт.

1-in-k S S SAT - это вариант NP-полный, где ровно одна вариабельная зависимость от предложения (A, B, C, ....)= 1 является true.Учитывая пару пункта с одним противоположным буквалом, и нет общего буквального литерала, я также могу изготовить третий:

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

Вопрос : это правило для неудовлетворяемого и уникально удовлетворяемого 1-in k формул?

Answer 1

Вы лечите разрешение, как если бы это было чисто синтаксическое правило.Это работает таким образом с традиционными пунктами CNF, потому что это соответствует базовому правилу вывода.Но пункт CNF с добавленным ограничением только одного буквального разрешенного для того, чтобы быть правдой, больше не соответствует тому, что правило разрешения может быть применено к.

Логическое выражение $ (a \ lor b) \ land (\ lnot {a} \ lor \ lnot {b}) \ loor (\ lnot {a} \ lor b) $ неудовлетворен как 1-in-k-sat формула, но наивно применяя правило разрешения, производит $ a= false, b= true$ как (неправильное) решение.