Включення та рівність множин

Міністерство освіти та науки України

Київський національний університет технологій та дизайну

М.К.МОРОХОВЕЦЬ

Основи Дискретної математики

МНОЖИНИ ТА ВІДНОШЕННЯ

Конспект лекцій

Для студентів напрямку “Комп’ютерні науки” 6.0402

КИЇВ КНУТД 2005

УДК 51.681.3517

Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402

/ Автор М.К.Мороховець. – К.: КНУТД, 2005. – 52 с. Укр.мовою.

У даному матеріалі викладено основні відомості з теорії множин, розглядаються поняття відношення, відображення. Наводяться приклади розв’язання задач. До кожного розділу подаються задачі та вправи.

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

Бібл. 6 найм.

Лекція 1. Поняття множини. Операції над множинами

Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів нашої інтуїції або інтелекту, які розрізняються між со-бою, що уявляється як єдине ціле. Ці об’єкти називаються елементами, або членами множини. Зауважимо, що формулювання поняття множини не на-кладає жодних обмежень на природу предметів, що входять у множину. Мно-жина може складатися, наприклад, з білих лебедів, чорних автомобілів, пар-них чисел. Відмітимо також, що канторівське формулювання дає змогу роз-глядати множини, елементи яких з тієї чи іншої причини не можна точно вка-зати (наприклад, множина усіх раціональних чисел, множина зірок Всесвіту). Фраза «об’єкти, що розрізняються між собою» з канторівського визначення множини означає, що для будь-яких двох предметів, які вважаються елемен-тами множини, має бути спосіб вирішити являються вони різними чи однако-вими. Слово «певний» розуміють у тому сенсі, що коли дано деяку множину та деякий предмет, то можна визначити, чи є цей предмет елементом даної множини.

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

Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів (а точніше, їх імен). На письмі множину, елементами якої є об’єкти х₁,х₂,…,х_n, будемо позначати {x₁,x₂,…,x_n}. Таке подання множини називається явним. Приклади множин, заданих явно: {2,3,8,7} – множина, елементами якої є числа 2, 3, 7 та 8; {,¯,,®,«} – множина, що складається із символів , ¯, , ®, «; {Марія, Петро, Олена, Олексій} – множина, що складається з кількох імен людей; {білий, зелений, блакитний} – множина, елементами якої є назви кольорів.

Щойно описана форма подання множин не є зручною, коли треба задати множину, що містить багато елементів, й зовсім неприйнятна, коли мова йде про множину, у якій нескінченно багато елементів. Для таких випадків використовують подання множини у формі {t(x₁,…,x_n)| P(x₁,…,x_n)}. Тут n – ціле додатне число, t(x₁,…,x_n) – вираз (послідовність символів), роль якого – показати, який вигляд мають елементи заданої множини, P(x₁,…,x_n) – твердження, яке задає необхідну й достатню умову належності об’єкта множині, x₁,…,x_n – змінні, роль яких – позначати у t(x₁,…,x_n) та P(x₁,…,x_n) місця, на які підставляються імена конкретних об’єктів при побудові елементів заданої множини або при перевірці, чи належить даний об’єкт заданій множині, причому місця, позначені однаковими змінними, «займають» одні й ті самі імена. Якщо нас не цікавить будова елементів множини, будемо використовувати вираз x замість t(x₁,…,x_n). Вираз P(x₁,…,x_n) може бути простим або складеним реченням природної мови, рівністю, нерівністю тощо. Взагалі під P(x₁,…,x_n) будемо розуміти скінченну послідовність зі слів, математичних виразів та символів x₁,…,x_n таку, що якщо кожне входження x_і (i=1,…,n) у цю послідовність замінити одним й тим самим іменем деякого об’єкту, то в результаті матимемо висловлення, тобто таке твердження, яке можна охарактеризувати як істинне або хибне. Іноді сполучник «та» («й») у виразі P(x₁,…,x_n) будемо заміняти комою. Описаний спосіб подання множини називається неявним.

Наведемо приклади множин, заданих неявно: {x| x – зірка Всесвіту} – множина, елементами якої є ті й тільки ті об’єкти, що являються зірками Всесвіту; {n| n – натуральне парне число} – множина, яка містить ті й тільки ті натуральні числа, що є парними; {n| n – непарне число й n ділиться на 5} – множина непарних чисел, кратних п’яти, будь-яке число, що не має зазначених властивостей, не належить даній множині; {(x,y)| x,y – дійсні числа} – множина, що складається з двійок дійсних чисел й тільки з них; можна також сказати, що це множина усіх точок декартової площини.

