Операції над множинами та їхні властивості

Для множин можна ввести ряд операцій (теоретико-множинних операцій), результатом виконання яких будуть також множини. За допомогою цих операцій можна конструювати із заданих множин нові множини.

Нехай A і B – деякі множини.

1.1.6.1. Означення 1.1.4. Об’єднанням множин A і B (позначають A È B) називають множину тих елементів, які належать хоча б одній з множин A чи B. Символічно операція об’єднання множин записується так

A È B = { x | x Î A або x Î B } або x Î A È B Û .

Наприклад, { a, b, c }È{ a, c, d, e }={ a, b, c, d, e }.

Властивості об¢єднання множин:

1) комутативність: A È B = B È A;

2) асоціативність: (A È B)È C = A È(B È C);

3) ідемпотентність A È A = A;

4) A ÈÆ = A;

5) A È Е = Е.

1.1.6.2. Означення 1.1.5. Перетином (перерізом) множин A і B (позначають A Ç B) називають множину, що складається з тих і тільки тих елементів, які належать множинам A і B одночасно. Тобто

A Ç B = { x | x Î A і x Î B } або x Î A Ç B Û .

Наприклад, { a, b, c }Ç{ a, c, d, e } = { a, c },

{ a, b, c }Ç{ d, e } = Æ.

Кажуть, що множини A і B не перетинаються, якщо A Ç B = Æ.

Операції об’єднання та перетину множин можуть бути поширені на випадок довільної сукупності множин { A_i | i Î N }. Так об’єднання множин A_i (записується A_i) складається з тих елементів, які належать хоча б одній з множин A_i даної сукупності. А перетин множин A (записується A_i) містить тільки ті елементи, які одночасно належать кожній з множин A_i.

Властивості перерізу множин:

1) комутативність: A Ç B = B Ç A;

2) асоціативність: (A Ç B)Ç C = A Ç(B Ç C);

3) дистрибутивність операції Ç відносно операції È: A Ç(B È C)=(A Ç B)È(A Ç C);

4) дистрибутивність операції È відносно операції Ç: A È(B Ç C)=(A È B)Ç(A È C);

5) ідемподентність: A Ç A = A;

6) A ÇÆ = Æ;

7) A Ç Е = A;

8) A Ç(A È B) = A;

9) A È(A Ç B) = A.

1.1.6.3. Означення 1.1.6. Різницею множин A і B (записується A \ B) називають множину тих елементів, які належать множині A і не належать множині B. Отже,

A \ B = { x | x Î A і x Ï B } або x Î A \ B Û .

Наприклад, { a, b, c } \ { a, d, c } = { b },

Z \ Z ₊= Z _–,

{ a, b } \ { a, b, c, d } = Æ.

Властивості різниці множин:

1) А \ А= Æ;

2) А \Æ =А;

3) А \ Е =Æ;

4) А \ В ¹ В \ А – різниця не комутативна;

5) (А \ В) \ С ¹ А \ (В \ С) – різниця не асоціативна;

6) (B È C) \ А = (В \ А) È (С \ А) – правий закон дистрибутивності операції \ відносно операції È;

7) (B Ç C) \ А = (В \ А) Ç (С \ А) – правий закон дистрибутивності операції \ відносно операції Ç.

1.1.6.4. Означення 1.1.7. Симетричною різницею множин A і B (записують A D B, A Å B або A ¸ B) називають множину, що складається з усіх елементів множини A, які не містяться в B, а також усіх елементів множини B, які не містяться в A. Тобто

A Å B = { x | (x Î A і x Ï B) або (x Î B і x Ï A)} або x Î A Å B Û .

Наприклад, { a, b, c }Å{ a, c, d, e } = { b, d, e },

{ a, b }Å { a, b } = Æ.

Властивості симетричної різниці:

1) комутативність: A Å B = B Å A;

2) асоціативність: (A Å B)Å C = A Å(B Å C);

3) дистрибутивність операції Ç відносно операції Å: A Ç(B Å C)=(A Ç B)Å(A Ç C);

4) A Å A = Æ;

5) A ÅÆ = А;

6) A Å B = (A \ В) È (В \ А).

Введені теоретико-множинні операції можна проілюструвати діаграмою (рис.1.1).

Рис. 1.1.

Тут множини A і B – це множини точок двох кругів.

Тоді A È B – складається з точок областей І, ІІ, ІІІ,

A Ç B – це область ІІ,

A \ B – область І,

B \ A – область ІІІ,

A Å B – області І і ІІІ.

1.1.6.5. Означення 1.1.8. Якщо зафіксована універсальна множина E, то доповненням множини A (яке є підмножиною універсальної множини E) називають множину всіх елементів універсальної множини, які не належать множині A. Записують .

Тобто

= { x | x Î E і x Ï A } або x Î Û x Ï A.

Неважко помітити, що = E \ A.

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

Властивості доповнення:

1) ;

2) ;

3) ;

4) ;

5) інволютивність: ;

6) ;

7) якщо А=В, то ;

8) якщо , то ;

9) правила (закони) де Моргана = Ç; = È Зазначимо, що правила де Моргана припускають узагальнення для сукупності множин:

; .

Приклад. Покажемо істинність однієї з наведених тотожностей – правила де Моргана.

= Ç.

Доведемо спочатку, що Í Ç.

Нехай елемент x Î, тоді x Î E \ (A È B), тобто x Ï A і x Ï B, звідси x Îі x Î, отже, x ÎÇ. Отже, за означенням підмножин:Í Ç.

Доведемо обернене включення:ÇÍ.

Припустимо x ÎÇ, це означає, що x Îі x Î, тобто x Ï A і x Ï B, тому x Ï A È B, отже x Î. Зі справедливості обох включень Í Çі ÇÍза законом антисиметричності для підмножин випливає істинність рівності = Ç.

Твердження доведено. <

Аналогічно можуть бути доведені всі інші наведені теоретико-множинні тотожності. Ці тотожності дають змогу спрощувати різні складні вирази над множинами.

Приклад. (A Ç B Ç C Ç)È(Ç C)È(Ç C)È(C Ç D) = (A Ç B Ç C Ç)È((ÈÈ D)Ç C) = = ((A Ç B Ç) È ())Ç C = E Ç C = C. <

Дата добавления: 2014-10-17