Множини. Операції над множинами

2,3 ∈ {2,3} і {2,3}∈А.

Однак це не означає, що елементи 2 та 3 є в множині А (в наведеному прикладі немає 2 і 3 серед елементів множини А, тобто 2,3∉А).

 

5.   Операції над множинами

Розглянемо дві множини А та В і введемо кілька операції над ними. Для графічної ілюстрації будемо використовувати так звані діаграми Венна або кола Ейлера. Діаграма Венна являє собою схемне зображення множин у вигляді множин точок: універсум U зображується множиною точок деякого прямокутника, а його підмножини – у вигляді кіл або інших простих областей у цьому прямокутнику.

Означення 1.5. Об’єднання А і В (А∪В) – множина, що складається з усіх елементів множин А, всіх елементів множини В і не містить ніяких інших елементів (рис 1.1,а), тобто А∪В = {x | x∈A або x∈В}.

Наприклад, {1,2,3}∪{2,3,4} = {1,2,3,4}.

Означення 1.6. Переріз (перетин) А і В (А∩В) – множина, що складається з тих і тільки тих елементів, які належать одночасно множині А та множині В (рис 1.1,б), тобто А∩В = {x | x∈A та x∈В}.

Наприклад, {1,2,3}∩{2,3,4} = {2,3}.

Означення 1.7. Різниця А і В або відносне доповнення В до А (А–В, A\B) – множина, що складається з тих і тільки тих елементів, які належать множині А та не належать множині В (рис 1.1,в), тобто

А\В = {x | x∈A та x∉В}. Наприклад, {1,2,3}\{2,3,4} = {1}.

Означення 1.8. Симетрична різниця (диз’юнктивна сума) А і В (А÷В, A⊕B) – множина, що складається з усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А (рис 1.1,г), тобто

А÷В = {x | (x∈A та x∉В} або (x∉A та x∈В)).

За означенням: А÷В = (А\В)∪(В\А).

Наприклад, {1,2,3}÷{2,3,4} = {1,4}.

Означення 1.9. Абсолютне доповнення або просто доповнення А (А’, A ) – множина, що містить усі елементи універсуму, за винятком елементів А (рис 1.1,д), тобто А’ = {x | x∉A).

За означенням: А’ = U\А.

 

 

 

А)    б)    в)

 

Г)    д)

Рис 1.1. Діаграми Венна.

(а – об’єднання, б – перетин, в – різниця, г – симетрична різниця, д – доповнення)

Операції  над множинами, як і операції над  числами, мають деякі властивості. Останні виражаються сукупністю тотожностей незалежно від конкретного  вмісту множин, що входять у них, і є підмножинами деякого універсуму U.

Для будь-яких множин А, В та С справедливі наступні властивості:

 ідемпотентність (самопоглинання)

1а) A∪A = A          1б) A∩A = A комутативність

2а) A∪B = B∪A         2б) A∩B = B∩A асоціативність

3а) A∪(B∪C) = (A∪B)∪C      3б) A∩(B∩C) = (A∩B)∩C дистрибутивність

4а) A∪(B∩C) = (A∪B)∩(A∪C)     4б) A∩(B∪C) = (A∩B)∪(A∩C) властивості ∅ та U

5а) A∪∅ = A          5б) A∩∅ = ∅

6а) A∪A’ = U          6б) A∩A’ = ∅

7а) A∪U = U          7б) A∩U = A

8а) ∅’ = U          8б) U’ = ∅ поглинання

9а) A∪(A∩B) = A         9б) A∩(A∪B) = A закони де Моргана

10а) (A∪B)’ = A’∩B’        10б) (A∩B)’ = A’∪B’ властивості доповнення, різниці та рівності

11. A∪B = U & A∩B = ∅ ⇔ B = A’
12. A’’ = A (інволютивність)
13. A\B = A∩B’
14. A÷B = (A∩B’) ∪(A’∩B)
15. A÷B = B÷A
16. (A÷B)÷C = A÷(B÷C)
17. A÷∅ = ∅÷A = A
18. A⊂B ⇔ A∩B = A ⇔ A∪B = B ⇔ A∩B’ = ∅
19. A=B ⇔ (A∩B’)∪(A’∩B) = ∅

Доведення цих співвідношень можна  ґрунтувати на означенні 1.3 та лемі 1.1, або доводити за допомогою побудови діаграм Венна для лівої та правої частин співвідношень. 