Множина може мати ім’я. Зазвичай імена множин позначаються великими латинськими літерами, що можуть мати індекси. На письмі ім’я множини розміщується перед множиною й між ними ставиться знак «=». Наприклад, запис А={a,b,c,d} означає, що множині {a,b,c,d} дано ім’я А. Ім’я множини можна використовувати замість самої множини. Одній й тій самій множині можна дати кілька імен. Деякі множини мають усталені імена (позначення). Так, множина усіх невід’ємних цілих чисел позначається N, усіх додатних цілих чисел – N⁺, множини усіх цілих, раціональних, дійсних чисел мають імена відповідно Z, Q, R.

Одна й та сама множина може бути задана явно й неявно. Наприклад, нехай A={x| x – додатне ціле число, x<10, х парне}. Можемо знайти усі такі числа, що задовольняють задані умови, отже, й задати множину А явно: А={2,4,6,8}.

Якщо деякий об’єкт х є елементом деякої множини А, будемо писати: хÎА. Даний вираз читається: «х належить А», «х є елементом А», «А містить х». Якщо треба зазначити, що певний об’єкт х не є елементом деякої множини А, будемо писати хÏА. Такий вираз читається: «х не належить А», «х не міститься в А», «х не є елементом А», «А не містить х». Таким чином, вираз хÎА (хÏА) є твердженням, істинність якого залежить від того, міститься об’єкт х у множині А чи ні. Наприклад, твердження аÎ{a,b,c} правильне, тому що об’єкт а міститься у множині {a,b,c}. Твердження хÏ{a,b,c} також правильне, оскільки множина {a,b,c} не містить об’єкта х. Твердження АÎN хибне, тому що А не є невід’ємним цілим числом, отже, не може належати множині N.

Включення та рівність множин

Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини А є елементом множини В, тобто для кожного х, якщо хÎА, то хÎВ. Використовується також й позначення ВÊА, що означає «В включає А» (або «В є надмножиною А»). Наприклад, ZÍQ, оскільки кожне ціле число є раціональним; RÊZ, тому що кожне ціле число є дійсним числом; множина А={2,4,1} є підмножиною множини В={-1, 0,1,2,3,4}, оскільки для елементів 2, 4, 1 множини А виконується: 2ÎВ, 4ÎВ, 1ÎВ. Якщо для множин А та В твердження АÍВ не є істинним, будемо писати АËВ. Наприклад, QËZ, оскільки не кожне раціональне число є цілим; якщо X={а,b,c}, Y={b,c,d}, то ХËY, тому що множина Х містить такий елемент (а саме, елемент а), якого немає у множині Y, тобто не кожен елемент множини Х є елементом множини Y (так само, як не кожен елемент множини Y належить множині Х, отже, YËХ). Якщо увести позначення: ("х) – «для кожного х» (або «для довільного х»), Þ – «випливає» (або «слідує»), Û – «тоді й тiльки тоді, коли», то визначення включення множин можна записати таким чином: АÍВ Û ("х) хÎА Þ хÎВ.

