�Основні поняття теорії множин�Алгебра множин

Лекція 2

Інститут інформаційних технологій

Кафедра прикладної математики

Дискретна математика

Множина. Елементи множин

Множина – це деяка сукупність об’єктів (предметів, ідей, понять), що розглядається як єдине ціле. Самі об’єкти є елементами.

Елементи множини – це об'єкти, які утворюють цю множину, і можуть мати деякі властивості і знаходитися в деяких відношеннях між собою або з елементами інших множин.

​

2

Позначення

Множини позначають заголовними, а елементи множин - рядковими латинськими буквами або рядковими латинськими буквами з індексами.

Запис А={a,b,d,h} означає, що множина А складається з чотирьох елементів a, b, d, h.

Твердження, що скінчена множина A складається з n елементів, записується саме так:

​

A={a₁,a₂,...,a_n}.

3

Позначення

Приналежність елемента множини позначається символом ∈: a ∈ A (читається: елемент а належить множині А).

У противному випадку позначають a ∉ A (читається: елемент а не належить множині А).

Елементами множин можуть бути інші множини, тоді ці елементи можуть позначатися заголовними буквами. Для деяких множин у ДМ використовують сталі позначення N, Z, Q, R, C.

4

Позначення

Приклад.

A = {D,C},

D={a, b},

C={c, d, e}.

При цьому D∈A, C∈A, проте a∉A и с∉A.

​

Приклад.

A = {{x,y},z}.

Цей запис означає, що множина A містить

два елементи: множину {x,y} та елемент z.

5

Скінчені і нескінчені множини

Множина називається скінченною, якщо вона містить скінченну кількість елементів і нескінченною, якщо вона містить нескінченну кількість елементів.

Приклади. Множина A={1,2,3,4,5,6,7,8,9,0} цифр у десятковій системі числення є скінченною.

В={{1}, {2}, 0}.

Множина точок кола є нескінченною.

​

​

6

Упорядковані множини

• Упорядкованою вважають таку множину, у якій є важливим порядок слідування елементів.

Наприклад, упорядкованою є множина, в якій кожен елемент має свій порядковий номер.

• Позначають упорядковану множину, як правило, або круглими, або трикутними дужками.

​

A=<1,2,3>, у загальному випадку : A=<a₁,a₂,..,a_n>, n∈N;

В=(а,b,с).

7

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

• Перерахуванням елементів

А = {a₁, a₂,... , a_n}.

Приклад.

Множина студентів-відмінників у групі позначимо Z_1а представимо її перерахуванням:

Z_1а = {Іванов, Петров, Сидоров}

​

8

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

• Через визначальну властивість

Множина Х = {х | Р(x)}, где Р(х) означає, що елемент х має властивість P(x).

Приклад.

Множину N₁₀ усіх натуральних чисел, що строго менше 20-ти, можна представити так:

N₁₀={x | x∈N, x<20}.

9

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

• Рекурсією
• графіком (таблицею)

Множина значень рекурсивної функції є рекурсивно - заданою множиною

F={f₁, f₂, f₃, …}.

f₁=1

f₂=1

……………………….

f_n= 3f_n-2+ f_n-1, n=3,4,…

Так, f₃ = 3f₁+f₂= 3×1+1=4 , f₄=3f₂+f₃=3×1+4=7 і т. і.

​

10

Підмножина

Множина А, усі елементи якої належать множині В, називають підмножинами множини В.

​

Позначення: A⊂B; A⊆B.

​

Приклад.

R – множина дійсних чисел;

N – множина натуральних чисел.

Множина N є підмножиною множини R.

11

Рівність множин

Неупорядковані множини рівні (рівнопотужні), якщо вони містять однаковий набір елементів.

​

Позначають: A=B.

Якщо множини не рівні, це позначається A≠B.

12

Рівність множин

А=В тоді і тільки тоді, якщо із умови x∈A слідує x∈B та з умови y∈B слідує y∈A.

Приклад.

Нехай задано множини

A = {1,2,3,4,5};

B – множина натуральних чисел від 1 до 5;

С = {c | 1≤ c ≤ 5, c∈N};

D = {4,1,5,2,3}.

Ці множини містять один набір елементів, тому A=B=C=D

13

Рівність множин

Приклад.

Нехай задано множини:

A={Іванов, Петров, Сидоров};

B={Іванов, Петров, Сидоров}.

A=B, якщо йдеться про тих же самих людей.

Інакше A≠B.

14

Рівність множин

Приклад.

Нехай A – множина остач, що отримуються при послідовному діленні натуральних чисел

{3, 4, 5, 6,…} на 3:

A={0, 1, 2, 0, 1, 2, 0, 1, 2, 0, …}.

Ця множина містить всього три елементи:

0, 1, 2.

Тому її можна записати у вигляді:

A={0, 1, 2}.

15

Потужність множин

