Законы алгебры логики.

Для преобразования логических формул к равносильным используются законы алгебры логики:

1. законы коммутативности
   • x ∧ y = y ∧ x
   • x ∨ y = y ∨ x
2. законы ассоциативности
   • (x ∧ y) ∧ z = x ∧ (y ∧ z)
   • (x ∨ y) ∨ z = x ∨ (y ∨ z)
3. законы поглощения (нуля и единицы)
   • x ∨ 0 = x
   • x ∧ 1 = x
4. законы дистрибутивности
   • x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
   • x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
5. закон противоречия
   • x ∧ ¬ x = 0
6. закон исключенного третьего
   • x ∨ ¬ x = 1
7. законы идемпотентности
   • x ∧ x = x
   • x ∨ x = x
8. закон двойного отрицания
   • ¬ (¬ x) = x
9. законы де Моргана
   • ¬ (x ∧ y) = ¬ x ∨ ¬ y
   • ¬ (x ∨ y) = ¬ x ∧ ¬ y
10. законы поглощения
    • x ∨ (x ∧ y) = x
    • x ∧ (x ∨ y) = x

Законы алгебры логики достаточно просто доказываются с применением различных способов.

Пример 1. Докажем второй закон де Моргана с помощью таблицы истинности. Построим таблицу истинности для левой и правой части закона.

x	y	x ∨ y	¬ (x ∨ y)	¬ x	¬ y	¬ x ∧ ¬ y
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Заметим, что результирующие столбцы в таблице истинности совпали. Таким образом, формулы в левой и правой части закона равносильны.

Пример 2. Докажем второй закон дистрибутивности (который несправедлив в алгебре чисел) путем тождественных преобразований.

1) Для доказательства раскроем скобки в правой части закона:
  (x + y) • (x + z) = x • x + x • z + y • x + y • z
2) Используем закон идемпотентности: x • x = x. В результате имеем,
  x + x • z + y • x + y • z
3) Применим закон поглощения x + x • z = x. После преобразования получим,
  x + y • x + y • z
4) Применим закон поглощения x + y • x = x. Окончательно получаем,
  x + y • z
Таким образом, (x + y) • (x + z) = x + y • z
Равенство доказано.