§ 5. Важнейшие пары равносильных формул

Пусть x, y и z – булевы переменные, Т - тавтология и П - противоречие. Используя таблицу истинности, легко показать:

1. $¬(¬x)$ равносильно x.
Если под x понимать обозначение некоторого высказывания, то получаем, что двойное отрицание высказывания x означает то же, что и высказывание x.
Полученное соотношение между $¬(¬x)$ и x называют законом двойного отрицания.
Аналогичным образом можно показать, что имеют место следующие свойства, часто называемые законами.
законы коммутативности (перестановочности)
2. x & y ~ y & x;
3. x ∨ y ~ y ∨ x;
законы ассоциативности
4. (x & y)& z ~ x &(y & z);
5. (x ∨ y)∨ z ~ x ∨ ( y ∨ z );
первый закон дистрибутивности
6. x&(y∨z) ~ x&y∨x&z
второй закон дистрибутивности
7. x∨y&z ~ (x∨y)&(x∨z)
законы де Моргана
8. ¬ (x&y) ~ ¬x ∨ ¬y
9. ¬ (x∨y) ~ ¬x & ¬y
законы идемпотентности
10. x&x ~ x
11. x∨x ~ x
закон исключенного третьего
12. x∨¬x ~ Т
закон противоречия
13. x&¬x ~ П
свойство операций с Т и с П
14. x&Т ~ А
15. x∨Т ~ Т
16. x&П ~ П
17. x∨П ~ x
законы поглощения
18. x∨x&y ~ x
19. x&(x∨y) ~ x
закон контропозиции
20. x⇒y ~ ¬y⇒ ¬x

Как уже замечено, соотношения 1) - 20) доказываются с помощью таблиц истинности.

Можно показать, что соотношения 1) - 20) будут иметь место и тогда, когда вместо переменных x, y и z будут подставлены произвольные формулы А, В и С соответственно.

Соотношения 1) - 20) позволяют находить для заданных формул равносильные упрощенные формулы или равносильные формулы, имеющие более удобный с некоторых позиций вид.

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

Из соотношений 2) - 6) видно, что операция & напоминает умножение (обладает некоторыми свойствами умножения), а ∨ - сложение, поэтому часто конъюнкцию называют (логическим) произведением, а дизъюнкцию - (логической) суммой.