1.8.  Нормальные и совершенные формы

 

Рассмотрим формулу n переменных А(а1, а2, …, аn).

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

Пример 1. xyz, Øxy – элементарные конъюнкции;

ØxÚyÚz, yÚz, xÚØz – элементарные дизъюнкции.

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

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

Для любой формулы алгебры высказываний путем равносильных преобразований можно получить её КНФ или ДНФ, причем не единственную.

Определение 4. Если в дизъюнктивной нормальной форме элементарные конъюнкции содержат каждую переменную либо её отрицание, то формула называется совершенной дизъюнктивной нормальной формой (СДНФ).

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

Пример 2. А(x,y,z)= xyzÚØxy – дизъюнктивная нормальная формa;

B(x,y,z)= (ØxÚyÚz)( yÚz)( xÚØz) – конъюнктивная нормальная форма;

C(x,y,z)= xyzÚØxyz – совершенная дизъюнктивная нормальная форма;

D(x,y,z)= (ØxÚyÚz)( xÚyÚz)( xÚyÚØz) – совершенная конъюнктивная нормальная форма.

Теорема 7.1 Для любой формулы алгебры высказываний существуют равносильные ей ДНФ и КНФ.

Теорема 7.2 Для любой отличной от тождественно ложной формулы алгебры высказываний существует и единственное её представление в виде СДНФ.

Теорема 7.3 Для любой отличной от тождественно истинной формулы алгебры высказываний существует и единственное её представление в виде СКНФ.