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

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

 

Пример

­­– дизъюнктивная нормальная форма

­­– конъюнктивная нормальная форма

 

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

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

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

3) полученные выражения упрощаются в соответствии с тождествами ()

 

Пример

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

Решение

В соответствии с законом де Моргана преобразуем .

.

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

.

В соответствии с законом идемпотентности . Откуда

.

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

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

.

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

 

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

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

Например, минитерм функции четырех переменных (х ₁, х ₂, х ₃, х ₄) в совершенной дизъюнктивной нормальной форме будет представлен дизъюнкцией двух минитермов: .

 

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

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

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

6.3. Представьте функцию трех переменных

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

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

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

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

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