Операции над множествами

Определим следующие операции.

1. Объединение. Пусть А и В - произвольные множества. Их объединением называется множество С = АÈВ, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В.

2. Пересечение. Пересечением множеств А и В называется множество С, состоящее из элементов одновременно принадлежащих А и В. Обозначается так: C=AÇB.

3. Разность. Разность множеств А и В - это множество С (С=А\В), состоящее из элементов множества А, не принадлежащих множеству В. Если ВÍА, то разность С = А\В называется дополнением В до А. Иногда, говоря о некотором наборе множеств подразумевают, что все они включены в некоторое множество S, которое называют универсальным множеством. В этом случае дополнение какого-либо множества А до S обозначается С(А) или .

4. Симметричная разность. По определению симметричная разность двух множеств А и В - это множество

С = АDВ = (А\В)È(В\А).

Основные свойства операций.

1. Операции пересечения и объединения коммутативны (перестановочны): АÇВ = ВÇА; АÈВ = ВÈА.

2. Операции пересечения и объединения ассоциативны.

(АÇВ) ÇС = АÇ (ВÇС) = АÇВÇС

(АÈB) ÈС = АÈ (ВÈС) = АÈВÈС.

Свойствами коммутативности и ассоциативности обладают многие операции. Чтобы не создалось впечатления, что коммутативность и ассоциативность являются общими свойствами всех операций, приведем пример неассоциативной операции - возведение в степень. Имеем: (2³)² = 8² = 64; = 2⁸ = 512.

Пример некоммутативной операции - операция умножения матриц (АВ¹ВА).

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

Для вещественных чисел закон дистрибутивности читается так: а(в+с) = ав + ас. Для множеств закон дистрибутивности имеет вид:

а) (АÈВ)ÇС = (АÇС) È (ВÇС)

б) (АÇB) ÈС = (АÈС) Ç (ВÈС).

Докажем равенство а).

Предположим, что xÎ (АÈВ) ÇС, тогда xÎС и xÎА или xÎВ. Рассмотрим первый случай xÎС и xÎА. Тогда хÎАÇС, а значит, по определению объединения, хÎ(АÇС)È(ВÇС).

Во втором случае, т.е. при xÎС и xÎВ получаем, что xÎ (ВÇС)È(АÇС). Таким образом, мы доказали включение

[(АÈВ) ÇС]Í[(АÇС)È(ВÇС)].

Докажем обратное включение. Пусть хÎ(АÇС)È(ВÇС), тогда хÎАÇС или хÎВÇС. В первом случае хÎА и хÎС. Во втором случае хÎВ и xÎС. В обоих случаях получаем, что хÎС и хÎА или хÎВ. Следовательно, хÎ(АÈВ) ÇС. Тем самым доказано включение (АÇС)È(ВÇС)Í(АÈВ) ÇС.

Таким образом, (АÈВ) ÇС=(АÇС)È(ВÇС), что и требовалось доказать.

Пусть А₁, А₂, . . . - некоторые множества и пусть все они включены в S (А₁, А₂, . . . Í S). Тогда выполняются следующие соотношения.

4. - дополнение объединения множеств равно пересечению их дополнений.

5. - дополнение пересечения множеств равно объединению их дополнений.

Докажем свойство 4. Пусть хÎ, тогда хÏзначит, x не принадлежит ни одному из множеств A_k ("k, хÏА_k), следовательно, по определению дополнения хÎS\А_k для любого k. Отсюда вытекает, что хÎ.

Обратно, пусть хÎтогда этот элемент принадлежит каждому из множеств S \ A_k ("k, хÎS\ A_k). Следовательно, хÏA_k для любого k, а, значит, хÏи поэтому хÎ, что и требовалось доказать.