3. Основные эквивалентные преобразования формул (законы логики высказываний)
Две формулы логики высказываний называются эквивалентными (равносильными), если они принимают одинаковые логические значения при одинаковых наборах логических значений входящих в них пропозициональных переменных. Эквивалентные формулы будем обозначать знаком « = ».
Таблицы истинности для эквивалентных формул совпадают (с точностью до перестановки строк).
Можно показать, что две формулы F и G эквивалентны тогда и только тогда, когда формула F G – тавтология.
В логике высказываний иногда приходится проводить преобразования формул, сохраняющие эквивалентность. Для таких преобразований используют законы логики высказываний, которые имеют вид эквивалентностей (равносильностей).
Пусть А, В, С – некоторые формулы логики высказываний, тогда следующие формулы эквивалентны:
1
–
идемпотентность.
.
А
А = А
2. А А = А
3.
– закон двойного отрицания.
4
–
свойства констант.
.
А
1 = А, А
1 = 1
5. А 0 = 0, А 0 = А
6. А
= 0 – закон противоречия.
7. А
= 1 – закон исключенного третьего.
8
– закон
поглощения.
.
А
(А
В) = А
9. А (А В) = А
1
–
коммутативность.
0.
А
В = В
А
11. А В = В А
1
–
ассоциативность.
2.
А
(В
С) = (А
В)
С
13. А (В С) = (А В) С
1
–
дистрибутивность.
4.
А
(В
С) = (А
В)
(А
С)
15. А (В С) = (А В) (А С)
1
–
законы Де Моргана.
6.
17.
18. А
В
=
– закон контрапозиции.
19. А
В
=
– закон противоположности.
20. А
В
=
В.
21. А В = (А В) (В А).
Доказательство этих эквивалентностей легко получается с помощью таблиц истинностей.
Пример. Трое мужчин – Вася, Гриша, Миша – пришли в цирк со своими детьми: Сашей, Петей и Колей. К детям подошел клоун и спросил: «Кто твой папа?» Каждый из детей сказал следующее:
Саша: Я сын Васи, Петя – сын Гриши.
Петя: Я сын Васи, Коля – сын Гриши.
Коля: Я сын Васи, Петя – сын Миши.
В ответах каждого из них одно утверждение истинно, а другое – нет. Требуется определить, кто чей папа.
Решение. Обозначим через ХY ребенка, имя которого начинается с буквы Х, а Y – имя папы. Тогда их высказывания можно записать так: СВ и ПГ, ПВ и КГ, КВ и ПМ.
Так как по условию задачи одно из парных высказываний верно, а другое – нет, то можно составить следующие истинные дизъюнкции:
СВ ПГ = 1, ПВ КГ = 1, КВ ПМ = 1.
Но тогда будет истинной и конъюнкция этих дизъюнкций:
(СВ ПГ ) (ПВ КГ) (КВ ПМ) = 1.
Используя основные эквивалетные преобразования к первой и второй скобке, имеем:
(СВ ПГ) (ПВ КГ) = = (СВ ПВ) (СВ КГ) (ПГ ПВ) (ПГ КГ) = = 0 (СВ КГ) 0 0 = СВ КГ.
XY XY = 0, так как у каждого мужчины по одному ребенку.
XY XZ = 0, так как один ребенок не может быть сыном двух пап.
Тогда конъюнкция примет вид:
(СВ КГ) (КВ ПМ) = 1.
Аналогично, используя основные эквивалентные преобразования, имеем:
(СВ КГ) (КВ ПМ) = СВ КГ КВ СВ КГ ПМ = = 0 СВ КГ ПМ.
Таким образом: Саша сын Васи, Коля сын Гриши, Петя сын Миши.
Если формула F содержит подформулу F1, эквивалентную формуле F2, то возможна подстановка всюду в формуле F вместо F1 формулы F2 без изменения истинности формулы F. В результате такой подстановки будет получаться эквивалентная формула. Это дает возможность упрощать формулы, используя основные эквивалентные преобразования.
Доказано, что всякую формулу логики высказываний можно заменить эквивалентной ей формулой, содержащей только две логические операции: дизъюнкцию и отрицание или конъюнкцию и отрицание.
Пример.
Упростить формулу
.
Решение. Применяя последовательно законы логики высказываний, получим:
= (п. 16) =
= (пп. 17, 16) =
=
= (пп. 13, 3) =
= (п. 8) =
Z
=
= (п. 20) = Х Z.
