2014-02-12
848
Дизъюнктивная (конъюнктивная) нормальная форма - это дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отрицаний, входящих в данный член не более одного раза.
Функция приводится к нормальной форме следующим путем: 1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным; 2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций); 3) полученное выражение упрощается и соответствии с тождествами 
и 
(
и 
).
Пример:
- дизъюнктивная нормальная форма (ДНФ).
- конъюнктивная нормальная форма (КНФ).
Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называют минитермами (макстермами) k- го ранга. Так, в приведенных выше формах ху - минитерм второго ранга, хуг - минитерм третьего ранга, а 
- макстерм второго ранга.
|
|
|
Если исходная формула содержит другие операции, то они предварительно выражаются через дизъюнкцию, конъюнкцию и отрицание, например:
Пример:
