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