§ 2. Свойства булевых функций

Одну и ту же булеву функцию можно представить в виде различных логических формул.

Пример. x | y =  = = (xy) 

Следовательно, множество всех формул можно разбить на классы эквивалентности таким образом, что все формулы, входящие в один класс, соответствуют одной и той же булевой функции; поэтому если функции, соответствующие некоторым формулам, равны, то сами эти формулы называют эквивалентными. Запись = означает, что формулы  и  эквивалентны.

Приведем список эквивалентностей (тождеств), характеризующих свойства множества элементарных функций. Функции x₁&x₂ , x₁x₂ , x₁x₂ обладают свойствами:

1. коммутативности, 2. ассоциативности.

3. Для конъюнкции и дизъюнкции выполняются дистрибутивные законы:

((x₁ x₂)  x₃) = (x₁x₃)  (x₂x₃)), ((x₁ x₂)  x₃) = (x₁x₃)  (x₂x₃)).

4. Конъюнкция, дизъюнкция и отрицание связаны законами де Моргана.

5. Справедливо правило снятия двойного отрицания: =x.

6. Кроме того, выполняются свойства идемпотентности: (x&x)=x, (xx)=x.

7. Для констант справедливы следующие соотношения: =1, =0,

(x&1)=x, (x&0)=0, (x1)=1, (x0)= x, (x&)=0, (x)=1. Предпоследнее равенство наз. законом противоречия, а последнее  законом исключенного третьего.

8. Конъюнкция обладает свойством дистрибутивности относительно сложения по mod 2:

((x₁x₂)  x₃) = (x₁x₃)  (x₂x₃)).

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

Cчитают операции упорядоченными по силе следующим образом: , &, , , .

Пример. Запись x₁  x₂  x₃  x₄ означает (x₁  ((x₂  x₃)  x₄)).

Если операция ассоциативна, то можно вместо формул ((x₁x₂)x₃), (x₁(x₂x₃)) используют выражение x₁x₂x₃, которое не является формулой, но может быть превращено в нее путем расстановки скобок, причем функциональные свойства не меняются, как бы мы эти скобки ни расставляли.

Иногда для & и  употребляют выражения, аналогичные символу суммирования: x_i, x_i.

Сформулируем ряд правил, вытекающих из пунктов 2 и 5 списка тождеств элементарных функций, которыми удобно пользоваться при осуществлении эквивалентных преобразований:

 если в лог. произведении один из множителей равен 0, то и лог. произведение равно 0,

 если в лог. произведении, содержащем не менее двух множителей, есть множитель, равный 1, то этот множитель можно зачеркнуть,

 если в лог. сумме, содержащей не менее двух слагаемых, имеется слагаемое, равное 0, то это слагаемое можно зачеркнуть,

 если в лог. сумме одно из слагаемых равно 1, то и лог. сумма равна 1.

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

Пример. С помощью эквивалентных преобразований выведем две полезные формулы, называемые правилами поглощения.

1) x  x&y = x&1  x&y = x & (1y) = x&1 = x: эл-т лог. суммы x “поглотил” лог. произведение.

2) x & (xy) = x&x  x&y = x  x&y = x: лог. множитель x “поглотил” логическую сумму xy.

Существует еще один способ для получения тождеств. Он основан на использовании принципа двойственности.

Функция f*(x₁,x₂,...,x_n) =(), называется двойственной функцией к f(x₁,x₂,...,x_n).

Таблицу для двойственной функции из таблицы для исходной функции можно получить, если инвертировать (то есть заменить 0 на 1 и 1 на 0) столбец функции, а затем его перевернуть.

Таблица	1.7
f	f*
0	1
1	0
x	x
&	
	&

В таблице 1.7 приведены важные примеры двойственных функций. Анализируя эту таблицу, принцип двойственности для формул над множеством P={0, 1, x, , x₁x₂, x₁x₂} можно сформулировать так: для получения формулы *, двойственной к формуле , нужно в формуле  всюду заменить 0 на 1, 1 на 0, & на ,  на &.

Пример. Если (x₁,x₂)=x₁x₂ , то *(x₁,x₂)=(x₁x₂)( ).

Из принципа двойственности вытекает, что если две функции равны ((x₁,x₂,...,x_n)=(x₁,x₂,...,x_n)), то равны и соответствующие им двойственные функции (*(x₁,x₂,...,x_n)=*(x₁,x₂,...,x_n)).

Пример. Из истинности первого закона де Моргана непосредственно следует истинность второго закона .