Равносильности алгебры логики

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

Перечислим основные равносильности алгебры логики.

Ассоциативность:

1. x_1˙(x₂·x₃)=(x₁·x₂)·x₃

2. 2. (x₁vх₂)Úx₃ = x₁v(х₂Úx₃)

Коммутативность:

3. x₁·х₂ = х₂ ·x₁

4. x₁Úх₂ = х₂ Úx₁

Дистрибутивность конъюнкции относительно дизъюнкции:

5. x₁·(х₂Úx₃) = x₁·х₂Úx₁ ·x₃

Дистрибутивность дизъюнкции относительно конъюнкции:

6. x₁Ú(х₂ ·x₃ ) = (x₁Úх₂) ·(x₁Úx₃ )

Идемпотентность:

7. х·х = х

8. хÚх = х

Двойное отрицание:

9. x=x

Законы де Моргана:

10. x₁×х₂=x₁ Ú х₂

11. x₁ Ú х₂ = x₁ × х₂

Закон противоречия:

12. х ×х = 0

Закон "исключенного третьего"

13. х Ú х = 1

Свойства констант:

14. х× 1 = х

15. х× 0 = 0

16. х Ú 1 = 1

17. х Ú 0 = х

18. 0 = 1

19. 1 = 0

Приоритет выполнения логических операций в порядке убывания следующий: отрицание, конъюнкция, дизъюнкция.

Рассмотрим некоторые тождественные преобразования:

1. х₁ Ú x₁ × x₂ = x₁

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

х₁ Ú x₁ × x₂ = x₁ × 1 v x₁ × x₂ = x₁ × (1 Ú x₂) = x₁ × (x₂ Ú 1) = x₁ × 1 = x₁

Первое преобразование справедливо в силу равносильности 14, второе - в силу равносильности 5, третье - равносильности 3, четвертое - равносильности 16 и пятое - равносильности 14.

Аналогично доказываются равносильности:

2. х₁ Ú х ₁ × x₂ = х₁ Ú х₂

3. х₁ × ( х ₁ Ú х₂ ) = х₁ × х₂

4. х₁ × ( х₁ Ú х₂ ) = х₁ × х₂

Рассмотрим более сложный пример. Докажем следующую равносильность:

х₁ × ( х₁ Ú х₂ ) × (х₁ Ú х₂ Ú x₃) = х₁ х₂

При доказательстве используем вышеприведенные тождественные преоб-разования.

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

х₁ × ( х₁ Ú х₂ ) × (х₁ Ú х₂ Ú x₃) = х₁ × х₂ × (х₁ Ú х₂ Ú x₃) = х₁ × х₂ × х₁ Ú

Ú х ₁ × х ₂ × х ₂ Ú х ₁ × х ₂ × x ₃ = х₁ × х ₁ × x ₂ Ú х ₁ × x ₂ Ú х ₁ × х ₂ × x ₃ = х ₁ × х ₂ Ú

Ú х ₁ × х ₂ Ú х ₁ × х ₂ × x ₃ = х₁ × ( х ₂ Ú х ₂ ) Ú х ₁ × х ₂ × x ₃ = х ₁ × х ₂ Ú х ₁ × х ₂ × x ₃ =

= х ₁ × ( х ₂ Ú х ₂ × x ₃ ) = х ₁ × х ₂ = х ₁ Ú х ₂ = х ₁ Ú х ₂ = х ₁ х ₂