2.1.3. Равносильность формул логики высказываний
Определение. Пусть А и В – две формулы, зависящие от одного и того же списка переменных. Будем называть их равносильными, если для любого набора значений переменных они принимают одинаковые значения.
Рассмотрим основные равносильности логики высказываний.
Пусть А, В, С – произвольные формулы. Тогда справедливы следующие свойства логических операций (табл. 11):
Таблица 11
1. Идемпотентность | ||
А Ù А = А | А U А = А | |
2. Коммутативность | ||
А Ù В = В Ù А | А U В = В U А | |
3. Ассоциативность | ||
А Ù (В Ù С) = (А Ù В) Ù С | А U (В U С) = (А U В) U С | |
4. Правила поглощения | ||
А Ù (А U В) = А | А U (А Ù В) = А | |
5. Дистрибутивность | ||
А Ù (В U С) = (А Ù В) U (А Ù С) | А U (В Ù С) = (А U В) Ù (А U С) | |
6. Правила де Моргана | ||
7. Свойства констант | ||
А Ù 1 = А А Ù 0 = 0 | А U 0 = А А U 1 = 1 | |
8. Закон исключения третьего и закон противоречия | ||
9. Снятие двойного отрицания | ||
10. Формулы расщепления (склеивания) | ||
11. Связь дизъюнкции, конъюнкции, отрицания и импликации | ||
12. Выражение эквивалентности | ||
Любая из этих равносильностей легко может быть доказана с помощью таблицы истинности.
Пример 23.
Рассмотрим одно из правил поглощения А Ù (А U В) = А.
Таблица 12
А | В | АUВ | АÙ(АUВ) |
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 |
По таблице 12 видно, что результирующий столбец и столбец А совпадают на все наборах. Значит, формулы действительно равносильны.
Однако часто равносильность экономнее доказывать без составления полной таблицы истинности, а с помощью приведенных выше равносильностей.
Пример 24.
1. Доказать равносильность формулы, используя логические законы: .
2. Упростить формулу: .
3. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим:
a) ;
b) ;
c) ;
d) ;
e) .
Решение.
1. .
2.
3. a)
Поскольку формула при любых значениях переменных равна нулю, то данная формула является противоречием.
b) .
Исходная формула не является ни тавтологией, ни противоречием, поскольку её значение зависит от значений переменных.
c)
Исходная формула не является ни тавтологией, ни противоречием, поскольку её значение зависит от значений переменных.
d)
Исходная формула не является ни тавтологией, ни противоречием, поскольку её значение зависит от значений переменных. e)
Поскольку формула при любых значениях переменных равна единице, то данная формула является тавтологией.