1302
правки
Изменения
Нет описания правки
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов:.
== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма(КНФ) в форме Крома''' {{- --}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}
'''Пример :'''
*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Крома можно удовлетворить(т.е КНФ в форме Крома не является тождественным <tex>0</tex>).
*Функцию <tex>F</tex> можно задать в форме Крома <tex> \iff </tex> выполнено следующее следствие:
{{Определение
|definition=
'''Конъюнктивная нормальная форма(КНФ) в форме Хорна''' {{- --}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}
'''Пример:'''
