Разложение булевых функций по переменным

Введем понятие степени булевой переменной x

Рассмотрим функцию вида f(x₁,x₂,x₃)

Выделим переменную x₁ и рассмотрим функцию f относительно нее.

Все множество наборов <a₁, a₂, a₃> таблицы истинности разбивается на два подмножества, в каждом из которых по четыре набора <0, a₂, a₃> и <1, a₂, a₃>.

Тогда функцию f(x₁,x₂,x₃) можно представить в виде дизъюнкции двух функций от двух переменных и эта формула будет иметь вид:

Рассмотрим следующие формулы:

Левая часть первой формулы эквивалентна правой, поскольку для x₁=0 и в соответствии с операцией конъюнкции. Аналогично можно показать справедливость второй формулы. Таким образом, поставив эти формулы в предыдущую дизъюнкцию, получим:

(*1)

Это выражение называется разложением функции f(x₁,x₂,x₃) по переменной x₁.

Теперь аналогично можно разложить функции f(0,x₂,x₃) и f(1,x₂,x₃) по переменной x₂. Получим

(*2)

Подставляя эти формулы в предыдущие получим

Внесем в соответствии с дистрибутивностью операции & переменную x₁ и ее инверсию в скобки, получим

Далее разложим f(x₁,x₂,x₃) по переменной x₃. Получим

(*3)

В общем виде для функции f(x₁,x₂,..,x_n) от n переменных разложение по m переменным (m£n) имеет вид

, (*4)

где дизъюнкция берется по всем 2^m наборам переменных x₁,x₂,..,x_m.

Рассмотрим разложение (*4) при крайнем случае, когда m=n. (см. пример (*3)).

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

Проделаем все это для примера (*3).

После удаления из (*3) конъюнкций с нулевыми значениями функции f на заданных наборах, получим:

Так как в соответствии с таблицей истинности

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

то из конъюнкций уберем сомножители функций, после чего получим:

Это и есть совершенная дизъюнктивная нормальная форма булевой функции f.

Лемма. Любая булева функция (кроме константы "0") имеет СДНФ, при том только одну.

Аналогично можно ввести конъюнктивную форму,

Построение СДНФ для функции, заданной таблицей

Данное следствие носит конструктивный характер, т.к. оно по таблице функции позволяет построить формулу, являющуюся СДНФ (если ).
СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f; каждому “единичному” набору (d ₁,…,d _n), т.е. набору, на котором значение функции равно 1, соответствует конъюнкция всех переменных, в которой x_i взято с отрицанием, если d i=0, и без отрицания, если d _i=1.

Пример 5.1. Записать СДНФ для функции x₁ ® x₂.

x1 x2	x1 ® x2	Основная элементарная конъюнкция
0 0	1
0 1	1	x2
1 0	0
1 1	1	x1x2

.