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

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

Пример. x | y = Ú = = (x­y) Å

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

Приведем список эквивалентностей (тождеств), характеризующих свойства множества элементарных функций. Функции 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.

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

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

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*
x	x
&	Ú
Ú	&

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

Пример. Если a(x₁,x₂)=x₁&x₂Ú & , то a*(x₁,x₂)=(x₁Úx₂)&( Ú ).

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

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