Рассмотрим формулу 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
Для любой отличной от тождественно
истинной формулы алгебры высказываний существует и единственное её
представление в виде СКНФ.