МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Множини методичні вказівки

до виконання практичних завдань

з дисципліни „Комп’ютерна дискретна математика”

для студентів базового напряму

„Програмна інженерія”

Затверджено на засіданні кафедри програмного забезпечення Протокол № 14 від 18.04.2013 р.

Львів – 2013

Множини. : Методичні вказівки до виконання практичних занять з дисципліни „Комп’ютерна дискретна математика” для студентів базового напряму „Програмна інженерія”/ Укл.: П. В. Сердюк – Львів: Видавництво Національного університету „Львівська політехніка”, 2013. – 35 с.

Укладачі

П. В. Сердюк., к. т. н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”

О.О. Нитребич, асист. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Відповідальний за випуск

Федасюк Д.В., д-р тех. наук, проф., завідувач кафедрою програмного забезпечення, проректор з науково-педагогічної роботи національного університету “Львівська політехніка”

Рецензенти

Гавриш В.І., к.ф.-м.н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Огородник Н.П., к.ф.-м.н., асис. кафедри теорії оптимальних процесів Львівського національного університету ім. І. Франка

Зміст

1.Вступ 4

2. Основні поняття теорії множин Кантора 4

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

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

5. Метод включення і виключення 13

6. Доведення рівностей з множинами 15

7. Комп’ютерне представлення множин 16

8. Приклади розв’язування завдань 18

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

Множини

Мета роботи: Ознайомлення на практиці із основними поняттями та властивостями множин, задачами і принципами для роботи з ними.

1. Вступ

Нехай у деякому селищі немає бородатих людей і всі чоловіки голяться або самі, або у місцевого перукаря. Також у цьому селищі існує правило, згідно з яким перукар голить тих і тільки тих, хто не голиться сам. Запитання: хто голить перукаря ? (Парадокс Рассела)

Теорія множин є теоретичною основою не лише дискретної, а й усієї сучасної математики.

Офіційно теорія множин була визнана наприкінці XIX ст., коли вона широко застосовувалася в математичному аналізі. Теорія множин стала основою створення алгебраїчних систем, що мають велике практичне застосування при розробці математичного забезпечення ЕОМ.

Сучасні дослідження теорії множин були започатковані Георгом Кантором таРічардом Дедекіндомв 1870-х роках. Група французьких математиків ХХ ст., які виступали під псевдонімом Н. Бурбакі, про множини говорили так: «Сьогодні ми знаємо, що майже всю сучасну математику можна вивести з одного джерела – теорії множин».

2. Основні поняття теорії множин Кантора

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

У 1901роціБертран Рассел, вивчаючи наївну теорію множин, дійшов допарадоксу(відтоді відомому якпарадокс Рассела), наведеного в епіграфі. Якщо відповіддю на поставлене в парадоксі питання буде «так», то перукар відноситься до категорії тих мешканців, хто голиться сам, а таких людей, відповідно до існуючого правила, він не повинен голити. Отже, перукар не повинен себе голити. Якщо ж він не буде голити самого себе, то стане відноситьсь до категорії тих, хто не голиться сам, а таких людей перукар якраз і повинен голити. Отже, перукар має голитися сам.

Таким чином була продемонстрована суперечливість наївної теорії множин і пов'язаної з нею канторівскої програми стандартизації математики. Це стало передумовою виникнення аксіоматичної теорії множин, що будується на системі аксіом– тверджень, що приймаються без доведення, за допомогою яких виводяться всітеоремита твердження теорії множин. Система аксіомЦермело-Френкеля(ZF) вважається стандартною системою аксіом для теорії множин. У рамках аксіоматичної теорії множини «існують» виключно формальним чином і їхні «властивості» залежать від вибору аксіоматики.

Будемо вважати, що множина – сукупність певних об’єктів, які об’єднані спільними властивостями.

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

Означення 2.1. Елементи множини – об’єкти будь-якої природи, що утворюють множину.

Приклад 2.1.

У множині учнів школи елементом буде учень.

У множині місяців року елементами є: липень, січень, жовтень і т.д.

У множині натуральних чисел елементами є 1, 4, 6 та ін.

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

Для позначення конкретних множин використовують великі букви латинського алфавіту: або великі букви з індексами .

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

Щоб показати належність елемента певній множині, використовують символ :– елементналежить множині(знакє стилізацією першої букви грецького слова– бути, існувати); неналежність елемента множині позначається символом:.

Деякі важливі числові множини мають стандартні позначення, яких слід дотримуватися. Так, літерами N, Z, Q, R позначають відповідно множину натуральних чисел, множину цілих чисел, множину раціональних чисел і множину дійсних чисел.

Означення 2.2. Множина називається скінченною, якщо вона складається зі скінченного числа елементів (тобто існує таке натуральне число, яке є кількістю її елементів). В протилежному випадку множина називається нескінченною.

Означення 2.3. Потужність скінченної множини – це кількість елементів у даній множині . Потужність множини позначається.

Щодо потужності нескінченної множини, то ми її розглядати не будемо.

Приклад 2.2.

Множина _{має потужність =5.}

_{Множина днів тижнів має потужність 7.}

_{Множина місяців року має потужність 12.}

Відношення між множинами

Означення 2.4. Порожня множина – це множина, що не містить жодного елемента і позначається символом .

Означення 2.5. Множина А називається підмножиною множини В, якщо кожний елемент множини А є в множині В. Це позначається як () – « включається в » (включає ), де – знак нестрогого включення.

Означення 2.6. Якщо и , тоназиваєтьсявласною, строгою чи істинною підмножиною . Позначення: , де– знак строгого включення.

Приклад 2.3.

Множина _{є підмножиною множини .}

Множина _{не є підмножиною множини В всіх місяців року.}

Множина  є підмножиною будь-якої множини А,  .

Множина А є підмножиною множини А, .▲

Означення 2.7. Дві множини А та В називаються рівними, якщо вони складаються з однакових елементів. У цьому випадку пишуть А=В.

Приклад 2.4.

• ;

• .▲

Множини і рівні (=), якщоі .

Означення 2.8. Якщо множини, що розглядаються, є підмножинами деякої множини, то таку множину називають універсумом або універсальною множиною. Універсум позначають літерою Варто_{зауважити, що універсальна множина не існує у всіх випадках.}

Означення 2.9. Множина, елементами якої є всі підмножини множини і тільки вони (включно з порожньою множиною та самою множиною А), називається булеаном або множиною-степенем множини і позначається P(A).

У випадку скінченної підмножини , що складається зелементів, булеанP(A) містить елементів:

Очевидно, що число елементів булеана P(A) залежить від числа елементів унiверсуму A=U. Наприклад, якщо , то маємо

Приклад 2.5. Розглянемо множину_. Булеаном даної множини є ,

Перша й остання підмножини невласні, інші – власні. ▲