Тема 1.2 Основні поняття теорії множин. Операції над множинами.

Теоретико-множинні представлення — опис досліджуваної системи, процесів засобами теорії множин, тобто як множини взаємозалежних і/чи взаємодіючих частин – елементів. Зв'язок між елементами задаються через відносини. Множини, елементи, відносини характеризуються певними властивостями і набором припустимих операцій над ними.

Склад об'єкта дослідження може бути представлений у вигляді дискретної множини. Множина - основне поняття в теорії множин, що вводиться без визначення. Про множину відомо як мінімум, то, що воно складається з елементів. Приналежність елемента а множині М позначається ( «а належить М»), неприналежність - чи . Іноді важливий порядок переліку елементів множини, тоді говорять про впорядковану множину.

Множина А називається підмножиною множини В (позначається ), якщо , елемент з А є елементом В (рис 1.1). Якщо та A = B, тоді А називається строгою (власним) підмножиною (позначається ).

Змістовні приклади множин і їхні можливі позначення:

А - множина співробітників фірми "Елегант";

M₁ - множина всіх операцій (робіт) по зборці комп'ютера;

М₂ — множина видів послуг, наданих фірмою "Силует";

N- множина натуральних чисел 1, 2, 3,...;

N₁₀₀ - множина натуральних чисел, що не перевершують 100;

R - множина всіх дійсних чисел і т.д.

Два визначення рівності множин:

I. Множини A та В рівні (А = В), якщо їхні елементи збігаються.

II. Множини А та В рівні, якщо та .

Множина, що складається з кінцевого числа елементів, називається кінцевою, у противному випадку - нескінченною (наприклад, множини N, R — нескінченні множини). Число елементів у кінцевій множині М називається його потужністю і позначається ½М½.

Множина потужності 0, тобто в якій немає елементів, називається пустою (позначається Æ): | Æ | =0. Прийнято вважати, що порожня множина є підмножиною будь-якої множини.

Булеан b(U) – це множина всіх підмножин, що складаються з елементів множини U.

Способи завдання множин:

1. Перерахуванням, тобто списком своїх елементів. Списком можна задати лише кінцеві множини. Позначення списку - у фігурних дужках. Наприклад, множина А пристроїв домашнього комп'ютера, що складається з процесорного блоку а, а також периферійних пристроїв В (монітора b, клавіатури с і принтера d), може бути представлено списком:

А = {а, В} чи А = {а, b, с, d}.

(Завдання типу N = 1,2,3,... - не список, але лише припустима умовна позначка.)

2. Процедурою, що породжує. Вона описує спосіб одержання елементів множини з вже отриманих елементів або інших об'єктів. У такому випадку елементами множини є всі об'єкти, що можуть бути побудовані за допомогою такої процедури. Наприклад, множина всіх цілих чисел, що є ступенями двійки , nÎN, а N-множина натуральних чисел, (припустиме позначення = 1,2,4,8,16,...) може бути представлено процедурою, що породжує, заданими двома правилами, що називаються рекурсивними, чи індуктивними:

– 1 Î М₂ⁿ;

– якщо т Î М₂ⁿ, тоді 2т Î М₂ⁿ.

3. Описом характеристичних властивостей множини, якими повинні володіти його елементи; позначається:

чи .

(«Множина М складається з елементів х таких, що х має властивість Р»). Наприклад, множина А периферійних пристроїв персонального комп'ютера PC може бути визначено:

А = {х: х - периферійний пристрій персонального комп'ютера PC}.

Якщо властивість елементів множини М може бути описано коротким вираженням, це спрощує його символьне представлення. Наприклад, множина усіх натуральних парних чисел М_2п може бути представлено:

.

Надійним способом точно описати властивість елементів даної множини є завдання процедури, що розпізнає. Вона повинна встановлювати для будь-якого об'єкта х, чи володіє він даною властивістю Р (і, отже, належить множині) чи ні. Наприклад, що розпізнає процедурою для множини А всіх співробітників фірми "Квант", що мають посвідчення фірми, є перевірка його наявності. Тоді множина А може бути представлене більш точно: “А - множина всіх співробітників фірми «Квант», що мають відповідне посвідчення фірми“.

Ще приклад: для опису характеристичної властивості елементів множини усіх цілих чисел, що є ступенями двійки ("бути ступенем двійки"), що дозволяє процедурою може служити будь-як метод розкладання цілих чисел на прості множники. Тоді якщо а = 1 чи якщо а = 2 х 2 х... х 2 = 2ⁿ, а Î N.

Приклад 1.Задати різними способами множина N усіх натуральних чисел: 1,2, 3,...

Списком множину N задати не можна через її нескінченність.

Процедура, що породжує, містить два правила:

a) 1 Î N; 6) якщо n Î N, то п+1Î N.

Опис характеристичної властивості елементів множини N:

N= {x: х - ціле позитивне число}.

Приклад 2.Задати різними способами множину М усіх парних чисел 2,4, 6,..., що не перевищують 100.

M_2n={2,4,6,...,100}.

а)2Î М_2n ; б) якщо nÎ N, те (п+2)Î М_2n ; в) n < 98.

М_2п= {п: п - ціле позитивне число, що не перевищує 100} чи

М_2п ={n : n Î N і n/2ÎN, n< 100}.

Приклад 3.Нехай U= {а, b, c}. Визначити в явному вигляді (перерахуванням своїх елементів) булеан b(U) - множина всіх підмножин, що складаються з елементів множини U. Яка потужність множини b (U)?

b(U)= {Æ, {а}, {b}, {с}, {а,b), {а,с}, {b, с}, {а, b, с}}. Потужність |b(U)| = 8.