Доведемо, наприклад, співвідношення 3б: A∩(B∩C) = (A∩B)∩C. Нехай x∈A∩(B∩C) ⇒ x∈A, x∈B, x∈C ⇒ x∈(A∩B) і x∈C ⇒ x∈(A∩B)∩C і A∩(B∩C)⊆(A∩B)∩C. Одержання оберненого включення виконується аналогічно.

Тепер наведемо доведення для 4а: A∪(B∩C) = (A∪B)∩(A∪C). З одного боку, оскільки (B∩C) ⊆ B, то A∪(B∩C) ⊆ A∪В. Аналогічно B∩C ⊆ C і A∪(B∩C) ⊆ A∪C. Значить, A∪(B∩C) ⊆ (A∪B)∩(A∪C). З іншого боку, якщо x∈(A∪B)∩(A∪C), то x∈A∪B і x∈A∪C. Якщо x∈A, то x∈A∪(B∩C). А якщо x∉A, то x∈B і x∈C і тоді x∈B∩C. Отже,

(A∪B)∩(A∪C) ⊆ A∪(B∩C). Разом з отриманим раніше включенням маємо потрібну рівність.

Доведемо співвідношення  1а: A∪A = A.

A∪A = (A∪A)∩U = (A∪A)∩(A∪A’) = A∪(A∩A’) = A∪∅ = A. 

Доведемо  співвідношення 10а: (A∪B)’ = A’∩B’ за допомогою діаграм Венна. Спочатку побудуємо діаграму для (A∪B)’ – рис. 1.2, а. Множині A’ відповідає рис. 1.2, б. Множині В’ – рис. 1.2, в. Множині A’∩B’ відповідають частини, які заштриховані на рис. 1.2 б, в. Ця множина зображена на рис. 1.2, г. 

  а  

 

 

 

б  в  г

Рис. 1.2. Діаграми Венна для доведення  співвідношення (A∪B)’ = A’∩B’. (а - (A∪B)’, б - A’, в - В’, г - A’∩B’).

 

Отримали, що множини (A∪B)’ та A’∩B’ однаково зображуються на діаграмах Венна, тобто (A∪B)’ = A’∩B’.

Із  властивостей комутативності й асоціативності операції об’єднання випливає, що об’єднання кількох множин можна виконати, послідовно об’єднуючи їх, причому порядок  входження множин не впливає на результат. Отже об’єднання сукупності множин можна  подати співвідношенням 

n

А₁ ∪ А₂ ∪ ... ∪ А_n =  A_i .

i=1

Аналогічно на n множин узагальнюється операція перерізу:

n

А₁ ∩ А₂ ∩ ... ∩ А_n =  A_i .

i=1

Використовуючи  узагальнення операцій об’єднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад, закон де Моргана, який в узагальненому вигляді має вигляд:

n

n

n

n

A_i = A_i і A_i = A_i . i=1 i=1 i=1 i=1

Означення 1.10. Сукупність множин А₁, А₂, ..., А_n називається розбиттям множини А, якщо:

n

1. A_i = А.

i=1

2. А_і ∩ А_j = ∅, ∀i≠j.

Якщо умова 2 не задовольняється, то сукупність множин буде називатися покриттям.

Наприкінці наведемо приклади використання тотожностей 1-19 для спрощення складних виразів, які містять множини, аналогічно тому, як проводяться спрощення виразів  в елементарній алгебрі.

1. (A∩B∩C) ∪ (A’∩B∩C) ∪ B’ ∪ C’ = 

= [(A∪A’) ∩ B ∩ C] ∪ B’ ∪ C’ =	(4б)
= (U ∩ B ∩ C) ∪ B’ ∪ C’ =	(6a)
= (B ∩ C) ∪ B’ ∪ C’ =	(7б)
= (B ∩ C) ∪ (B ∩ C)’ =	(10б)
= U              2. (A∩B∩C∩D’) ∪ (A’∩C) ∪ (B’∩C) ∪ (C∩D) =	(6a)
= (A∩B∩C∩D’) ∪ [(A’∪B’∪D) ∩C] =	(4б)
= (A∩B∩C∩D’) ∪ [(A∩B∩D’)’ ∩C] =	(10б)
= [(A∩B∩D’) ∪ (A∩B∩D’)’] ∩ C =	(4б)
= U ∩ C =	(6a)
= C              3. (A∩B’)’ ∪ B =	(7б)
= (A’∪B’’) ∪ B =	(10б)
= (A’∪B) ∪ B =	(12)
= A’ ∪ (B∪B) =	(3a)
= A’ ∪ B	(1a)