1.2. Операції над множинами. Тотожні перетворення множин.
Визначимо основні операції над множинами. Нехай і – деякі множини.
1.
Об’єднанням
множин
і
(позначається
)
називається множина тих елементів, які
належать хоча б одній з множин
чи
,
тобто
.
2.
Перетином
множин
і
(позначається
)
називається множина тих елементів, які
належать обом множинам
та
одночасно, тобто
.
Аналогічно
визначаються операції об’єднання та
перетину будь-якої кількості множин.
Кажуть, що множини
і
не перетинаються, якщо
.
3. Різницею
множин
і
(позначається
або
)
називається множина тих елементів, які
належать множині
та не належать множині
,
тобто
.
4.
Доповнення
(заперечення)
множини
(позначається
)
називається множина тих елементів, які
не належать множині
,
тобто
.
Неважко бачити, що
.
5.
Симетричною різницею
множин
і
(позначається
або
)
називається множина, що складається з
усіх елементів множини
,
які не належать множині
,
та з усіх елементів множини
,
які не належать множині
,
тобто
.
Введені теоретико-множинні операції можна проілюструвати діаграмою Венна (рис. 1.1).
Рис. 1.1. Діаграма Вена.
На цій
діаграмі множини
і
– це множини точок кола та еліпса
відповідно. Тоді
складається з точок областей 1, 2, 3;
– точки області 2;
– точки області 1, а
– точки області 3;
– точки областей 3 та 4, а
складається з точок областей 1 та 4;
складається
з точок областей 1 та 3.
В алгебрі множин визначено такий пріоритет операцій:
1. .
2. .
3. .
4. .
5. .
Таким чином з множин за допомогою наведених вище операцій можна складати складні вирази. У таких виразах множини, з яких вони складаються, називають елементарними та використовують їх як змінні. Якщо два вирази зображають рівні множини при будь-яких значеннях елементарних множин, з яких вони складаються, то ці вирази називають еквівалентними або тотожніми.
Виділимо основні тотожності (закони) алгебри множин:
1. Комутативні закони:
1.1.
. 1.2.
. 1.3.
.
2. Асоціативні закони:
2.1.
.
2.2.
.
2.3.
3. Дистрибутивні закони:
3.1.
.
3.2.
.
4. Властивості порожньої та універсальної множин:
4.1.
.
4.2.
. 4.3.
. 4.4.
.
4.5.
.
4.6.
. 4.7.
. 4.8.
.
5. Властивості операцій множин із собою:
5.1.
.
5.2.
. 5.3.
. 5.4.
.
6. Властивості операцій множин із своїм запереченням:
6.1.
(закон виключеного третього).
6.2.
(закон протиріччя).
6.3.
.
6.4.
.
7. Закон інволюції (подвійного заперечення):
.
8. Закони елімінації (поглинання):
8.1.
.
8.2.
.
9. Закони де Моргана:
9.1.
.
9.2.
.
10. Властивості позбування різниці та симетричної різниці:
10.1.
.
10.2.
.
З наведених вище тотожностей виводяться такі важливі правила:
11. Правила викреслення:
11.1.
.
11.2.
.
12. Правила скліювання:
12.1.
.
12.2.
.
За допомогою наведених вище законів можна здійснювати тотожні перетворення виразів. Основною задачею, природно, є задача спрощення виразу, тобто перетворення його до еквівалентного виразу, який містить найменшу кількість операцій. І хоча єдиного правилу (алгоритму) спрощення виразів не існує, часто дозволяє значно спрощувати вирази така процедура:
За допомогою законів групи 10 позбавляємося від операції різниці та симетричної різниці. Таким чином вираз містить лише операції перетину, об’єднання та заперечення, причому заперечення можуть бути і над складним виразом (так звані „довгі” заперечення).
За допомогою використання один або декілька разів законів де Моргана позбавляємося „довгих” заперечень. Таким чином вираз містить лише операції перетину, об’єднання та заперечення, причому заперечення можуть бути лише над елементарними множинами.
За допомогою дистрибутивних законів (найчастіше за допомогою закону 3.1) „розкриваємо дужки” і перетворюємо вираз у об’єднання перетинів елементарних множин або їх заперечень. При цьому одночасно використовуються властивості 5.2, 6.2 та 4.1.
Послідовно застосовуючи закон поглинання 8.1, правило викреслення 11.1 та правила склеювання спрощуємо вираз.
Проілюструємо діє вищенаведеної процедури на наступному прикладі.
Приклад
1.1. Спростити вираз
.
■