Задачи SAT и 3-SAT

Допустим, имеется множество X из n булевых переменных x1, …, xn; каждая переменная может принимать значение 0 или 1 (эквиваленты false и true).

Литералом по X называется одна из переменных xi или ее отрицание. Наконец, условием называется обычная дизъюнкция литералов. (Еще раз: все). Мы говорим, что условие имеет длину , если оно содержит литералов.

А теперь дадим формальное определение присваиванию значений, удовлетворяющих набору условий. Логическим присваиванием для X называется присваивание значения 0 или 1 каждому xi; другими словами, это функция ν : X → {0,1}.

Присваивание v неявно задает  значение истинности, противоположное xi. Присваивание выполняет условие C, если после него C дает результат 1 по условиям булевой логики; это эквивалентно требованию о том, чтобы по крайней мере один из литералов в C имел значение 1.

Присваивание выполняет совокупность условий C1, …, Ck, если в результате его все Ci дают результат 1; иначе говоря, если в результате его конъюнкция C1 ҍ C2 ҍ … ҍ Ck дает результат 1. В этом случае v называется выполняющим присваиванием в отношении , а набор условий  называется выполнимым.

Рассмотрим простой пример. Допустим, имеются три условия:

Логическое присваивание ν, которое задает всем трем переменным значение 1, не является выполняющим, потому что с ним не выполняется второе из перечисленных условий; с другой стороны, присваивание ν‘, которое задает всем переменным значение 0, является выполняющим.

Теперь можно привести формулировку задачи выполнимости, также обозначаемой SAT:

Для заданного множества условий C1, ..., Ck по множеству переменных

X = {x1, …, xn} существует ли выполняющее логическое присваивание?