<tex>(x_1\vee\overline x_2) \wedge (\overline x_1 \vee x_3 ) \wedge (\overline x_3 \vee x_2 ) \wedge (\overline x_1 \vee \overline x_2) \wedge... </tex>
'''Утверждения{{Утверждение|statement=Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Крома можно удовлетворить (т.е КНФ в форме Крома не является тождественно равной <tex>0</tex>).|proof=Данный алгоритм подробно описан в статье о выполнимости булевых формул, заданных в форме Крома:'''[[2SAT]].}}
*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Крома можно удовлетворить (т.е КНФ в форме Крома не является тождественно равной <tex>0</tex>).{{Утверждение Данный алгоритм подробно описан в статье о выполнимости булевых формул, заданных в форме Крома: [[2SAT]]. *|statement=Функцию <tex>F</tex> можно задать в форме Крома <tex> \iff </tex> выполнено следующее следствие: <tex> F(x_1, ..., x_n)=F(y_1, ..., y_n)=F(z_1, ..., z_n)=1 \Rightarrow</tex> <tex>F(\langle x_1, y_1, z_1 \rangle, \langle x_2, y_2, z_2 \rangle, ..., \langle x_n, y_n, z_n \rangle)</tex>}}
= КНФ в форме Хорна =
