Специальные формы КНФ — различия между версиями
VVolochay (обсуждение | вклад) |
VVolochay (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[КНФ | + | Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций#Конъюнктивная нормальная форма (КНФ) |конъюнктивной нормальной форме]],т.е имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов: |
Версия 08:57, 15 октября 2010
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в конъюнктивной нормальной форме,т.е имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов:
КНФ в форме Крома
| Определение: |
| Конъюнктивной нормальной формой(КНФ) в форме Крома - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию нескольких литералов,количество которых не превышает двух. |
Пример:
КНФ в форме Хорна
| Определение: |
| Конъюнктивной нормальной формой(КНФ) в форме Хорна - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию литералов,в которой присутствует не более одного неотрицательного литерала. |
Пример:
Каждая скобка представляет собой дизъюнкт Хорна.
Любую формулу можно представить в виде КНФ в форме Хорна.Для этого любую формулу необходимо преобразовать в конъюнкцию элементарных дизъюнкций и далее каждую дизъюнкцию представить в форме дизьюнкта Хорна.
