Конституенты и представление функций. Совершенные нормальные формы

Совершенные нормальные формы

Нормальные формы

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

Функция приводится к нормальной форме следующим путем: 1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным; 2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций); 3) полученное выражение упрощается и соответствии с тождествами и (и).

Пример:

- дизъюнктивная нормальная форма (ДНФ).

- конъюнктивная нормальная форма (КНФ).

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

Если исходная формула содержит другие операции, то они предварительно выражаются через дизъюнкцию, конъюнкцию и отри­цание, например:

Пример:

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

Можно показать, что любая булева функция, не являющаяся тождественным нулем (единицей), имеет одну и только одну совер­шенную дизъюнктивную (конъюнктивную) нормальную форму. Если какой-либо член j дизъюнктивной (конъюнктивной) нормаль­ной формы не содержит переменной х, то она вводится тождест­венным преобразованием
j = j() = j х Ú j (соответ­ственно j = j Ú =(j Ú х)(j Ú)). В силу тождеств j Ú j = j и jj = j одинаковые члены, если они появляются, заменяются одним таким членом.

Продолжая второй пример, приведем данную функцию к совершенной дизъюнктивной нормальной форме:

Приведение к совершенной конъюнктивной нормальной форме иллюстрируется следующим при­мером:

Для совокупности переменных выражение называют конституентой единицы, а выражение - конституентой нуля ( означает либо, либо ). Данная конституента единицы (нуля) обращается в единицу (нуль) только при одном соответствую­щем ей наборе значений переменных, который получается, если все переменные принять равными единице (нулю), а их отрицания - нулю (единице). Например, конституенте единицы соот­ветствует набор (1011), а конституенте нуля - набор (1001).

Так как совершенная дизъюнктивная (конъюнктивная) нор­мальная форма является дизъюнкцией (конъюнкцией) конституент единицы (нуля), то можно утверждать, что представляемая ею булева функция f() обращается в единицу (нуль) только при наборах значений переменных, соответствующих этим конституентам. На остальных наборах эта функция обращается в нуль (единицу).

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

Пример. Функции, заданной таблицей

соответствуют совершенные нормальные формы:

Полученные выражения можно преобразовать к другому видуна основании свойств булевой алгебры.