Очевидно, що для будь-якої множини Х виконується ХÍХ. Доведемо, що для будь-яких множин X,Y,Z XÍY, YÍZ Þ XÍZ. Для цього достатньо показати, що ("х) хÎХ Þ хÎZ. При доведенні будемо використовувати те, що XÍY та YÍZ. Отже, нехай хÎХ. Оскільки XÍY, то хÎY, але YÍZ, а тому хÎZ. Таким чином, ми показали, що для довільного х хÎХ Þ хÎZ. Коротко побудоване міркування можна записати так: хÎХ Þ хÎY Þ хÎZ.

Назвемо множини X та Y рівними (й позначимо Х=Y), якщо XÍY та YÍХ, тобто Х=Y Û ХÍY та YÍХ. Наприклад, множини А={3,7,2} та В={7,2,3} рівні, тому що АÍВ та ВÍА, оскільки для елементів множини А маємо: 3ÎВ, 7ÎВ, 2ÎВ, а для елементів множини В маємо: 7ÎА, 2ÎА, 3ÎА. Якщо умова рівності множин Х та Y не виконується (тобто ХËY або YËХ), то будемо говорити, що множини Х та Y не рівні й писати Х≠Y. Наприклад, якщо Х={a,b,c}, Y={d,f,a}, то Х≠Y, оскільки ХËY (а також YËХ); множини {1,2,3} та N не рівні, оскільки NË{1,2,3} (хоча {1,2,3}ÍN).

Множина Х називається власною підмножиною множини Y, або Х строго включається в Y (позначається ХÌY), якщо ХÍY, але Х≠Y, тобто ХÌY Û ХÍY та Х≠Y. Наприклад, якщо А={a,b,c}, В={a,b,c,d}, то АÌВ, оскільки для елементів множини А маємо: аÎB, bÎB, cÎB, отже, АÍВ, але ВËА, тому В≠А. Також ZÌQ, оскільки не кожне раціональне число є цілим (й тому QËZ), тобто Z≠Q, хоча ZÍQ.

Через Æ позначимо множину, що не містить жодного елементу, тобто ("х) хÏÆ. Така множина називається порожньою множиною. З визначення порожньої множини випливає, що ÆÍА для будь-якої множини А. Дійсно, оскільки Æ не має елементів, то умова хÎÆ Þ хÎА не порушується для жодного х. Зауважимо, що множина {Æ} не є порожньою, оскільки містить один елемент (порожню множину), отже, Æ≠{Æ}, але ÆÎ{Æ}. Для множини A={a,b,c} маємо ÆÏА, тому що серед елементів множини А немає елемента Æ.

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

Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто

АÈВ = {х| хÎА або хÎВ}.

Тут сполучник «або» використовується у тому розумінні, що елемент множини АÈВ може належати обом множинам (А та В).

Наведемо приклади об’єднання множин. Нехай А={1,4,5,8,9}, В={3,4,6}. Тоді АÈВ={1,3,4,5,6,8,9}. Елемент 4 з об’єднання АÈВ належить обом множинам А та В, кожен з інших елементів з АÈВ належить лише одній з цих множин. Розглянемо тепер АÈА. За визначенням об’єднання множин маємо: АÈА=А. Дійсно, жоден елемент, що не належить множині А, не може належати й множині АÈА. Нехай А={х| x – натуральне парне число}, В={x| xÎZ, x<-5}. Тоді АÈВ – це множина, елементами якої є усі від’ємні цілі числа, менші ніж -5, й усі натуральні парні числа.

Перетином множин А та В (позначається АÇВ) називається множина усіх об’єктів, що є елементами обох множини А й В, тобто

АÇВ = {х| хÎА та хÎВ}.

Нехай, наприклад, А={2,5,6,8,0}, В={3,4,5,6}. Тоді АÇВ={5,6}, оскільки елементи 5 та 6 й тільки вони є спільними для множин А та В. Розглянемо множини С={1,2,3} та D={4,5,6}. Очевидно, не існує жодного елементу, який би належав як множині С, так й множині D. Отже, множина СÇD не містить жодного елементу, тобто є порожньою: СÇD=Æ. Розглянемо перетин множин X={x| xÎN, х<100} та Y={х| x – непарне додатне число}. ХÇY – це множина непарних додатних чисел, що не перевищують 100.

Будемо говорити, що множини А та В не перетинаються, якщо АÇВ=Æ. Наприклад, не перетинаються множина від’ємних цілих чисел та множина натуральних парних чисел. Якщо АÇВ≠Æ, то множини А та В є такими, що перетинаються. Наприклад, множини Z та N є такими, що перетинаються, оскільки вони мають спільні елементи.

Різницею множин А та В (позначається А\В) називається множина, що складається з тих елементів множини А, які не належать множині В, тобто

А\В={x| xÎA, xÏB}.

Наприклад, якщо А={2,5,6,8}, В={3,5,8,9,0}, то А\В={2,6}. Нехай Х={1,3,4,6}, Y={4,5,6,1,2,3}; тоді Х\Y=Æ, оскільки у множині Х немає таких елементів, які б не належали Y. Нехай Р – множина усіх непарних натуральних чисел, тоді N\Р – це множина усіх невід’ємних парних цілих чисел.

Абсолютним доповненням (доповненням) множини А (позначається А') називається множина тих об’єктів, які не належать множині А, тобто

А'={х| хÏА}.

Множина В\А називається ще відносним доповненням множини А до множини В.

Покажемо, що В\А=ВÇА'. Для цього треба довести, що В\АÍВÇА' та ВÇА'ÍВ\А. Покажемо, що В\АÍВÇА'. Використовуючи визначення операцій різниці, перетину множин та операції доповнення множини, маємо: хÎВ\А Þ хÎВ та хÏА Þ хÎВ та хÎА' Þ хÎВÇА', отже, доведено, що хÎВ\А Þ хÎВÇА', а це означає, що В\АÍВÇА'. Тепер покажемо, що ВÇА'ÍВ\А: хÎВÇА' Þ хÎВ, хÎА' Þ хÎВ, хÏА Þ хÎВ\А, отже, хÎВÇА' Þ хÎВ\А.

Симетричною різницею множин А та В (позначається АDВ або А+В) називається множина, елементи якої належать або тільки множині А, або тільки множині В, але не обом множинам А та В, тобто

АDВ=(А\В)È(В\А).

Наприклад, нехай А={1,2,3,4}, В={3,4,6,7}, тоді АDВ={1,2,6,7}. Якщо А={х| хÎN, 1<х<101}, В={x| xÎN, х<100}, то АDВ={0,1,100}.

Розглянемо ще кілька прикладів доведення тверджень про множини.

І. Доведемо, що якщо АÍВ, то АÇСÍВÇС (або, більш коротко, АÍВ Þ АÇСÍВÇС) для будь-яких множин А, В, С.

Нам треба показати, що АÇСÍВÇС за умови АÍВ. Іншими словами, при доведенні включення АÇСÍВÇС ми можемо використовувати не лише загальні відомості про множини (такі, наприклад, як означення підмножини, операцій над множинами), а й те, що АÍВ. Отже, нехай хÎАÇС. Тоді, виходячи з означення операції перетину множин, маємо: хÎА та хÎС. Оскільки АÍВ, то з хÎА випливає хÎВ. Тепер з того, що хÎВ та хÎС, випливає хÎВÇС.

ІІ. Доведемо, що для будь-яких множин А та В

AÍBÈC Û AÇB¢ÍC.

Для доведення треба показати, що АÍВÈС Þ АÇВ'ÍС та АÇВ'ÍС Þ АÍВÈС. Покажемо спочатку, що АÍВÈС Þ АÇВ'ÍС. Для цього доведемо включення АÇВ'ÍС, користуючись тим, що АÍВÈС. Отже, нехай хÎАÇВ'. Звідси маємо: хÎА та хÎВ' (тобто хÏВ). Оскільки АÍВÈС, то хÎВÈС, отже, хÎВ або хÎС. Але раніше ми одержали, що хÏВ. Тоді залишається тільки можливість хÎС. Таким чином, ми показали, що хÎАÇВ' Þ хÎС, а це означає, що АÇВ'ÍС. Далі доведемо, що АÇВ'ÍС Þ АÍВÈС. Для доведення треба показати, що АÍВÈС за умови АÇВ'ÍС. Нехай хÎА. Якщо В – довільна множина, то хÎВ або хÏВ. Розглянемо кожен з цих випадків. Нехай хÎВ. Тоді з означення операції об’єднання множин випливає, що х є елементом множини, яка є об’єднанням множини В з будь-якою множиною. Отже, хÎВÈС. Розглянемо тепер другий випадок, тобто хÏВ. Тоді хÎВ', а оскільки хÎА, то хÎАÇВ'. Але відомо, що АÇВ'ÍС, значить хÎС, звідки випливає, що хÎВÈС. Коротко доведення можна записати таким чином.

(Þ) хÎ AÇB¢ Þ хÎА, хÎВ' Þ хÎА, хÏВ Þ хÎВÈС, хÏВ Þ хÎВ або хÎС, хÏВ Þ хÎС.

(Ü) хÎА Þ хÎА, хÎВ або хÏВ Þ 1) хÎА, хÎВ або 2) хÎА, хÏВ.

1) хÎА, хÎВ Þ хÎВ Þ хÎВÈС.

2) хÎА, хÏВ Þ хÎА, хÎВ' Þ хÎАÇВ' Þ хÎС Þ хÎ ВÈС.

Доведення завершено.

Якщо усі множини, що розглядаються при розв’язанні якоїсь задачі або при якихось міркуваннях, є підмножинами деякої множини U, то таку множину U називають універсальною множиною (універсумом). Наприклад, для елементарної арифметики універсальною множиною є Z. Для графічного зображення підмножин деякої універсальної множини U використовують так звані діаграми Венна, або кола Ейлера. Діаграма Венна є схематичним зображенням множин у вигляді точкових множин: універсальна множина зображується множиною точок деякого прямокутника, а її підмножина А – у вигляді кола або якоїсь іншої простої області усередині цього прямокутника. Доповнення множини А (до U) зображується тією частиною прямокутника, що лежить за межами кола, що зображує А. Множини, що не перетинаються, зображуються областями, що не перекриваються. Якщо АÍВ, то на діаграмі Венна та область, що зображує множину А, цілком лежить усередині області, що зображує множину В. Діаграми Венна є корисним допоміжним засобом при вивченні операцій над множинами.