Равенство функций. 
Основные законы булевой алгебры

Два набора значений переменных булевой функции {х_х, х₂, х"}.

и {у_х, у₂, у_п} считаются соседними, если они отличаются ровно в одном разряде.

Пример 3.1.

• (ООН) и (1011) —соседние наборы;
• (0101) и (0100) — также соседние наборы. ?

Переменная х, булевой функции z (х_1; х₂, x_t, …, х") называется существенной, если можно указать такой набор переменных, что z (х_х, х₂, …, 0, …, х") не равна z (х_1; х₂, х").

Пример 3.2.

Для таблично заданной функции z (х_х> х₂) переменная х₂ является существенной, так как при постоянном значении х_х изменение значения переменной х₂ приводит к изменению значения функции. ?

В данном примере х₂ уже не является существенной. Действительно, табличная функция меняет свое значение лишь при изменении значения х,. Иначе значение функции не меняется. ?

Следствие. Если переменная не является существенной, то ее называют фиктивной и ее можно исключать.

Две булевых функции z_x и z₂ считаются равными, если одна из этих функций может быть получена из другой функции путем добавления или удаления фиктивной переменной. Очевидно, таблицы истинности у них одинаковы.

Пример 3.4.

В соответствии с приведенными ниже таблицами функции z (х_их₂) и z (хД равны. Действительно, как очевидно из таблиц, z (хД получается из функции z (xj, х₂) удалением фиктивной переменной х₂.

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

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

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

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

Законы булевой алгебры

Законы нуля и единицы Законы поглощения

• 1−0 = 1 14. х_х-Ui+х₂) = х_х
• 2. 1=0 15. Xj +(xj •х₂) = х₁
• 3. х-1 = х
• 4 х ? 0 = 0 Законы коммутативности

g' _{Jc +} 2_j логического умножения

' и сложения

• 6. х + 0 = х
• 16. Xj •х₂=х₂ х₁

Закон исключенного третьего 17. х_х + х₂ = х₂ + х_х

7 У* 4- У* — Л

Законы ассоциативности

Закон противоречия логического умножения

и сложения

• 8. х-х = 0. ,
• 18. xj •Сх₂-х₃) = (х₁? х₂) • х₃

Закон двойного отрицания 19. х_х +(х₂ +х₃) = (х₁ +х₂) + х₃

Q V —.

Законы дистрибутивности

Законы идемпотентности 20. х_х (х₂+х₃) = х_а х₂+х_х х₃

• 10. х • х = х 21- х₁+х₂-х₃=(х₁+х₂)-(х₁+х₃)
• 11. х + х-х Закон контрапозиции

Законы де Моргана 22. х_х —> х₂ = х₂ —> х_х

• 12. х_х -х₂ -X] +х₂ Правила замены логических
• 13. х₁+х₂=х_] х₂ операций
• 23. х_х —> х₂ = х_х + х₂
• 24. х_х х₂ = (х_х • х₂) + (х_х • х₂)

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

Пример 3.5.

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

Доказательство.

Что и требовалось доказать. ?

Пример 3.6.

Применяя табличный метод, докажем один из законов де Моргана.

Рассмотрим значения левой и правой частей равенства на всевозможных наборах переменных. Результаты сведем в таблицу истинности.

При рассмотрении таблицы легко увидеть, что левая и правая части исследуемой формулы эквивалентны. Доказательство проведено. ?

Рассмотрим некоторые типовые логические операции.

1. Операция поглощения.

Если существует функция.

то операцию х₂ + х₂ = 1 называют иногда операцией склеивания. Эта операция позволяет минимизировать некоторые формулы.

2. Операция добавления.

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