Тождественные преобразования

Геометрическое представление. Область определения булевых функций от п переменных у = f (х₁, x₂,..., x_n) можно рассматривать как совокупность n -мерных векторов (слов длины n), компонентами которых являются буквы 0 и 1 двоичного алфавита. При п = 3 каждый вектор представляется вершиной единичного куба в трехмерном пространстве (рис. 20). В общем случае совокупность векторов (х₁, x₂,..., x_n) отображается на множество вершин n -мерного куба.Всетакие вершины образуют логическое пространство.

Булева функция отображается на n -мерном кубе путем выделения вершин, соответствующих векторам (х₁, x₂,..., x_n) на которых булева функция у = f (х₁, x₂,..., x_n) принимает значения 1. Обычно такие вершины отмечают жирными точками. Так, на рис. 20 отображена функция в соответствии с таблицей из (8).

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

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

Пример: (дизъюнктивная нормальная форма); (конъюнктивная нормальная форма).

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

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

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

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

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

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

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

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

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

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

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

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

.

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