Число елементів у скінченній множині М називають потужністю М і позначають |M|.

Приклад.

Нехай задано множину A={x| 4≤x≤12, x∈N},

тоді |A|=9.

16

Приклад.

B – множина всіх шахових фігур,

С – множина всіх шахових фігур, що якими користувалися при проведенні гри.

|B|=6 (пішак, тура, слон, кінь, ферзь, король)

|С|=32 (16 білих і 16 чорних).

​

​

Строге і нестроге включення

Нестроге включення позначають А⊆В, та означає, що А – підмножина множини В, і можливо співпадає з В.

Строге включення позначають А⊂В, та означає, що А – підмножина множини В, і не співпадає з B. А⊂В читають: “А належить (або не включається у) до В” .

Зауваження. Не можна вважати рівносильними поняття відношення приналежності і включення однієї множини до іншої за причини різної смислової інтерпретації.

17

Строге і нестроге включення

Виконання співвідношень А ⊆ В і В ⊆ А є можливим за умови при А = В.

А = В, якщо А ⊆ В і B ⊆ А.

Ці співвідношення є ознакою рівності множин через відношення включення.

Строге включення представляють співвідношенням A⊂B, A≠B.

18

Строге і нестроге включення

Приклад.

X – множина студентів групи І,

Y – множина відмінників групи І.

Тоді Y ⊆ X,

Z – множина студентів усіх потоків 1 курсу.

Тоді X ⊂ Z. Включення X до Z є строгим.

Для трьох множин А, В, С справедливі такі співвідношення:

19

Універсальна множина

Універсальна множина − це така множина, що містить всі можливі (допустимі) підмножини (елементи).

Універсальна множина позначається символом U.

​

Універсальна множина U може відрізнятися для кожної окремої задачі і визначається умовою задачі.

20

Порожня множина

Порожньою називають таку множину, яка не містить ніяких елементів.

Порожня множина позначається спеціальним символом ∅.

Операції з порожньою множиною:

​

Порожня множина ∅ є підмножиною будь-якої множини, тобто ∅ ⊆ А, де А – будь-яка множина.

21

Порожня множина

Порожня множина - це також множина, тому, якщо деяка множина A не містить жодного елементу, то A=∅; |A|=0.

Запис A={∅} означає, що A містить один елемент – ∅, |A|=1.

​

22

Множина-степінь (булеан)

Множина всіх підмножин множини X називається множиною-степенем X або булеаном і позначається P (X).

Для довільної множини X з n елементів її множина-степінь P (X) містить 2ⁿ елементів:

| P (X)| = |2^X| =2 ^{|X |} = 2ⁿ

Приклад..

A={a, b, c}.

2^A={∅,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}

Порожня множина має тільки одну підмножину – саме порожню множину, тому P(∅)={∅}.

23

Геометрична інтерпретація множин : �діаграми Венна

Побудова діаграм Венна полягає в поділі площини на 2ⁿ підмножин за допомогою n замкнутих фігур (де n – число зображуваних множин). Кожна фігура на діаграмі представляє окрему множину з 2ⁿ підмножин.

​

24

Діаграми Венна для двох множин

Діаграма Венна для двох множин A і B виглядає таким чином.

​

25

Діаграми Венна для трьох множин

Діаграма Венна для трьох множин A, B і C виглядає таким чином.

​

26

Діаграми Венна для чотирьох множин

Діаграму Венна для чотирьох множин A, B, C і D можна зобразити таким чином.

​

27

Кола (круги) Ейлера

Індивідуальні відношення між заданими множинами зображують за допомогою кругів Ейлера (www.youtube.com/watch?v=unXIsqKQLOg).

28

А = {1, 4, 6};

В = {1, 5, 8};

Загальний елемент – 1

A∩B

А = {1, 4, 6};

В = {1, 6};

B⊆A

​

А = {1, 4, 6};

С = {3, 5, 8};

Немає спільних елементів A і B.

A≠B

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

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

29

Операції над множинами

Об’єднання (сума) A∪B є множина, яка містить всі елементы, що належать або A, або B, або A та B водночас.

A ∪ B={x | x∈A або x∈B}.

30

A∪B

Операції над множинами

Приклад .

Нехай дано множини:

А={a, b, m};

В={m, n, c, p}.

​

А∪В=

31

{a, b, c, m, n, p}

Операції над множинами

Перетин (добуток) A∩B є множиною, що містить тільки ті елементи, що належать A і B водночас.

A∩B={x | x∈A і x∈B}.

32

A∩B

Операції над множинами

Приклад .

Нехай дано множини:

​

А={a, b, m};

В={m, n, c, p}.

​

А∩В =

33

{m}

Операції над множинами

Доповнення (заперечення) Ā ( “не А”) є множиною U\A.

34

= {x | x ∉ A}.

Операції над множинами

Приклад .

