Что является примером неудовлетворительной формулы 3-CNF?

15

Я пытаюсь обернуть голову вокруг доказательства полноты NP, которое, кажется, вращается вокруг SAT / 3CNF-SAT.

Возможно, это поздний час, но я боюсь, что не могу придумать формулу 3CNF, которая не может быть удовлетворена (возможно, я упускаю что-то очевидное).

Можете ли вы привести пример такой формулы?

logic satisfiability 3-sat user11171
источник

Ответы:

29

Технически, вы можете написать в 3-CNF как ( x ∨ x ∨ x ) ∧ ( ¬ x ∨ ¬ x ∨ ¬ x ) , но вам, вероятно, нужен «реальный» пример.x∧¬x(x∨x∨x)∧(¬x∨¬x∨¬x)

В этом случае для формулы 3CNF необходимо как минимум 3 переменные. Поскольку каждое предложение исключает ровно одно присваивание, это означает, что вам нужно по крайней мере предложений, чтобы иметь невыполнимую формулу. Действительно, самый простой из них:23=8

Нетрудно видеть, что эта формула не является удовлетворительной.

(x∨y∨z)∧(x∨y∨¬z)∧(x∨¬y∨z)∧(x∨¬y∨¬z)∧(¬x∨y∨z)∧(¬Икс∨Y∨¬Z)∧(¬Икс∨¬Y∨Z)∧(¬Икс∨¬Y∨¬Z)
Shaull
источник
возможно, я здесь довольно наивен, но почему вы не можете выполнить серию сравнений, чтобы определить, есть ли наборов неэквивалентных выражений? - v - количество уникальных переменных. Если я посчитал правильно, то есть только n ( n - 1 )2vvN(N-1)2
@BenCrossley - не уверен, что вы имеете в виду. Можете привести пример?
Shaull
8

Если вы хотите более сложные примеры таких формул, взгляните на некоторые тестовые задачи SATLIB . ToughSAT также хороший инструмент для создания экземпляров 3-SAT; легко построить как удовлетворяющие, так и неудовлетворительные экземпляры.

Юхо
источник