ПРИМЕНЕНИЯ НОРМЛАЬНЫХ ФОРМ
Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т. е. имеет вид
Примеры элементарных конъюнкций:
Соединим эти конъюнкции знаками дизъюнкции и получим дизъюнктивную нормальную форму (ДНФ):
Дизъюнктивная нормальная форма называется совершенной, если в каждый конъюнкт (скобочку) входят все переменные из набора переменных. Приведённые выше дизъюнктивные нормальные формы являются также совершенными дизъюнктивными нормальными формами. Пример несовершенной, простой ДНФ:
Алгоритм приведения формулы алгебры высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме: <алгоритм записать дома>
|
, 
– элементарная конъюнкция.
. В левой части только 
, а следовательно, набор переменных не полный.
