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

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

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

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

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

10.5. Проблема разрешимости

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

Ответ на этот вопрос можно получить, построив для данной формулы таблицу соответствия, что сводится по существу к опре­делению значений формулы при всевозможных наборах значении входящих в нее переменных. Если на всех наборах формула прини­мает значения только 0 или только 1, то она невыполнима.

При большом количестве переменных такой способ практически неосуществим из-за огромного числа возможных наборов значений переменных. Более удобный путь - приведение формулы к нор­мальной форме. Если в процессе такого приведения формула не обращается в тождественный 0 или 1, то это свидетельствует о ее выполнимости.

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

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

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

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

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

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

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