Z = {…,-2,-1,0,1,2,…}.

У цій задачі U=Z.

нехай Z_- – множина від’ємних чисел та 0, тоді:

Z_- = {… -2, -1, 0}.

Доповненням до множини Z_- є множина натуральних чисел:

N={1,2,…}.

​

35

Операції над множинами

Різниця A\B є множина, що містить усі елементи A, і не належить B.

А\В≠В\А

36

A\B

A\B =

A ∩B

А\В={x|x∈A, x∉B};

Операції над множинами

Приклад.

Нехай дано множини:

А={a, b, m};

В={m, n, c, p}.

​

А \ В =

37

{a,b}

В \ А =

{n,c,p}

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

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

1. A

2. A∩B

3. A∪B

4. A\B

​

38

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

Приклад.

Розставити дужки (визначити послідовність виконання операцій) у формулі:

39

E=A\B∪ (A)∩D\B.

E=A\B∪((A)∩D)\B.

E=A\(B∪((A)∩D))\B.

E=(A\(B∪((A)∩D)))\B.

E=A\B∪A∩D\B

Закони алгебри множин

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

A∪B=B∪A

A∩B=B∩A

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

A∪(B∪C)=(A∪B)∪C

A∩(B∩C)=(A∩B)∩C

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

A∪(B∩C)=(A∪B)∩(A∪C)

A∩(B∪C)=(A∩B)∪(A∩C)

40

Закони алгебри множин

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

41

Закони алгебри множин

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

A∪A=A

A∩A=A

6. Закон інволюції (подвійного заперечення)

7. Закон заперечення

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

42

Закони алгебри множин

9. Закон елімінації (поглинання)

A∩(A∪B)=A

A∪(A∩B)=A

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

43

Закони алгебри множин

Приклад.

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

А∩ (В∪С)=(А∩В)∪(А∩С).

​

44

Закони алгебри множин

Продовження прикладу.

45

В∪С

А∩ (В∪С)

А∩ (В∪С)

Закони алгебри множин

Продовження прикладу.

46

(А∩В)

(А∩С)

(А∩В)∪(А∩С)

(А∩В)∪(А∩С)

Закони алгебри множин

Приклад.

Записати формулу, що відповідає заштрихованій частині діаграми Венна

47

(А∪В)

​

У результаті отримали формулу

(А∪В)\С

(А∪В)\С

Закони алгебри множин

Приклад.

Спростити вираз:

48

Відповідь:

Взаємно-однозначна відповідність

Взаємно-однозначною називається така відповідність між множинами A та B, при якій кожному елементу a∈A відповідає один і тільки один елемент b∈B і кожному елементу b∈B відповідає один і тільки один елемент a∈A.

​

Функція, що визначає взаємно-однозначну відповідність називається бієктивною функцією або бієкцією.

49

Еквівалентні множини

Множини A і B називаються еквівалентними (A~B), якщо між ними існує бієкція (принаймні одна).

Еквівалентні множини називають рівнопотужними, що позначається так:

|A| = |B|.

​

Еквівалентними один одному виявляються усі скінченні множини з однаковим числом елементів n (потужність кожної з цих множин дорівнює n).

50

Зліченні множини

Множина A називається зліченною, якщо вона еквівалентна натуральному ряду N (A~N).

​

За допомогою бієкції ϕ=N→A можна перерахувати всі елементи з A, забезпечивши їх індексами. Можна стверджувати, що:

A = {a_n}, n=1,2,…,∞.

51

Зліченні множини

Множина парних натуральних чисел N_ч={2,4,…,m,…}, всіх натуральних чисел N={1,2,…,n, …}, цілих чисел Z та раціональних чисел Q послідовно вкладені:

N_ч ⊂ N ⊂ Z ⊂ Q.

Хоча нижче подані множини не є рівними, вони еквівалентні одна одній, тобто, мають однакову потужність і є зліченними:

|N_ч| = |N| = |Z| = |Q|.

​

52

Нескінченні множини.�Зліченні, континуальні множини

Існують нескінченні зліченні множини, і їх потужність вважають більшою, ніж |N|.

​

Множина точок відрізку [0, 1] = {x∈R; 0≤x≤1} не є зліченною (теорема Г. Кантора). Її потужність називають континуум і позначають малою літерою c: |[0, 1]|=c.

​

Множину [0, 1] і будь-яку еквівалентну множину називають континуальними.

53

Нескінченні множини.�Зліченні, континуальні множини

На осі дійсних чисел R континуальними (тобто еквівалентними одна одній й відрізку

[0, 1]) є множини:

• [a,b],
• (a, b), при будь-якому a<b;
• (0, +∞);
• множина (– ∞, + ∞), що дорівнює R.

Континуальними є також множини точок будь-якого квадрата і кола на площині R², паралелепіпеда і кулі у просторі R³ .

54