Математические методы в библиотечной работе. Елизаров А.М - 54 стр.

отношение (АЛ8) получило название закона двойного
отрицания.
 Отмеченное сходство между алгеброй множеств
и алгеброй логики не случайно — далее мы укажем,
что в некотором смысле эти две алгебры являются
различными формулировками одной и той же теории.
Как установить справедливость этих равносиль-
костей? Укажем полезный способ проверки, который
можно применить в данной ситуации.
   Теорема. Логические выражения X и У равно-
сильны в том и только в том случае, когда экви-
валенция Х←→У истинна при всех значениях логи-
ческих переменных.
   Доказательство. Пусть выражения равносиль-
ны: X    У. Это означает, что для любой комбинации
значений логических переменных X и У одновременно
или истинны, или ложны. Но тогда эквиваленция
Х←→У истинна.
   Пусть теперь X←→У истинна при любых наборах
значений переменных. Это возможно лишь тогда,
когда X и У либо одновременно истинны, либо одно-
временно ложны, что указывает на равносильность
X    У .
   Отметим разницу между эквиваленцией и равно-
сильностью: эквиваленция — это логическая операция,
позволяющая по двум высказываниям строить новое,
а равносильность — это отношение между высказы-
ваниями» состоящее в том» что значения истинности,
этих высказываний всегда одни и те же.
   Логические выражения» истинные при любых зна-
чениях истинности входящих в них переменных, на-
зывают тождественно истинными или тавтологиями
(от греческого „тауто"— то же самое, ,,логос" —
слово).
   Пример 1. Докажем один из законов де Моргана
(АЛ7):                Для этого построим таблицу
истинности для               , и убедимся, что она
является тавтологией (табл. 12).
   Покажем, как на основе знания основных равно-
сильностей можно упрощать сложные высказывания.
   Пример 2. Упростим сложное высказывание


54