Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций)

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

Пример

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru ­­– дизъюнктивная нормальная форма

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru ­­– конъюнктивная нормальная форма

Формулы приводятся к нормальной форме следующим путем:

1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным;

2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций);

3) полученные выражения упрощаются в соответствии с тождествами Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru ( Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru )

Пример

Привести к дизъюнктивной и конъюнктивной нормальным формам функцию Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

Решение

В соответствии с законом де Моргана преобразуем Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

На основе законов дистрибутивности раскроем скобки:

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

В соответствии с законом идемпотентности Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru . Откуда

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

Полученное выражение является дизъюнктивной нормальной формой.

Аналогичным образом представим заданную функцию в конъюнктивной нормальной форме:

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru

Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

Конъюнктивная нормальная форма получена.

Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называются минитермами (макситермами) k-го ранга. Так, например, Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru – минитерм третьего ранга, а Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru – макситерм второго ранга.

Совершенной дизъюнктивной (конъюнктивной) нормальной формой называется дизъюнктивная (конъюнктивная) нормальная форма, каждый минитерм (макситерм) которой содержит все переменные (либо в прямом, либо в инверсном виде).

Например, минитерм Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru функции четырех переменных (х1, х2, х3, х4) в совершенной дизъюнктивной нормальной форме будет представлен дизъюнкцией двух минитермов: Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru .

Вопросы и задания

6.1. Может ли одной и той же дизъюнктивной нормальной форме соответствовать несколько различных совершенных дизъюнктивных нормальных форм?

6.2. Может ли одной и той же совершенной дизъюнктивной нормальной форме соответствовать несколько различных дизъюнктивных нормальных форм?

6.3. Представьте функцию трех переменных Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций) - student2.ru

а) в дизъюнктивной нормальной форме;

б) в совершенной дизъюнктивной нормальной форме;

в) в конъюнктивной нормальной форме;

г) в совершенной конъюнктивной нормальной форме.

6.4. Схема, представленная на рис.4.4 соответствует дизъюнктивной нормальной форме. Каждая ветвь цепи соответствует одному минитерму. Какая цепь соответствует макситерму? Каков общий вид схемы, соответствующей конъюнктивной нормальной форме?

Наши рекомендации