Т. А. Сливина математическая логика и теория алгоритмов

3. Равносильности, выражающие основные законы алгебры логики
– коммутативность коньюнкции и дизьюнкции.
– ассоциативность коньюнкции и дизьюнкции.
– дистрибутивность коньюнкции относительно дизьюнкции и наоборот.
Докажем формулу 6.
При х = 1, формулы и будут истинны, тогда и – тоже истинна.
При х = 0, ≡ ≡ ≡ следовательно, ≡
Таким образом, обе части формулы 6 равносильны одной и той же формуле и поэтому принимают одинаковые логические значения. Что и требовалось доказать.
Равносильности 3-ей группы выражают основные законы алгебры логики: коммутативность, ассоциативность и дистрибутивность (относительно логических операций – коньюнкции и дизьюнкции). Эти же законы имеют место в алгебре чисел. Поэтому над формулами алгебры логики можно производить те же преобразования, которые проводятся в алгебре чисел, т. е.
1) раскрытие скобок;
2) заключение в скобках;
3) вынесения за скобки общего множителя.
Кроме этих преобразований над формулами алгебры логики можно производить и преобразования, основанные на использовании равносильностей.
Равносильные преобразования формул используют
1) для доказательства равносильностей,
2) для приведения формул к заданному виду,
3) для упрощения формул.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций коньюнкции и дизьюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.


Пример.
1. Доказать равносильность
Доказательство:

2. Упростить формулу

3. Доказать тождественную истинность формулы

Запишем цепочку равносильных формул:

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