Множини. Методичка

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

МНОЖИНИ

МЕТОДИЧНІ ВКАЗІВКИ

до виконання практичних завдань з дисципліни „Комп’ютерна дискретна математика‖

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

Затверджено на засіданні кафедри

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

Львів – 2013

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

Укладачі

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

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

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

Рецензенти

Гавриш В.І., к.ф.-м.н., доц. кафедри програмного забезпеченння національного університету ―Львівська політехніка‖ Огородник Н.П., к.ф.-м.н., асис. кафедри теорії оптимальних процесів Львівського національного університету ім. І. Франка

3

МНОЖИНИ

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

1.Вступ

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

(Парадокс Рассела)

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

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

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

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

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

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

4

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

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

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

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

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

Приклад 2.1.

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

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

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

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

Для позначення конкретних множин використовують великі букви латинського алфавіту: A, B,C,...,X ,Y,... або великі букви з індексами A1, A2 ,...

.

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

a1, a2 ,....

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

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

5

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

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

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

Приклад 2.2.

Множина A {1,4,7,8,10} має потужність A =5. Множина днів тижнів має потужність 7. Множина місяців року має потужність 12.

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

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

Означення 2.5. Множина А називається підмножиною множини В,

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

множини В всіх місяців року.

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

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

Приклад 2.4.

1,2,3 3,1,2 ;

1,2,4 20 ,21,22 .▲

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

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

6

універсальна множина не існує у всіх випадках.

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

P(A).

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

A n P( A) 2n.

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

Приклад 2.5. Розглянемо множину A {a,b}. Булеаном даної множини є P( A) { , {a},{b},{a,b}}.

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

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

Спосіб 1. Найбільш природним є спосіб задання множини переліком

(або списком) елементів.

Наприклад: A 1,2,3,4,5 .

Порядок елементів у записі множини значення не має:

A 1,2,3,4,5 3,5,2,1,4 .

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

Приклади стислого представлення множин:

A 0,1,...,9 ;

A 3,5,...,2n 1,... ;

A 3, 5, 9,..., 2n 1,... .

Спосіб 2. Універсальним є задання множини за допомогою характерних властивостей її елементів (тобто властивостей, які мають всі елементи даної множини і лише вони). Наприклад:

A x | x N, x 16 ;

A x | x Z, 10 x 19 ;

A x | x Z .

2

Спосіб 3. Аналітичний, за допомогою символів операцій над множинами та дужок.

7

Наприклад, C A B (незнайомі символи будуть описані в наступному підрозділі).

Спосіб 4. Вербальний (мовний) за допомогою опису характерних властивостей, які повинні мати елементи множини.

Наприклад, множина А – це множина, елементами якої є всі назви днів тижня.

Спосіб 5. Множини зручно задавати графічно за допомогою діаграм Ейлера-Венна. Діаграми Ейлера-Венна (Джон Венн (1834-1923) англійський логік і математик, професор Кембриджського університету) є геометричним зображенням множин. Множина зображується замкненою кривою довільної форми (найчастіше – кругом). Точки, які лежать всередині замкненої кривої, можна розглядати як елементи відповідної множини.

Наприклад:

На наступній діаграмі Ейлера-Венна задані множини a,b, c , b, d,e в універсумі U a,b, c, d, e :

8

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

Вважаємо, що всі множини, що розглядаються, є підмножинами деякого універсуму U.

Означення 4.1. Об'єднанням двох множин A та B називається множина A B , що складається з усіх елементів, що належать хоча б одній з множин A, B :

A B {x| (x A) (x B)},

де – знак об’єднання.

На діаграмі Ейлера-Венна об’єднання показується сірим кольором:

A B

Об’єднання складається з усіх елементів множини A та усіх елементів множини B і не містить ніяких інших елементів.

Операція об’єднання узагальнюється на довільну кількість множин. У такому випадку використовується позначення:

Означення 4.2. Перерізом двох множин A та B називається множина, що складається з тих і лише тих елементів, що належать і A, і В:

A B {x| (x A) (x B)},

де – знак перерізу.

На діаграмі Ейлера-Венна переріз показаний сірим кольором:

A B

Операція перерізу узагальнюється на довільну кількість множин. У

9

такому випадку використовується позначення:

Приклад 4.2.

A a,b , B b, d, e, k , A B b ;

A k, p , B b,c,d , A B ;

A Z , B x | x Z, x 0 , A B N;

A {прямокутники}, B {ромби}, A B {квадрати}.▲

позначається BA .

Зобразимо поняття різниці множин за допомогою діаграм ЕйлераВенна:

A \ B

ТЕОРЕМА 4.1. A \ B A B.

Доведення. A \ B {x | (x A) (x B)} {x | (x A) (x B)}, тоді

A \ B A B.

Означення 4.4. Різниця універсальної множини U і будь-якої її підмножини А називається доповненням множини A до універсальної U . Позначається A U \ A .

На діаграмі Ейлера-Венна доповнення показане сірим кольором:

10