Множества и отображения

16. Соотношения между высказываниями и соответствующими им множествами истинности

Мы рассмотрели такие множества истинности составных высказы­ваний, которые образованы посредством связок V, А, . Все остальные связки можно определить через эти три основные и тем самым вывести, какие множества истинности им соответствуют. Например, известно, что импликация X —» У эквивалентна дизъюнкции X V У. Поэтому множе­ство истинности для X —» У будет тем же, что и множество истинности для X V У, т. е. оно будет иметь вид A U Б.

На диаграмме Эйлера-Венна выделенная область показывает множе­ство истинности этого высказывания (см. рис. 2.6).

Отметим, что незаштрихованная область на этой диаграмме показы­вает множество А \ В = А П В, представляющее собой множество истинно­сти высказывания ХА У. Поэтому заштрихованная область будет множе­ством А \ В = А П В, которое является множеством истинности высказы­вания ХА У. Таким образом, мы установили, что высказывания X —» У, XV У, X А У эквивалентны. Вообще, два высказывания эквивалентны то­гда и только тогда, когда они имеют одни и те же множества истинности.

Заметим, что диаграммы Эйлера-Венна помогают обнаруживать от­ношения между высказываниями.

Предположим теперь, что X — логически истинное высказывание. Что представляет собой его множество истинности? Поскольку высказы­вание X логически истинно тогда и только тогда, когда оно истинно в каждом логически возможном случае, множеством истинности для вы­сказывания X должно быть универсальное множество U.

Подобным же образом, если высказывание X логически ложно, то оно ложно в каждом логически возможном случае, и поэтому его множеством истинности будет пустое множество 0.

Рассмотрим отношение следствия. Напомним, что из X следует У то­гда и только тогда, когда импликация X —> У логически истинна. Но высказывание X —»• У тогда и только тогда логически истинно, когда его множество истинности совпадает с U, т. е. (А \ В) = U и А \ В = 0. Но если А \ В пусто, то В включает в себя А. Отношение включения обозначает­ся, как мы отмечали, А С Б и читается «А является подмножеством Б». Таким образом, высказывание X —»• У логически истинно тогда и только тогда, когда А С Б.

17. Выводы

Каждому высказыванию соответствует его множество истинности, каждой логической связке соответствует операция над множеством. Каж­дому отношению между высказываниями соответствует отношение ме­жду множествами истинности. Множествами истинности высказываний

XV У; ХЛУ; X и X-> У

служат соответственно:

AUB; А П В; А и А\В.

Высказывание X логически истинно, если А = U, и логически ложно, если А = 0. Высказывание X и У эквивалентны тогда и только тогда, когда А = В; из X следует У тогда и только тогда, когда А С В.

18. Абстрактные законы операций над множествами

Введенные операции над множествами подчинены некоторым очень простым абстрактным законам, которые будут перечислены в этом раз­деле.

Эти законы очень напоминают элементарные законы алгебры выска­зываний.

По этой причине множество, его подмножества и законы сочетания подмножеств образуют алгебраическую систему, называемую булевой ал­геброй. Система составных высказываний, подчиняющаяся таким зако­нам, тоже называется булевой алгеброй. Таким образом, любую из этих систем можно изучать или с алгебраической, или с логической точки зре­ния.