1.4. Операції на множинах

Об'єднаня, перетин, різниця, доповнення

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

1 . Об'єднання (сума) А  В є множина, що складається з тих і тільки тих елементів, які входять або до А, або до В, або до А і В одночасно (рис. 1.7).

Приклад. Нехай дані множини А = {а, b, т}; В = {т, с, р}, тоді їх об'єднання А  В = {а, b, с, т, р}.

2. Перетин (добуток) А  В є множина, що містить тільки елементи, які належать до А і В одночасно (рис. 1.8).

Приклад. Для множин А і В з попереднього прикладу А  В = {т}.

3. Різниця А\В є множина, що складається в точності з усіх елементів А, які не належать до В (рис. 1.9).

Приклад. Для вищерозглянутих тут множин А і В

А\В = {а, b}.

4. Доповнення (заперечення) (читається «не А») є множина U\A (рис. 1.10).

Різницю множин можна виразити через операції заперечення та перетину таким чином:

.

Приклад. Виконаємо дії на множині цілих чисел Z ={..., -2, -1, 0, 1, 2, ...} та множині Z_- = {...,-2,-1,0}. Доповненням до множини Z_- є множина натуральних чисел N = {1, 2, ...}: = N.

Запитання

1. Дайте визначення операціям на множинах:

1. Наведіть самостійно приклади множин і виконайте кожну з чотирьох операцій.

1. При виконанні якої операції використовується універсальна множина?

2. Чи можуть деякі з цих операцій бути виражені одна через іншу? Яким чином?

Завдання

1. Для множин А = {1, 2, 3, 4, 5}, В = {0, 3, 6} знайдіть:

   1. ;

   2. ;

   3. ;

   4. .

2. За допомогою діаграм Венна доведіть, що .

3. Нехай А — деяка множина. Знайдіть значення виразів:

   1. A  ;

   2. A  A;

   3. A\;

   4. A  U;

   5. A  ;

   6. A  A;

   7. \ A;

   8. A  U.

4. Знайдіть множини А і В, якщо А\В = {1, 5, 7, 8}, B\А ⁼ {2, 10}, А  B = {3, 6, 9}.

5. Нехай А, В і С — множини. Покажіть, що:

   1. (A  B)  A;

   2. A  (A  B);

   3. (A\B)  A;

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

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

6. Зобразіть за допомогою діаграм Венна перетин та об'єднання трьох множин.

7. Доведіть, що А  В правильно тоді і тільки тоді, коли правильно .

8. Які висновки можна зробити про множини А і В, якщо правильна одна з таких рівностей:

   1. A  B = A;

   2. A  B = A;

   3. A\B = A;

   4. A\B = B\A.

1.5. Алгебра множин

Пріоритет операцій, тотожності алгебри множин, тотожні перетворення виразів

Множина 2^U всіх підмножин універсальної множини U із заданими на ньому чотирма операціями складає алгебру множин.

У загальному випадку алгебру може складати будь-який клас cr  2^U підмножин універсальної множини U, замкнений відносно всіх чотирьох операцій (див. п. 4.8). Визначення алгебри, що не містить надмірних (точніше, залежних) обмежень, виглядає таким чином.

Визначення

Клас множин cr називається алгеброю (множин), якщо:

1. U  cr.

2. З А, В  cr виходить A  В  cr.

3. З А, В  cr виходить А\В  cr.

Алгебра множин широко застосовується у програмуванні, зокрема, при роботі з різноманітними базами даних і становить основу для побудови багатьох математичних структур. Разом з тим, що алгебра множин має основоположне значення в математиці, вона дуже проста і близька до реального життя. Ми щодня застосовуємо операції та закони алгебри множин, не замислюючись над цим. Ми відраховуємо з множин задач, які потрібно розв'язати, множину розв'язаних та беремося до розв'язання решти. Із них ми, вірогідно, в першу чергу виберемо ті, які відносяться до множини легких. Ми готуємо сніданок, визначаючи перетин множини наявних продуктів з множиною продуктів, які нам подобаються. Все наше життя проходить серед множин, які якось взаємозв'язані.

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

Пріоритет операцій в алгебрі множин такий:

1. .

2. A  B .

3. A  B .

4. А\В.

Розглянемо приклад.

Приклад. Нехай треба розташувати дужки (визначити послідовність виконання операцій) у формулі:

.

З урахуванням пріоритетів це слід зробити так:

.

В алгебрі множин cr автоматично виконуються такі тотож­ності, які дозволяють віднести cr до класу так званих булевих алгебр (див. розділ 4):

1. Комутативні закони

1.1. .

1.2. .

2. Асоціативні закони

1. .

2. .

3. Дистрибутивні закони

1. .

2. .

4. Властивості порожньої та універсальної множин

4.1. A   = А.

4.2. A  U = A.

4.3. A  U = U

4.4. А   = .

5. Закони ідемпотентності

5.1. A  A = А

5.2. А  А = А.

6. Закон інволюції

.

7. Закон протиріччя

.

7. Закон виключеного третього

.

7. Закон елімінації

9.1.

9.2. .

10. Закони де Моргана

10.1.

10.2. .

Усі наведені тотожності можна наочно зобразити і довести, використовуючи діаграми Венна.

Приклад. Довести за допомогою діаграм Венна дистрибутивний закон 3.2.

.

Проілюструємо на діаграмі ліву частину тотожності, виконавши спочатку об'єднання множин В і С, а потім перетин з А (рис. 1.11).

ВС А(ВС)

Рис. 1.11 Побудова діаграми Венна для

Тепер побудуємо діаграму для правої частини тотожності - (рис. 1.12.)

Рис. 1.12 Побудова діаграми Венна для

Як бачимо, праві діаграми на рис. 1.11 і 1.12 співпадають, отже тотожність 3.2 справедлива.

За допомогою тотожностей алгебри множин можна здійснювати еквівалентні перетворення виразів - Розглянемо такі перетворення на прикладі.

Приклад. Спростити вираз

(застосуємо закон де Моргана)

(асоціативність і комутативність)

(застосуємо закон ідемпотентності)

(застосуємо дистрибутивний закон)

(згідно з властивостями порожньої множини)

=  .

Відповідь:

Запитання

1. Розташуйте операції алгебри множин відповідно до їх пріоритетів.

2. Назвіть тотожності алгебри множин, запишіть відповідні формули.

3. Яким чином можна графічно зобразити та довести закони і тотожності алгебри множин? Наведіть приклад такого доведення.

4. Яким чином виконуються еквівалентні перетворення формул алгебри множин? Наведіть приклади.

Завдання

1. Доведіть за допомогою діаграм Венна:

а) асоціативні закони;

б) дистрибутивні закони;

в) властивості порожньої і універсальної множин.

2. Доведіть за допомогою еквівалентних перетворень закони елімінації.

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

4. Спростіть вирази:

а) ;

б) ;

в) ;

г) .

5. В якому відношенні знаходиться множини А і В, якщо А\В = В\А = ?

5. Чи є алгеброю клас множин, замкнених відносно:

а) операцій , ;

б) операцій , доповнення.