Відношення приналежності та включення

Множина – одне з первинних понять у математиці. Будь-яке визначення в дискретній математиці можна вивести за допомогою поняття множини. Під множиною слід розуміти об'єднання в одне ціле об'єктів, що добре розрізнюються інтуїцією або думкою. Термін ”множина” має синоніми – ”сукупність”, “набір”. Об'єкти, які утворюють множину, називаються його елементами. Як правило, множину утворюють елементи однієї природи. Наприклад, числа (натуральні, цілі, дійсні), букви латинського алфавіту.

Відношення приналежності. Приналежність об'єкта множині позначається за допомогою символу : .

Відношення включення. Говорять, що множина є підмножиною множини , якщо кожний елемент є елементом , тобто належить (виконується поелементна приналежність):

,

при цьому – підмножина множини ; – надмножина множини (рис. 1.1, а).

Відношення строгого включення не припускає співпадіння множин й позначається символом : (див. рис. 1.1, а).

Множини рівні , якщо вони складаються з тих самих елементів. Якщо й (), то (рис. 1.1, б).

а б

Рисунок 1.1 – Відношення включення

Таким чином, відношення приналежності встановлює зв'язок між множиною і його елементами, а відношення включення – між двома множинами. Нестроге включення допускає рівність двох множин.

Приклад 1.1. Дано множина (рис. 1.2). Які з наступних тверджень правильні?

Рисунок 1.2 – Структура множини А із прикладу 1.1

Розв’язок: – правильне, тому що в множині є елемент 2;

– правильне, тому що в множині є елементи 1, 2, тобто , ;

– правильне, тому що в множині є елемент 3, тобто ;

– правильне, тому що в множині є елемент {3};

– не правильне, оскільки в множині немає елемента 4;

– правильне, тому що в множині є елемент ;

– не правильне, оскільки в множині немає елемента 4, тобто .

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

Множину можна задати декількома способами, а саме:

1) перерахуванням елементів: , ;

2) використанням характеристичної властивості:

M={x | x, що мають властивість Q} або ;

; ;

3) за допомогою процедури, що породжує (породжувальна процедура – операції над множинами) ;

4) графічно за допомогою діаграм Ейлера (рис. 1.3):

Рисунок 1.3 – Діаграма Ейлера для ілюстрації множини

Визначення 1.1. Булеан множини – є множина всіх підмножин множини , при цьому називається універсумом (універсальною множиною або простором) і часто позначається .

Визначення 1.2. Потужність множини (кардинальне число) – кількість елементів множини. Потужність множини позначається або . Потужність булеана визначається формулою:

. (1.1)

Кінцева множина містить кінцеве число елементів.

Порожня множина не містить жодного елемента, його потужність дорівнює нулю: .

Приклад 1.2. Дано: множина . Знайти: .

Розв’язок. Потужність множини визначається кількістю елементів: . Потужність булеана множини А обчислюється за формулою (1.1): . Булеан множини містить порожню множину – ; всі одноелементні підмножини множини – , , ; всі двоелементні підмножини множини – , , ; триелементну підмножину, що співпадає із самою множиною – :

.

Таким чином, булеан множини А складається з порожньої множини, трьох одноелементних підмножин множини А, трьох двоелементних підмножин множини А та самої множини А.

Визначення 1.3. Множина А називається власною підмножиною множини В, якщо А є підмножиною множини В, а В не є підмножиною множини A.

Порожня множина є підмножиною будь-якої множини.Універсум Uабо універсальну множинуможна розглядати як надмножину всіх множин: .

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

У прикладі 1.2 універсумом є множина А як надмножина всіх множин булеана. Порожня множина і сама множина є невласними, інші множини – елементи булеана – власні.

1.3 Алгебра множин Кантора

Визначення 1.4. Алгебра А є сукупністю носія N і сигнатури S: . Сигнатура задає набір операцій над елементами з носія, які діють за певними правилами.

Множини у сукупності з операціями об'єднання , перетинання й доповнення – або утворюють алгебру множин Кантора . Порядок операцій: 1) –; 2) ; 3) . Дані операції утворюють базис в алгебрі множин Кантора. Інші операції (різниця \ і симетрична різниця ) можуть бути виражені через базисні.

Операції над множинами вводяться за такими правилами:

1. Перетинання складається із всіх елементів , які належать одночасно двом множинам і (рис. 1.4, а):

. (1.2)

2. Об'єднання складається із всіх елементів , які належать множині або множині (рис. 1.4, б):

. (1.3)

3. Доповнення визначається через теоретико-множинну різницю (рис. 1.4, в):

. (1.4)

4. Вирахування (теоретико-множинна різниця, рис. 1.4, г) складається із всіх елементів , які належать зменшуваній множині , але не належать віднімаючій множині

. (1.5)

Зв’язок з базисними операціями перетинання й різниці встановлюється за формулою:

. (1.6)

5. Симетрична різниця (рис. 1.4, д):

. (1.7)

Для симетричної різниці мають місце формули, що встановлюють зв’язок з базисними операціями:

. (1.8)

Діаграма Ейлера для симетричної різниці зображено на рис. 1.4, д.

Рисунок 1.4 – Ілюстрація результатів теоретико-множинних

операцій на діаграмах Ейлера

1.4 Закони й тотожності алгебри множин

1. Комутативність:

, . (1.9)

2. Асоціативність:

, . (1.10)

3. Дистрибутивність (розподільний закон):

, . (1.11)

4. Ідемпотентність (повторення, тавтологія):

. (1.12)

5. Операції з константами (як константи виступають порожня й універсальна множини):

, , , . (1.13)

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

. (1.14)

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

. (1.15)

8. Інволюція:

. (1.16)

9. Закон Де Моргана:

, . (1.17)

10. Елімінація (поглинання):

, . (1.18)

11. Склеювання:

, . (1.19)

12. Закони Порецького:

, . (1.20)

Для об'єднання й перетинання множин справедливі такі формули обчислення потужності:

, . (1.21)

Порожня й універсальна множини вводяться для замкнутості теоретико-множинних операцій. Це означає, що результат застосування цих операцій є елемент тієї ж природи, що й об'єкти з носія. Таким чином, алгебра множин Кантора замкнута щодо введених операцій.

1.5 Контрольні запитання

1. Як визначається множина?

2.Чи можуть повторюватися елементи множини?

3.Які існують способи задання множин?

4. Чому дорівнює потужність множини?

5. Чим характеризується невласна підмножина?

6.Яка множина є власною?

7. Чи є множина невласною підмножиною самого себе?

8. Коли дві множини є рівними?

9. Які теоретико-множинні операції є базисними?

10. Як визначається пріоритет операцій алгебри Кантора?

11. Чи є поняття потужності множини і його кардинального числа ідентичними?

12. Як формулюються закони й тотожності алгебри множин?

13. Як ілюструються теоретико-множинні операції за допомогою діаграм Ейлера?

14. Яка множина називається булеаном?

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

2 ВІДПОВІДНОСТІ. ФУНКЦІЇ. ВІДОБРАЖЕННЯ