Равносильность формул. 
Законы логики высказываний

Пусть F и G — формулы логики высказываний; х_г, х₂, …, х" — логические переменные, входящие хотя бы в одну из этих формул.

Будем считать, что F и G — равносильные формулы, и писать F = G, если на любых одинаковых наборах логических значений переменных х_ь х₂, ???, х_п логические значения формул F и G совпадают.

Проверить равносильность двух любых формул можно, составив для них таблицы истинности. Как и в случае с тавтологиями и противоречиями, практически это удобно лишь в тех случаях, когда в формулы входит небольшое число переменных и формулы не очень длинны.

Пример 2.6.

Убедимся в том, что формулы.

Решение. Строим совместную таблицу истинности формул F и G.

равносильны.

Из таблицы очевидно, что на любых одинаковых наборах логических значений переменных х_х, х₂ логические значения формул F и G совпадают: столбцы формул F и G в таблице одинаковы. Это означает, что формулы F и G равносильны. ?

Замечание. Формулы, проверяемые на равносильность, не обязаны зависеть от всех логических переменныхх_г, х₂,…, х_п из списка.

Говорят, что формула F не зависит от переменной х,-, если для любого фиксированного набора логических значений остальных переменных, входящих в эту формулу, логическое значение F одно и то же, когда х, истинно и когда х, — ложно. Таким образом, понятие равносильности определено и для формул, содержащих разное количество переменных.

Как вытекает из определения и вида таблиц истинности, равносильность формул F = G обладает следующими свойствами.

• 1. F = F, т. е. любая формула равносильна самой себе, — свойство рефлексивности.
• 2. Если F = G, то G = F, т. е. равносильность справедлива «в обе стороны», — свойство коммутативности.
• 3. Если F = G и G = Н, то F = Н, свойство транзитивности, позволяющее строить «цепочки» равносильных формул.

С другой стороны, выражение F = G можно рассматривать как одну формулу, в которой подформулы F и G связаны логической операцией эквивалентности F G.

Из определения этой операции (см. табл. 2.2) вытекает утверждение: формулы F и G равносильны тогда и только тогда, когда формула F <-" G является тавтологией, т. е. тождественно истинной формуле.

Приведем список наиболее важных равносильных формул логики высказываний, часто называемых законами логики высказываний.

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

Законы логики высказываний.

Законы нуля и единицы Законы поглощения

• 1.0 = 1 14. Aa (AvB)=A
• 2.1 = 0 15. Av (AaB)=A
• 3. Аа1 = А
• 4 А л 0 = 0 Законы коммутативности

‘ конъюнкции и дизъюнкции

• 6 AvO = A^аВ = ВлА
• 17. AvB = BvA

Закон исключенного

третьего Законы ассоциативности

• 7 AvA = l конъюнкции и дизъюнкции
• 18. А, а (В л С) = (А л В) а С

Закон противоречия _19< Av^BvC) = (AvB)vC

8. АлА = 0.

Законы дистрибутивности

Закон двойного отрицания _{20 A v} (В, а С) = (A v В) a (A v С).

9. А = А 21. А л (В, а С) = (А, а В) v (А, а С).

Законы идемпотентности Закон контрапозиции

• 10. АаА = А 22. А—>В = В—> А
• 11. A v, А = А

Правила замены логических Законы де Моргана операций

• 12. АлВ = АуВ 23. А —> В = A v_B _
• 13. AvB = AaB 24. (А В) = (AaB)v (AaB)

Некоторые из приведенных здесь законов были известны в течение многих столетий. Закон исключенного третьего в словесной формулировке гласит: «Каждое высказывание истинно или ложно, третьего не дано».

Закон противоречия формулируется так: «Никакое высказывание не может быть одновременно и истинным, и ложным».

Закон контрапозиции используется в математике для доказательства «от противного».

Особое внимание обратим на законы 20 и 21. Они называются законами дистрибутивности. Более точно, закон 20 — дистрибутивность дизъюнкции относительно конъюнкции, а 21 —дистрибутивность конъюнкции относительно дизъюнкции.

Закон 21 имеет аналог в школьной алгебре — это дистрибутивность умножения чисел относительно сложения с раскрытием скобок.

Закон 20 такого аналога не имеет. Сложение чисел не дистрибутивно относительно умножения. Отличие операций конъюнкции и дизъюнкции над высказываниями от числовых операций умножения и сложения состоит в том, что для высказываний выполняются обе дистрибутивности.

Пример 2.7.

С помощью таблиц истинности проверить, являются ли равносильными формулы F и G:

Решение. Составим таблицы истинности для каждой формулы.

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

Пример 2.8.

С помощью таблиц истинности проверить, являются ли равносильными формулы F и G:

Решение. Составим таблицы истинности для заданных формул.

Из составленных таблиц очевидно, что формулы не равносильны. ?