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

Как видно на рис.4.4 и рис.4.5, одна и та же булева функция может быть реализована различными переключательными схемами и описана разными формулами. Далее рассмотрим правила тождественного преобразования булевых функций.

На основании таблиц соответствия нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:

1) коммутативность:

;

2) ассоциативность:

;

3) дистрибутивность:

;

4) свойство констант:

;

5) свойство отрицания:

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

Таблица 5.1
х	у	z

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

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

Эти свойства позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам соответствия:

1) законы де Моргана:

;

2) законы поглощения:

;

3) законы идемпотентности:

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

Из равенства и свойств отрицания следует, что

т.е.

После раскрытия скобок получим следующее:

Так как и , а и , то предыдущее выражение можно представить в следующем виде:

Используя свойства констант (, , , ), получаем

– очевидное тождество.

Таким образом, путем эквивалентных преобразований мы привели выражение первого закона де Моргана к тождеству и этим доказали справедливость данного закона.

Второй закон де Моргана может быть легко получен на основе первого путем отрицания левой и правой части и соответствующей замены переменных. Запишем первый закон де Моргана относительно переменных a и b: