144
правки
Изменения
→КНФ в форме Крома
== КНФ в форме Крома ==
{{Определение|definition='''Конъюнктивной нормальной формой(КНФ) в форме Крома''' - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию нескольких литералов,количество которых не превышает 2х. Эта же такая форма называется 2-CNF (2-conjunctive normal form).}}
Пример:
В такой форме можно представить задачу 2-SAT (2-satisfiability,задача распределения значений булевым переменным таким образом, чтобы они удовлетворяли всем наложенным ограничениям).Алгоритм для решения 2-SAT может быть применим во всех задачах, где есть набор величин, каждая из которых может принимать 2 возможных значения, и есть связи между этими величинами(к примеру,такие как нахождение такого расположения меток на диаграмме, при котором никакие две не пересекаются и т.д.).
== КНФ в форме Хорна ==
