Специальные формы КНФ

Материал из Викиконспекты
Перейти к: навигация, поиск

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в конъюнктивной нормальной форме,т.е имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов:


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

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


Пример:

[math](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... [/math]


КНФ в форме Хорна

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


Пример:

[math] (\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 ...[/math]


Каждая скобка представляет собой дизъюнкт Хорна.

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