Операции над множествами. Законы де Моргана

Объединением двух множеств А и В называется множество вида:

AÈB ={a / aÎ A или aÎ B}(рис. 1.2, а).

Пересечением двух множеств А и В называется множество вида:

AÇB={a / aÎ A и aÎ B} (рис. 1.2, б).

Если множества А и В не имеют общих элементов, то AÇB=Æ.

Пример 1.2. Если A={12,15,18}, a B={12,14,16,18}, то AÈB={12,14,15,16,18}, AÇB={12,18}.

а б

Рис. 1.2.

Свойства операций объединения и пересечения

1. AÈB = ВÈА, AÇB = ВÇА (коммутативность);

2. (AÈB)ÈС = AÈ(BÈС), (AÇB)ÇС = AÇ(BÇС) (ассоциативность).

Свойство 2 позволяет записывать без скобок объединение и пересечение любого количества множеств:

=A₁È A₂È...È A_k={a/ aÎA₁ или aÎA₂ или ... или aÎ A_k},

=A₁Ç A₂Ç...Ç A_k={a/ aÎA₁ и aÎA₂ и ... и aÎ A_k}.

Объединение и пересечение связаны законами дистрибутивности:

AÇ(BÈC)= (AÇB) È (AÇС); AÈ(BÇC)= (AÈB) Ç(AÈС).

Докажем первый из них (второй доказывается аналогично).

ÿ С одной стороны, если aÎAÇ(BÈC), то aÎA и aÎ(BÈC), т.е. aÎA и(aÎB или aÎC). Следовательно, (aÎA и aÎB)или(aÎA и aÎC), т.е. aÎ(AÇB)È(AÇС). Отсюда следует, что AÇ(BÈC) Í (AÇB)È(AÇС).

С другой стороны, пусть теперь, наоборот, aÎ(AÇB)È(AÇС). Тогда (aÎA и aÎB) или(aÎA и aÎC), т.е. aÎA и(aÎB или aÎC). Следовательно, aÎAÇ(BÈC). Значит, (AÇ B)È(AÇС) Í AÇ(BÈC).

По свойству 3 операции включения следует равенство правой и левой частей доказываемого равенства.

ÿ

Для операции объединения множеств нейтральным является пустое множество Æ, а для операции пересечения множеств - универсальное множество U.

Семейство множеств {A₁,A₂,...,A_m} называется покрытием множества А, если имеет место равенство A=A₁È A₂È...È A_m. Множества A₁,A₂,...,A_m называются блоками покрытия.

Пример. Множества {1,2,3,5,7}, {3,6,9}, {2,4,6,8} образуют покрытие множества {1,2,3,4,5,6,7,8,9}.

Важным частным случаем покрытия является разбиение. Семейство множеств {A₁,A₂,...,A_m} называется разбиением множества А,если A=A₁È A₂È...È A_m, A_i ¹Æ, A_iÇA_j =Æ, i¹j, 1£ i, j £m. Множества A₁,A₂,...,A_m называются блоками разбиения.

Таким образом, покрытие является разбиением, если его блоки не пусты и попарно не пересекаются.

Из определения разбиения следует, что порядок записи блоков, в силу коммутативности объединения, может быть произвольным. Например, два разбиения {1,2,9}È{5,7}={5,7}È{1,2,9} множества {1,2,5,7,9} считаются совпадающими.

Пример 1.3. Составить все возможные разбиения множества {1,2,3}.

Решение. {1}È{2,3}; {2}È{1,3}; {3}È{1,2}; {1}È{2}È{3}.

В некоторых случаях удобно рассматривать разбиения, в которых порядок записи блоков фиксирован, т.е. любая перестановка блоков даёт новое разбиение. Такие разбиения называют поблочно упорядоченными.

Разность множеств А и В определяется следующим образом:

A\B ={a / aÎA и aÏB} (рис. 1.3, а).

Пример. По условию примера 1.2 A\B ={15}, В\А ={14,16}.

Этот пример хорошо иллюстрирует тот факт, что разность не обладает свойством коммутативности; эта операция также не является и ассоциативной.

Пользуясь понятием универсального множества, можно определить дополнение к множеству А,как разность вида: = U \ A (рис. 1.3, б).

Пример. Пусть в качестве универсального множества выступает множество целых чисел Z и пусть А - это множество всех чётных чисел. Тогда - это множество всех нечётных чисел.

Операции объединения, пересечения и дополнения множеств связаны между собой законами де Моргана:

, .

ÿ Если a Î , то a Ï AÇB. Это значит, что или aÎ , или aÎ , т.е. aÎ . Следовательно, .

С другой стороны, если aÎ , то или aÎ , или aÎ . Это значит, что aÏ AÇ B , т.е. a Î . Таким образом, Í .

Из этих двух включений следует первый закон де Моргана. ÿ

Второй закон доказывается аналогичным образом.

а б

Рис. 1.3.