§ 2. Простейшие операции над множествами

Как мы видели из рассмотрения «ошибочного множе­ства» F в примере 1.1 необходимо проявлять вниматель­ность при определении множества. Тем не менее, строя новые множества из старых по простым правилам, можно безопасно получить много интересных примеров.

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

Определение. Пусть даны множества А и В. Пересечением множеств А и В называется множество всех элементов, принадлежащих А и В, и обозначается А ∩ В; таким образом,

}.

Аналогично объединение А и В обозначается А B и определяется следующим образом:

}.

Значения этих обозначений нетрудно запомнить, но иногда бывают ошибки. Один из путей запомнить, какой символ обозначает какую операцию,— объединить сим­волы в слова и записать « ересечение» и « бъединение». Эти определения выводятся из слов «и» и «или», и, как следствие, мы имеем

= , =

и, что, вероятно, менее очевидно,

= A, = A.

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

Заметим также, что определение объединения исполь­зует включение «или», называемое так сотому, что оно включает «и» так, что

{1, 2} {2, 3} = {1, 2, 3},

{1, 2} {2, 3} = {2}.

Элементы в пересечении множеств (в данном случае это — единственное число 2) включаются в объединение. Это обычная математическая договоренность, и существу­ет пример, в котором математическое значение является более точным, чем при общем употреблении.

Пример 2.1. В предположении, что каждый день или дождливый, или ясный, математическим (или логи­ческим) ответом на вопрос

«Ясно или дождливо сегодня?»

будет

«Да».

Определение. Разность множеств А и В (также называемая дополнением В до А) записывается в виде А\В и определяется соотношением

А\В = {х: х А и х∉ В}.

Поэтому, если А = {1, 2, 3} и B = {2, 3, 4}, то А\В={1} и В\А = (4).

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

Определение. Симметрическая разность множеств А и B, т. е, АΔВ, определяется как

АΔВ=(А B)\(A B).

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

Пример 2.2. Предположим, что мы имеем две про­граммы, называемые Р и Q, и что А — множество всех значений данных, доступных Р, а В — множество всех значений данных, доступных Q. Тогда А В — множество всех данных, доступных Р и Q; A В — множество всех данных, доступных по крайней мере или Р, или Q; А\В —' множество всех данных, доступных Р, но недо­ступных Q; В\А — множество всех данных, доступных Q, но недоступных Р; АΔB — множество всех данных, до­ступных только одной из программ Р или Q.

Чтобы полностью определить А и B, мы должны знать некоторые данные о вычислениях, связанные с Р и Q. В нашем случае достаточно сказать, что они произ­водятся на некоторой конечной ЭВМ.

Перед дальнейшим изложением будет удобно опреде­лить два специальных множества. Первое из них пу­стое множество.

Определение. Пустое множество (обозначает­ся ø) есть множество, обладающее свойством