Изменения

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций#Конъюнктивная нормальная форма (КНФ) |конъюнктивной нормальной форме]],т.е имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов:

== КНФ в форме Крома ==

'''Конъюнктивной нормальной формой(КНФ) в форме Крома''' - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию нескольких литералов,количество которых не превышает двух.}}

'''Пример:'''

 *Функцию <tex>F</tex> можно задать в форме Крома, если выполнено следствие(верно и обратное):  <tex> F(x_1, ..., x_n)=F(y_1, ..., y_n)=F(z_1, ..., z_n)= 1 \Rightarrow F(<x_1, y_1, z_1>, <x_2, y_2, z_2>, ..., <x_n, y_n, z_n >) </tex>  = КНФ в форме Хорна ==

'''Конъюнктивной нормальной формой(КНФ) в форме Хорна''' - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию литералов,в которой присутствует не более одного неотрицательного литерала.}}

Каждая скобка представляет собой [http://ru.wikipedia.org/wiki/Дизъюнкт_Хорна''Дизъюнкт Хорна'дизъюнкт ']. Любую формулу можно представить в виде КНФ в форме Хорна. Для этого формулу необходимо преобразовать в конъюнкцию элементарных дизъюнкций и далее каждую дизъюнкцию представить в форме дизьюнкта Хорна. '''Утверждения:''' *Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.  *Функцию <tex>F</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>