1302
правки
Изменения
→КНФ в форме Хорна
= КНФ в форме Хорна =
{{Определение
|definition=
<tex> (\overline x_1 \vee \overline x_2 \vee ... \vee \overline x_n ) \wedge (x_1 \vee \overline x_2 \vee ... \vee \overline x_n)\wedge ...</tex>
Каждая скобка представляет собой [http://ru.wikipedia.org/wiki/Дизъюнкт_Хорна''Дизъюнкт Хорна''].
*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <tex>F</tex> можно задать в форме Хорна <tex> \iff </tex> когда выполнено следующее следствие :
<tex> F(x_1, ..., x_n)=F(y_1, ..., y_n)=1 \Rightarrow F(x_1 \wedge y_1, x_2 \wedge y_2, ..., x_n \wedge y_n)</tex>
==См.также==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]
