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

Пересечением множеств A и В называют множество, состоящее из тех и только из тех элементов, которые одновременно принадлежат множествам A и В. Обозначают пересечение , где - символ пересечения.

={ x x и x }

Пересечение множеств определяется конъюнкций высказываний, отсюда сходство знаков и . Если не пересекаются, пишут = Ø (рис. 1.4)

= Ø

рис. 1.4

Если же множества A и В имеют хотя бы один общий элемент, то они пересекаются и Ø (рис. 1.5)

Ø

Рис. 1.5

Заштрихованная площадь здесь - пересечение .

Объединением (суммой) двух множеств A и В называют множество , состоящее из элементов, принадлежащих хотя бы одному из этих множеств.

С=А+В= ={ x x A }={ x x A или }- дизъюнкции высказываний.

Объединение изображается так:

Рис. 1.6

Понятия объединения и пересечения могут быть обобщены на случай любого числа множеств (конечного или бесконечного). Если даны множества А1, А2,... Ак,..., то символическая запись означает объединение данных множеств, т.е. определяет множество, каждый элемент которого принадлежит хотя бы одному из А_к.

Символическая запись означает пересечение данных множеств, т.е. определяет множество, каждый элемент которого принадлежит всем данным множествам.

Пример: Найти пересечение и объединение множеств А и В, если А = {1;2;3;4;5}, B = {4;5;6;7}. В пересечение множеств А В войдут общие элементы: А В = {4;5}. Объединение А В = {1;2;3;4;5;6;7} получается добавлением к элементам множества А недостающих элементов из множества В.

Разностью множеств А и В называют множество А\В тех элементов множества А, которые не содержатся в множестве В:

С = А\В = { x x є A и x B }.

Если В А, то разность А\В называют дополнением множества В до множества А и обозначают С_АВ или _А. На диаграмме это обозначается так:

Рис. 1.7.

Если множества А и В пересекаются, то говорят об их разностях А \ В и В \ А. Изобразим разности на диаграммах Эйлера – Венна (Рис. 1.8).

А В

А\В В\А

Рис. 1.8

Свойства операций над множествами:

1. А Ø = А.

2. А Ø = Ø.

3. А А = А;

(Идемпотентность)

А А = А

4. А В = В А;

(Коммутативность)

А В = В А

5. А (В С) = (А B) С;

(Ассоциативность)

А (В С) = (А В) С

6. А (В С) = (А В) (А С);

(Дистрибутивность)

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

7. Если А Е и В Е, то:

а) С_Е (А В) = С_Е А С_Е В, или

Е \ (А В) = (Е \ А) (Е \ В);

(Законы двойственности)

б) С_Е (А В) = С_Е А С_Е В, или

Е \ (А В) = (Е \ А) (Е \ В)

8. Если В А, то А В = А и А В = В.

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

(А В) С = А В С

(А В) (А С) = А В А С.

Декартовым произведением множеств А и В называют множество А В всех упорядоченных пар элементов (а, в) где а є А, в є В. Элементы а и в называют при этом компонентами (координатами) пары (а, в). Так, для произведения множеств X и Y используется запись X Y = {(x; y) x є X y є Y }.

Если множества X и Y совпадают, то говорят о декартовом произведении множества X само на себя:

X Y = {(x; y) I x є X y є X }.

Пусть заданы множества X = {1; 2; 3}, Y = { a; в }.

Тогда X Y = {(1; а); (1; в); (2; а);(2; в); (3; а); (3; в)},

X X = {(1;1);(1;2); (1;3); (2;1); (2;2); (2;3); (3;1); (3;2); (3;3)}.

Элементы декартова произведения двух множеств можно также представить в виде таблицы или в виде графика.

Пример. Дано: X = { 1, 2, 3, 4 }

Y = { 4;5 }

Изобразить X Y графиком на плоскости.

Решение. Множество X Y состоит из следующих пар:

А В = {(1;4); (1; 5); (2;4); (2;5); (3;4); (3;5); (4;4); (4;5)}.

Отметим эти точки на плоскости (Рис. 1.9)

Рис. 1.9

Свойство декартового произведения:

1. X Ø = Ø X = Ø

2. X Y ≠ Y X

3. X (Y Z) ≠ (X Y) Z

4. X (Y Z) = X Y (X Z)

5. X (Y Z) = (X Y) (X Z)

Более общее определение произведения множеств X_1, X_2,X₃,…,X_n:

Декартовым произведением X₁ X₂ X₃ … X_n называется множество, состоящее из упорядоченных n элементов, первая компонента которых принадлежит множеству X₁, вторая – множеству X₂, n -я -множеству X_n, т.е.

X₁ X₂ …X_n = {(X₁; X₂;…;X_n) x₁ є X₁; x₂ є X₂; x_n є X_n }

Упорядоченная n -ка («энка») элементов, выбранных из множеств X_1, X_2,X₃,…,X_n, называется КОРТЕЖЕМ (с фр. – торжественное шествие). Число n называют длиной кортежа, а элементы x_1, x_2, x₃,…, x_n – его компонентами.

Два кортежа (x_1, x_2,x₃,…,x_n) и (y_1, y_2,y₃,…,y_m) называют равными, если они имеют равные длины n = m и состоят из одних и тех же элементов, т.е. x₁ = y₁, x₂ = y₂,…, x_n = y_m

Количество элементов в декартовом произведении трёх множеств:

n (X₁ X₂ X₃ ) = n₁ (X₁) n₂ (X₂) n₃ (X₃)

Пример: Найти декартово произведение множеств

X₁ = { a; в }, X₂ = { 1;2 }, X₃ = { 3;4;5 }

Решение:

X1 X2 X3={(a;1;3),(a;1;4), (a;1;5) (a;2;3), (a;2;4), (a;2;5), (в;1;3), (в;1;4), (в;1;5), (в;2;3), (в;2;4), (в;2;5)

Количество элементов: n1 n2 n3 =2 2 3= 12.

Поиск по сайту: