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

Пусть даны множества A и B.

Пересечением множеств A и B (обозначается AB) называется множество всех элементов, принадлежащих одновременно A и B:

AB={x: x  A  x  B}

или иначе х  х АВ  хА  хВ

О бъединением множеств A и B (обозначается AB) называется множество всех элементов, принадлежащих либо A, либо B, либо одновременно и A и B:

AB={x: x  A  x  B}

и ли иначе х  х АВ  хА  хВ

Мнемоника: «ересечение» и «бъединение».

Следствие

Элементы пересечения множеств включаются в объединение. АВ  AB. Например, {1, 2}  {2, 3} = {1, 2, 3}, {1, 2} {2, 3} = {2}; {2}  {1, 2, 3}.

Разность (дополнение) множеств A и B (записывается в виде A \ B) – множество элементов, принадлежащих A и не принадлежащих B:

A \ B ={x: xA  xB} (дополнение B до A)

иначе х  х А\В  хА  хВ .

Так, если A = {1, 2, 3}, B = {2, 3, 4}, то A\B={1}, B\A={4}.

Симметрическая разность множеств A и B (обозначается AB) определяется как: A  B = (A  B) \ (A  B)

Два множества A и B не пересекаются, если A  B = .

Дополнение множества A (обозначается A) определяется как

A = E \ A = {x: x  A} или х  хА  хА 

Следствия:

A  A = E ;

A  A = .

Пример 2.3.

Пусть E={1,2,3,4}, A={1, 3, 4}, B={2, 3}, C={1, 4}. Для более сложных комбинаций операций будем указывать скобки.

AB = A(B)= A{1, 4} = {1, 4};

(AB) = {3} = {1, 2, 4};

(B\A)  C = {2} C = {1, 2, 4}. 

Пример 2.4.

Доказать, что для множеств A, B, C

A  (B  C) = (A  B)  (A  C).

Доказательство 1 (взаимным вложением множеств)

Необходимо доказать два утверждения:

A  (B  C)  (A  B)  (A  C) и

(A  B)  (A  C)  A  (B  C).

Каждое их этих доказательств состоит из последовательности утверждений вида «если справедливо P, то справедливо Q» (или «из P следует Q», запись: P  Q). Значит, если имеется последовательность P₀, P₁, ... P_n такая, что P₀  P₁, P₁  P₂, ..., P_n-1  P_n, то мы имеем прямое доказательство P₀  P_n.

x A  (B  C)  x A и x(B  C)  x A и (xB или xC)  (x A и xB) или (x A и xC)  (x A  B) или (x A  C)  x (A  B)  (A  C)

Отсюда A  (B  C)  (A  B)  (A  C).

В обратную сторону:

x (A  B)  (A  C)  (x A  B) или (x A  C)  (xA и xB) или (xA и xС)  x A и (x B или x C)  x A и (x B C)  x A  (B  C).

Отсюда: (A  B)  (A  C)  A  (B  C), поэтому A  (B  C) = (A  B)  (A  C)

Заметим, что здесь вторая часть доказательства совпадает с первой (это бывает далеко не всегда), и можно записать: x A  (B  C)  x A и x B C и т.д.

Доказательство 2 (методом принадлежности)

Основываясь на формальном определении равенства множеств, запишем:

х хА  (ВС)  х(АВ)  (АС)

х хА  хВС  хАВ  хАС

х хА  (хВ  хС)  (хА  хВ)  (хА  хС)

Введя краткие обозначения, получим

а_х   (в_х  с_х) (а_х  в_х )  (а_х  с_х )

Это выражение представляет собой логический закон дистрибутивности конъюнкции относительно дизъюнкции. Поскольку это ТИ-высказывание, то доказываемое равенство верно. 

Пример 2.5.

Доказать, что относительно данного множества Е дополнение любого множества A (A  E) единственно.

Доказательство

Предположим, что существуют два множества B и C, каждое из которых удовлетворяет требованиям дополнения A, т.е. B A= C A= и BA = CA = E. Тогда B = B E = B  (CA) = (B  C)  (B A) = (B  C)   = B  C.

Поэтому если x B, то x B и x C. Следовательно, B BC. Значит, B C и B B. Однако B B всегда, следовательно, B C.

Аналогично (меняя C и B местами) имеем: C  B.

Итак, C=B  B=C=A′ и A′ единственно. 

Здесь применялось доказательство «от противного», которое хорошо при доказательстве единственности: сначала предполагается, что существует два таких объекта, а затем доказывается, что они совпадают.

Пример 2.6.

Для любых множеств X и Y верно соотношение: (X  Y)′=X′ Y′. (Вместе с соотношением (X  Y)′=X′ Y′ это называется законами де Моргана).

П остроим диаграммы Венна, иллюстрирующие это.



Пример 2.7.

Представим множество A  (B  C), если общая диаграмма для A, B, C следующая:

Далее заштрихуем B диагональными линиями в одном направлении, а С – в другом направлении. Тогда площадь с двойной штриховкой даст множество B  C:

Далее эту область перештрихуем горизонтальными линиями, а A – вертикальными. Тогда вся заштрихованная область представляет A  (B  C):

Тождества теории множеств доказываются либо методом взаимного включения, либо с помощью метода принадлежности, лмбо с помощью диаграмм Венна.

1. (A′ ) ′ = A

2. A  B = B  A коммутативность пересечения

3. A  B = B  A коммутативность объединения

4. A  (B  C) = (A  B)  C ассоциативность пересечения

5. A  (B  C) = (A  B)  C ассоциативность объединения

6. (A  B)  C = (A  C)  (B  C) дистрибутивность пересечения

относительно объединения

7. (A  B)  C = (A  C)  (B  C) дистрибутивность объединения

относительно пересечения

8. (A  B) ′ = A′  B′	законы де Моргана
9. (A  B) ′ = A′  B′
10. A  A = A	тождества
11. A  A = A	сокращения

12. A  A′ = 

13. A  A′ = E

14. A  B  B′  A′

15. A = B  A  B  B  A

16. A  B  B  C  A  C

17. A = B  A′ = B′

18. A  E = E

19. A  E = A

20. A   = A

21. A   = 