Основні означення теорії множин.

Множина – це будь-яке об’єднання відмінних та визначених об’єктів нашої інтуїції або інтелекту, яке розглядається як єдине ціле.

Множина – це сукупність об’єктів, об’єднаних за певною ознакою.

Приклади:

- множина букв алфавіту;

- множина точок на прямій;

- множина двозначних натуральних чисел;

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

Множини позначають А, В, С, …

Об’єкти з яких складається множина називаються її елементами: а, в, с, …

Якщо елемент а належить множині А, то позначають: . Якщо елемент d не належить множині А, то позначають: .

Якщо елементами множини є числа, то її називають числовою:

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

- множина цілих чисел: Z

- множина раціональних чисел: Q

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

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

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

Кількість елементів множини називається потужністю:

Множина яка не має жодного елемента називається порожньою: Æ

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

Будь – яка множина є підмножиною самої себе. Порожня множина є підмножиною будь – якої множини. Тому у будь – якої множини є дві очевидних підмножини: порожня і сама ця множина.

Приклад: . Підмножини множини А: Æ.

Множина всіх підмножин множини А називається булеаном множини А і позначається: В (А).

Теорема: кожна множина А, яка містить п елементів, має 2^п підмножин.

{ Æ}

Теорема: порожня множина є підмножиною будь – якої множини.

Нехай дано дві множини: А і Æ. Доведемо, що Æ .

Припустимо, що твердження Æ хибне, тоді в порожній множині існує елемент який не є елементом множини А, а це неможливо, бо порожня множина не містить елементів. Значить умова Æ не є хибною.

 

Дві множини А і В називаються рівними, коли кожний елемент множини А є елементом множини В і навпаки: ,

Властивості множин:

§ рефлективність: ;

§ симетричність: ;

§ транзитивність:

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

Множина вважається заданою, якщо про будь – який об’єкт можна сказати чи належить він до даної множини чи ні.

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

Наприклад:

- множину студентів групи можна задати їх списком у журналі;

- С={червень, липень, серпень} – множина літніх місяців.

Спосіб задання множини переліком її елементів доцільно використовувати коли ця кількість не дуже велика. Так, множину всіх натуральних чисел, які менші 100000, можна задати переліком її елементів, але це займе дуже багато часу. У таких випадках використовують слідуючий запис: В={1; 2; 3; …; 99998; 99999}. Знак … можна використовувати тоді, коли зрозуміло, які елементи вони замінюють.

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

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

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

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

Для множин, які задаються характеристичною властивістю їх елементів, використовують запис: , де - скорочене позначення речення «елемент х має властивість Р»

Приклади:

1) - множина натуральних чисел, що при діленні на 3 дають остачу 1.

2) - множина всіх раціональних коренів рівняння.

3) - множина натуральних чисел між числами 5 і 10.

2. Дії над множинами.

 

1. Об’єднанням множин А і В називається множина, яка складається з усіх тих і тільки тих елементів, які належать хоча б одній з множин А або В.

Позначається:

Об’єднання множин можна виконувати з будь – якою кількістю множин:

Для об’єднання множин справедливі слідуючи властивості:

1) комутативна:

2) асоціативна:

3) Æ= А

4) ідемпотентність:

5) тоді і тільки тоді, коли

Діаграми (круги) Ейлера – Венна - це графічне зображення множин.

(Д. Венн – англійський математик, 1834-1932р.р. Л. Ейлер – швейцарський математик, 1707-1783р.р.)

 

 

 

Приклад:

 

2. Перетином множин А і В називається множина, яка складається з усіх тих і тільки тих елементів, які належать як множині А так і множині В (спільні елементи множин).

Позначається:

Дві множини А і В називаються непересічними, якщо Æ.

Дві множини А і В називаються пересічними, якщо Æ.

Перетин множин можна виконувати з будь – якою кількістю множин:

Для перетину множин справедливі слідуючи властивості:

1) комутативна:

2) асоціативна:

3) Æ=Æ

4) ідемпотентність:

5) тоді і тільки тоді, коли

Приклад:

 

3. Різницею множин А і В називається множина, яка складається з тих і тільки тих елементів, які належать множині А і не належать множині В.

Позначається:

 

 

 

Множина

Приклад:

4. Універсальна множина – це найбільша множина U, для якої вся решта множин є підмножинами.

На діаграмах Ейлера – Венна універсальну множину позначають прямокутником:

 

Для універсальних множин справедливі слідуючи співвідношення: ,

5. Доповненням множини А до універсальної множини U називається така множина, що визначається співвідношенням

Позначається:

Множини і не мають спільних елементів, тому Æ, . Очевидно, що множина А є доповненням до , а тому .

За допомогою доповнення множин можна також у зручному вигляді подати різницю множин .

Теорема:

Доведення: так як , то .

 

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

Алгебра множин являє собою сукупність тотожностей (рівностей).

Для будь – яких підмножин А, В і С універсальної множини U дійсними є такі рівності:

1) - комутативний закон

2) - асоціативний закон

3) - дистрибутивний закон

4) Æ= А

5) ()

 

1^’) - комутативний закон

2’) - асоціативний закон

3’) - дистрибутивний закон

4’)

5’) Æ

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

Доведемо рівність 3:

Доведення складається з двох частин:

1) Нехай , тоді або

а) якщо , то і , а отже

б) якщо , то і , а отже і , тому

2) Нехай , тоді і , тому або ( і ), а значить .

У загальному вигляді рівності 3 і 3’ можна подати у такому вигляді:

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

1) якщо і , то В =Æ.

2) Æ=U

3) - закон ідемпотентності

4)

5) - закон поглинання

6) - закон де Моргана

7) якщо і Æ, то

1’) якщо і , то .

2’) Æ

3’) - закон ідемпотентності

4’) Æ=Æ

5’) - закон поглинання

6’) - закон де Моргана

7’) якщо Æ і , то

Рівність алгебри множин, отримана з іншої рівності через заміну всіх входжень , , на Æ, Æ на називається двоїстою по відношенню до вихідної рівності.

Для будь – якого істинного твердження, що формується в термінах та Æ

двоїсте по відношенню до цього речення є також істинним. З цього випливає, що якщо є деяке твердження 1 – 7, то відповідне йому твердження 1’ – 7’ випливає на підставі двоїстості. Це дозволяє спрощувати різні складні вирази алгебри множин.

Узагальнення операцій над множинами:

1) перетин множин: при ;

2) об’єднання множин: при ;

3) формули де Моргана: , .

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

1. Що таке множина? Наведіть приклади різних множин.

2. Що таке скінченна та нескінченна множини? Наведіть приклади.

3. Яка множина називається порожньою?

4. Що таке підмножина?

5. Які є способи задання множин?

6. Що називається потужністю множини?

7. Що називається булеаном множини?

8. Що називається об’єднанням множин? (*)

9. Що називається об’єднанням множин? (*)

10. Що називається перерізом множин? (*)

11. Що називається різницею множин? (*)

12. Сформулювати і записати закони алгебри множин. (**)

 

Література:

О.А. Борисенко. Лекції з дискретної математики: навчальний посібник для вузів. Суми, СумДУ, 1999р. лекції 2 - 4

Ю.В. Нікольський, В.В.Пасічник, Ю.М. Щербина. Дискретна математика. Підручник для вищих навчальних закладів. Київ. 2007р. розділ 1. п. 1.12 – 1.13