Нормальные формы. Совершенные нормальные формы.

Пусть - система высказывательных переменных.

Дизъюнктивная нормальная форма называется совершенной (СДНФ), если она представляет дизъюнкцию полных различных элементарных конъюнкций.

Пример 3. - СДНФ.

- не является СДНФ.

Элементарной дизъюнкцией (конъюнкцией) называется дизъюнкция (конъюнкция) некоторых переменных этой системы или их отрицания.

Дизъюнктивной нормальной формой (ДНФ) называется формула, являющаяся дизъюнкцией некоторого числа элементарных конъюнкций.

Теорема. ДНФ является тождественно ложной тогда и только тогда, когда каждая её составляющая элементарной конъюнкции содержит некоторую высказывательную переменную и её . Элементарная конъюнкция (дизъюнкция) называется полной, если она содержит все переменные данной системы и при том только по одному разу.

Алгоритм построения СДНФ.1) Приводим формулу к ДНФ. 2) Избавляемся от повторяемости переменных 3) Избавляемся от повторяющихся элементарных конъюнкций. 4) Дополняем элементарные конъюнкции недостающими высказывательными переменными.

- СДНФ.Т еорема. Теорема. Для любой не тождественно ложной (истинной) формулы существует эквивалентная ей СДНФ (СКНФ).

Док-во явл-ся конструктивным.

Пусть - данная логическая формула .

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

2. Рассмотрим каждую из э.к. (э.д.), которые полными не явл-ся.

- в э.к. (э.д.) присутствует конъюнкция (дизъюнкция) двух одинаковых высказывательных переменных. В этом случае для упрощения применяем один из законов:

; ; (; ; )

Выполнив одно из этих преобразований, мы избавимся от повторяющихся переменных. В случае пробразования () вся э.к. (э.д.) будет равна 0 (1), поэтому эту э.к. (э.д.) можно исключить из рассматрения.

- в э.к. (э.д.) () отсутствуют некоторые высказывательные переменные

- недостающие переменные.

Для получения полной э.к. (э.д.) к конъюнкции (дизъюнкции ) добавим конструкцию

После этого применяя дистрибутивный закон, раскрываем все скобки. При этом получим дизъюнкцию э.к. (конъюнкцию э.д.). Причем все полученные э.к. (э.д.) будут полными и различными. Т.о.получим дизъюнкцию полных конъюнкций (конъюнкцию полных дизъюнкций).

1) Если в полученной дизъюнкции (конъюнкции) имеются повторяющиеся полные конъюнкции (дизъюнкции), то применяем закон

.

После этого получаем СДНФ (СКНФ).