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

ПЕРЕДМОВА

Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає в себе як традиційні розділи, які вже сформувалися (теорію множин, математичну логіку, комбінаторику, теорію графів та ін.), так і нові, що інтенсивно розвиваються (теорію алгоритмів, кодування та ін.).

Спеціалісти, які займаються прикладними дослідженнями, програмуванням мають все більшу потребу у використанні апарату дискретної математики, що пояснюється широким застосуванням комп’ютерної техніки та інформаційних технологій. Тому сьогодні дисципліна “Дискретна математика” є однією з основних фундаментальних дисциплін у загальнонауковій підготовці студентів – комп’ютерників.

Методичні рекомендації мають за мету надання допомоги студентам у організації їх самостійної роботи з опанування курсу дисципліни. Зміст і стиль подання матеріалу у посібнику повністю відповідає навчальній програмі дисципліни “Дискретна математика” та задовольняє потреби суміжних математичних і прикладних дисциплін.

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

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

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

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

Об’єкти, що утворюють множину, називаються елементами множини. Елементи звичайно позначаються малими літерами латинського алфавіту, а множини великими. Якщо m є елемент, який належить множині М, то використовується запис , у протилежному випадку - . Читається так: m належить М.

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

Множина може задаватися різними способами: перерахуванням елементів для скінченної множини або зазначенням їх властивостей. У разі перерахування використовують фігурні дужки {}. Наприклад, множину М цифр десяткового алфавіту можна задати у вигляді М ={0, 1, …, 9}.

Цю ж саму множину можна задати й інакше, як М ={i|i – ціле, }, де справа від вертикальної риски зазначається характеристична властивість елементів цієї множини.

Якщо ж множина М є множиною, наприклад, парних чисел, то вона записується як М ={m|m – парне число} або М ={m|m=2k, kÎ N}.

Іноді нескінченні множини задаються простим перерахуванням кількох перших елементів, і тоді характеристична властивість є заданою в неявному вигляді. Наприклад, множину парних чисел можна задати у вигляді A ={2, 4, 6, 8, …}.

Для того, щоб позначити множину всіх предметів, що є елементами множини А і мають властивість P, замість {x| i P(x)} часто пишуть { |P(x)}.

Наприклад, означає множину всіх дійсних чисел від 0 та 1 включно, а - множину всіх додатних раціональних чисел, квадрати яких менші за число 2.

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

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

Дві множини рівні тільки тоді, коли вони складаються з одних і тих самих елементів. Тому будь-яка множина Х = Х.

Рівність двох множин Х і Y позначається через Х = Y, а нерівність множин Х і Y – через Х ≠ Y. Для будь-яких рівних множин Х, Y і Х, Y, Z виконуються умови:

1. Якщо Х = Y, то Y = X;

2. Якщо Х = Y та Y = Z, то Х = Z.

Порядок елементів у множині не є суттєвим. Множини {3, 4, 5, 6} і {4, 5, 6, 3} являють собою одну й ту саму множину.

Множини не містять однакових елементів. Так, множина простих дільників числа 60 дорівнює {2, 3, 5}, а не {2, 2, 3, 5}.

Слід розрізняти об’єкт і множину, єдиним елементом якої є цей об’єкт. Так множина {1, 2} становить об’єкт, який є елементом множини {{1, 2}}. Множини {{1, 2}} і {1, 2} не рівні, оскільки перша – одноелементна множина, що має єдиний елемент {1, 2}, а друга має два елементи 1 і 2.

Якщо множина не містить жодного елемента, то вона називається порожньою і позначається . Інколи її називають ще пустою множиною. Наприклад, множина трикутників з двома прямими кутами є порожньою. Також множина простих чисел, які діляться на число чотири, є порожньою. Але множина { } не є порожньою, тобто ={ }; ця множина є одноелементною. Її єдиним елементом є порожня множина.

Усі підмножини множини А, яка складаються з n елементів, створюють множину, що називається множиною-степенем, або булеаном множини А і позначається Р(А) або В(А). Якщо, наприклад, А ={1, 2, 3}, то множина-степінь

Р(А) ={ {1, 2, 3}, {1, 2, }, {1, 3}, {2, 3}, {1}, {2}, {3}, { }}. (1.1)