144
правки
Изменения
→КНФ в форме Крома
Пример:
<math>(A \or \neg B) \and (\neg A \or C ) \and (\neg C \or B ) \and (\neg A \or \neg C ) \cdots </math>
В такой форме можно представить задачу 2-SAT (2-satisfiability,задача распределения значений булевым переменным таким образом, чтобы они удовлетворяли всем наложенным ограничениям).Алгоритм для решения 2-SAT может быть применим во всех задачах, где есть набор величин, каждая из которых может принимать 2 возможных значения, и есть связи между этими величинами(к примеру,такие как нахождение такого расположения меток на диаграмме, при котором никакие две не пересекаются и т.д.).
