Доказательство равносильностей

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

2. С помощью эквивалентных преобразований
Равносильности алгебры логики относительно базовых
логических операций:
Ассоциативность:
x1 ▪ (x2 ▪ x3) = (x1 ▪ x2) ▪ x3
(x1 ∨ х2) ∨ x3 = x1 ∨ (х2 ∨ x3)
Коммутативность:
x1 ▪ х2 = х2 ▪ x1
x1 ∨ х2 = х2 ∨ x1
Дистрибутивность
конъюнкции
относительно
дизъюнкции:
x1 ▪ (х2 ∨ x3) = x1 ▪ х2 ∨ x1 ▪ x3

Дистрибутивность
дизъюнкции
относительно
конъюнкции :
x1 ∨ (х2 ▪ x3) = (x1 ∨ х2) ▪ (x1 ∨ x3)
Идемпотентность:
х ▪ х = х
х ∨ х = х
Двойное отрицание:
Законы де Моргана:

Закон противоречия:
Закон «исключенного
третьего»:
Свойства констант:
х ▪ 1 = х
х ▪ 0 = 0
х ∨ 1 = 1
х ∨ 0 = х
0 = 1
1 = 0

Все равносильности легко доказываются по таблицам истинности.
Примеры.
1
х1 ∨ x1 ▪ x2 = x1
х1 ∨ x1 ▪ x2 = x1 ▪ 1 ∨ x1 ▪ x2 = x1 ▪ (1 ∨ x2) = x1 ▪ (x2 ∨ 1) = x1 ▪ 1 = x1
2
x ∨ y ∨ z ∨ 1 = 1
x ∨ y ∨ z ∨ 1 =x ∨ y ∨ 1= x ∨1=1

3
x ▪ y ▪ x = x ▪ y
x ▪ y ▪ x = x ▪ x ▪ y = x ▪ y
4
y ▪ (a ∨ b) ▪ (x ∨ y ∨ z) = (a ∨ b) ▪ y
y ▪ (a ∨ b) ▪ (x ∨ y ∨ z) = (a ∨ b) ▪ (y ▪ x ∨ y ▪ y ∨ y ▪ z) =
=(a ∨ b) ▪ (x ▪ y ∨ y ∨ y ▪ z) = (a ∨ b) ▪ y ▪ (x ∨ 1 ∨ z) =
=(a ∨ b) ▪ y ▪ 1 = (a ∨ b) ▪ y
5
x ▪ (y ∨ z) ▪ (x ∨ y ∨ z) = x ▪ (y ∨ z)
x ▪ (y ∨ z) ▪ (x ∨ y ∨ z) = (y ∨ z) ▪ ( x ▪ x ∨ x ▪ y ∨ x ▪ z) =
= (y ∨ z) ▪ (0 ∨ x ▪ y ∨ x ▪ z) = (y ∨ z) ▪ (x ▪ y ∨ x ▪ z) =
=(y ∨ z) ▪ x ▪ (y ∨ z) = x ▪ (y ∨ z)

6
(x1 ∨ х2) ▪ (x1 ∨ x3) = x1 ∨ х2 ▪ x3
(x1 ∨ х2) ▪ (x1 ∨ x3) = x1 ▪ x1 ∨ x1 ▪ x3 ∨ х2 ▪ x1 ∨ х2 ▪ x3 =
=x1 ∨ x1 ▪ x3 ∨ х2 ▪ x1 ∨ х2 ▪ x3 = x1 ▪ (1 ∨ x3 ∨ х2) ∨ х2 ▪ x3 =
=x1 ▪ 1 ∨ х2 ▪ x3 = x1 ∨ х2 ▪ x3
7
x ∨ x ▪ y = x ∨ y
x ∨ x ▪ y = (x ∨ x) ▪ (x ∨ y) = 1 ▪ (x ∨ y) = x ∨ y