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

Множини

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

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

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

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

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

Львів – 2013

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

Укладачі

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

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

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

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

Рецензенти

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

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

Зміст

1. Вступ. 4

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

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

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

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

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

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

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

9. Завдання до виконання. 26

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

Список літератури. 34

МНОЖИНИ

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

Вступ

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

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

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

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

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

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

Наприклад: .

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

.

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

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

Ø ;

Ø ;

Ø .

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

Ø ;

Ø ;

Ø .

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

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

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

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

Універсум на діаграмах Ейлера-Венна зображується у вигляді прямокутника.

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

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

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

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

,

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

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

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

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

Приклад 4.1.

Ø ,

Ø ,

Ø , ▲

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

,

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

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

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

Приклад 4.2.

Ø , , ;

Ø , , ;

Ø , ,

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

,

,

:

,

де – знак різниці.

Приклад 4.3.

Ø , , , ;

Ø , , ;

Ø , {непарні числа}, {парні числа}.▲

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

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

ТЕОРЕМА 4.1.

Доведення. , тоді

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

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

Для роботи із множинами часто використовують закони, наведені у таблиці 4.1.

Таблиця 4.1.

Назви законів	Формулювання законів
Закони комутативності
Закони асоціативності
Закони дистрибутивності
Закон подвійного доповнення
Закони ідемпотентності
Закони де Моргана
Закони поглинання
Закони тотожності
Закон домінування

Геометрична ілюстрація:

Приклад 4.4.

Розглянемо множини ,

.▲

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

Приклад 4.5. Нехай ; ; ; .

Означення 4.6. Кортеж – це впорядкований набір елементів.

Означення 4.7. Компоненти кортежу – елементи, що утворюють кортеж.

На відміну від множини, компоненти кортежу можуть повторюватись. Кортеж записують у круглих дужках, наприклад, (a, b, c, a, d, k) – кортеж довжиною 6. Кортежі довжини два часто називають парами, а довжини 3 – трійками.

Означення 4.8. Два кортежі називаються рівними, якщо вони мають однакову довжину та їхні відповідні компоненти рівні. Тобто, кортежі та рівні, якщо m=n, а також

Означення 4.9. Декартовим добутком двох множин та називається множина всіх впорядкованих пар(a,b):

Якщо A=B, то такий добуток називають декартовим квадратом множини А:

Аналогічно можна ввести декартовий добуток трьох , чотирьох і т.д. множин. При скорочено пишуть і кажуть про n-й декартовий степінь множини A. Елементами є послідовності (набори, вектори, рядки) ( ) довжиною n.

2. Нехай – множини символів, які позначають горизонтальні і вертикальні поля шахівниці. Тоді – множина всіх кодів кліток шахівниці.▲

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

Для будь-яких скінченних множин та виконується рівність .

У випадку трьох множин також легко довести рівність:

Ці рівності є частковими випадками принципу включення-виключення.

Приклад 5.1. Скільки чисел серед 1,2,3,…,99,100 таких, що не діляться на жодне з чисел 2,3,5?

Підрахуємо спочатку кількість чисел, які діляться принаймні на одне з чисел 2,3,5. Нехай – множина тих чисел, які діляться на 2, – множина тих чисел, які діляться на 3, – множина тих чисел, які діляться на 5. Тоді

, , ,

, , , .

Тому, використавши формулу обчислення потужності для об’єднання трьох множин, маємо:

Отже, кількість чисел, які не діляться на жодне з чисел 2,3,5, дорівнює 100-74=26. p

ТЕОРЕМА 5.1. Для довільних множин A_k, k=1..n виконується:

Приклад 5.2. Розглядаються всі перестановки n чисел 1,2,…,n. Знайти число D_n тих перестановок, у яких принаймні одне число стоїть на місці зі своїм номером.

Позначимо через A_k множину тих перестановок, у яких на k-му місці стоїть k. Тоді

.

Множина містить ті перестановки, у яких на місцях відповідно стоять числа , а на інших n-k місцях числа впорядковані довільно. Тому

,

a

.

З теореми 5.1. випливає, що

p

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

Приклад 8.1. Задати двома різними способами множину А всіх парних чисел 2, 4, 6, ...., що не перевищують 1000.

Розв’язання:

1. Перерахуванням: А={2, 4, 6, 8, 10, …, 998, 1000};

2. Описом: А={(x|xÎN) (х/2ÎN), N£1000}; (N – множина натуральних чисел 1, 2, 3, ….).▲

Приклад 8.2. Зобразіть фігури, задані множинами , , де – дійсна площина. Які фігури зображають множини ?

Розв’язання:

Приклад 8.4. Перечисліть елементи наступних множин:

1) А={a|aÍB, B={1,2,3}};

2) A={a|aÎB, B={1,2,3}}.

Розв’язання:

1) Так, як аÍВ, а В – трьохелементна множина, то існує 2³=8 підмножин: А={{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, Æ}.

2) Так, як аÎВ, то А=В={1,2,3}.▲

Приклад 8.5. Довести, використовуючи закони алгебри множин, що

Розв’язання:

▲

Приклад 8.6. Спростити вираз

Розв’язання:

Використовуючи закони алгебри множин:

▲

Приклад 8.7. Опитування 100 студентів показало, що серед них англійську мову вивчають 29 студентів, німецьку – 30, французьку – 9, лише французьку – 1, англійську та німецьку – 10, німецьку та французьку – 4, всі три мови – 3 студенти. Скільки студентів не вивчають жодної мови? Скільки студентів вивчають лише німецьку мову? У розв’язку використовувати діаграми Ейлера-Венна.

Розв’язання:

Введемо позначення:

U – множина всіх опитаних студентів;

А – множина студентів, які вивчають англійську мову;

Н – множина студентів, які вивчають німецьку мову;

Ф – множина студентів, які вивчають англійську мову.

З умови задачі очевидно, що =3, тоді =4-3=1; 10-3=7. У такому випадку лише німецьку мову вивчають 30-7-3-1=19 студентів.

Із умови задачі також випливає, що 9-1-1-3=4, тому лише англійську мову вивчають 29-4-3-7=15 студентів. Тоді число студентів, що не вивчають жодної мови, буде рівним 100-(1+1+3+4+7+15+19)=50 студентів.

Рис. 8.1 Діаграма Ейлера-Венна

Приклад 8.8. Довести, що для будь-яких множин А та В виконується рівність .

Розв’язання:

Для доведення використаємо метод від супротивного, тобто нехай і .

Із АÍВ випливає, що якщо аÎА, то аÎВ. (1)

З іншої сторони із Ë існує такий елемент а, що та , отже і . (2)

Використовуючи (1) та (2):

З того, що і випливає, що та , а звідси =Æ, тобто отримали суперечність.

Таким чином, вираз хибний і тому , тобто .

Аналогічно можна показати, що і, отже, , що і потрібно було довести. ▲

Приклад 8.9. Знайти декартовий добуток множин A={1,2,3}, B={a,b} та його потужність.

Розв’язання:

A´B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b) },

B´A = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3) }.

Як бачимо, A´B ¹ B´A.

Потужність декартового добутку: |A´B|=|B´A| = 3×2=6. ▲

Приклад 8.10. Довести рівність множин:(AÈB)´С=(A´C)È(B´C)

Розв’язання:

Доведемо, що (AÈB)´СÍ(A´C)È(B´C).

Нехай zÎ(AÈB)´С, тоді z=(x,y), де xÎAÈB та yÎС. Отже, xÎA або xÎВ. Тобто xÎA та yÎС або xÎВ та yÎС. Тому zÎA´C або zÎB´C. За означенням об’єднання zÎ(A´C)È(B´C).

Доведемо, що (AÈB)´СÊ(A´C)È(B´C).

Нехай zÎ(A´C)È(B´C), тоді zÎA´C або zÎB´C. Так як z=(x,y), то xÎA, yÎС або xÎB, yÎС.Отже, xÎA або xÎВ при yÎС. Тому xÎAÈB і yÎС. За означенням декартового добутку zÎ(AÈB)´С. ▲

Приклад 8.11. Зобразіть на координатній площині декартовий добуток множин А×В, якщо:

a) А= {1,2,3}, В=[3,5];

b) А={х ׀ x R, 1≤x≤3}; B={y ׀ y R, 3≤y≤5};

c) А=R, В=[3,5];

d) А=R, В=R.

Розв’язання:

а) Так як множина А складається з трьох елементів, а множина В містить всі дійсні числа від 3 до 5, включаючи і самі ці числа, то декартовий добуток А×В складатиметься з нескінченної кількості пар, перша компонента яких або 1, або 2, або 3, а друга – будь-яке дійсне число з проміжку [3, 5]. Безліч таких пар дійсних чисел на координатній площині зобразиться трьома відрізками (рис. 8.2).

Приклад 8.12. На координатній площині побудувати множину (-1; 3]×[1; 3).

Розв’язання:

Першу множину поміщаємо на осі OX, другу на осі OY. Множина всіх пар, тобто декартовий добуток, зображається точками заштрихованого прямокутника, але без лівої та нижньої сторони (рис. 8.5).

Рис. 8.5 Декартовий добуток

Приклад 8.13. Скільки цілих чисел між 0 та 1000 містять рівно одну цифру 6?

Розв’язання:

Нехай S – множина цілих чисел між 0 та 1000, що містять рівно одну цифру 6. Розглянемо три підмножини S₁, S₂ та S₃ множини S.

S₁ – множина, яка містить число, що складається з однієї цифри і ця цифра 6;

S₂ – множина, яка містить двохзначне число, що містить лише одну цифру, яка рівна 6;

S₃ – множина, яка містить трьохзначне число, що містить лише одну цифру, яка рівна 6.

Множина S₁ містить лише один елемент – число 6.Отже, | S₁|=1.

У множині S₂ кожен елемент, що містить 6, є або першою, або другою цифрою. Якщо 6 – друга цифра, то існує 8 різних чисел, які будуть стояти на першій позиції, оскільки перше число не може бути 0 або 6. Якщо 6 – перша цифра, то таких чисел 9, оскільки друга цифра не може бути рівна 6. Таким чином, S₂ містить 8+9=17 елементів, тобто | S₂|=17.

Елемент із S₃ може містити 6 як першою, так і другою чи третьою цифрою. Якщо 6 – перша цифра, то існує 9 варіантів вибору другої цифри та 9 варіантів вибору третьої цифри. Згідно комбінаторному принципу множення, S₃ містить 9 ´ 9=81 чисел з першою цифрою 6. Якщо 6 –друга цифра, то існує 9 варіантів вибору третьої цифри та 8 варіантів вибору першої цифри, оскільки перша цифра не може бути нулем. Очевидно, S₃ містить 9´8=72 чисел, у яких 6 – друга цифра. Аналогічно, S₃ містить 72 числа, у яких 6 – третя цифра. Отже, всього S₃ містить 81+72+72=225 елементів, тобто |S₃|=225.

Оскільки та множини S₁, S₂ і S₃ – ті, що попарно не перетинаються, тоді

.▲

Приклад 8.14. Скільки додатних цілих чисел, менших 1001, діляться на 2, 3 чи 5?

Розв’язання:

Нехай X – множина додатних цілих чисел, які діляться на 2, 3 чи 5. Розглянемо три підмножини X₁, X₂ і X₃ множини X.

X₁ – множина додатних цілих чисел, які діляться на 2. Число елементів чи потужність цієї множини дорівнює .

X₂ – множина додатних цілих чисел, які діляться на 3 Число елементів чи потужність цієї множини дорівнює .

X₃ – множина додатних цілих чисел, які діляться на 5. Число елементів чи потужність цієї множини дорівнює .

Тоді множина X₁ÇX₂ – множина додатних цілих чисел, які діляться на 2 або 3. Відповідно . Множина X₁ÇX₃ – множина додатних цілих чисел, які діляться на 2 або 5. Тоді . Множина X₂ÇX₃ – множина додатних цілих чисел, які діляться на 3 або 5. Аналогічно .

Множина X₁ÇX₂ÇX₃ – множина додатних цілих чисел, які діляться на 2, 3 або 5. Число елементів чи потужність цієї множини дорівнює .

Використовуючи формулу включення і виключення:

Приклад 8.15. Про множини А, B, С відомо, що: = {1, 2, 3, 4, 5, 6}, = {3}, ={1, 2, 4, 6}, ={2, 5, 6}, = {2}, {1, 2, 5}, {1, 6}.

Знайдіть множини А, B, С.

Розв’язання:

Зобразимо перетин трьох множин A, B, C на рис. 8.6. і позначимо всеможливі утворені множини :

Рис. 8.6 Приклад перетину трьох множин

Складемо систему рівнянь:

1. = {1, 2, 3, 4, 5, 6};

2. ={3};

3. ={1, 2, 4, 6};

4. ={2, 5, 6};

5. = {2};

6. ={1, 2, 5};

7. ={1, 6}.

Отримаємо:

={3}, ={2}.

Із рівнянь (6 - 7) зрозуміло, що ={1}.

Тоді з рівняння (6) випливає, що ={5}, а з рівняння (7) та (3) випливає, що , а ={6}. Із рівняння (3) ={4}.

Отже, = {1, 3, 5, 6},

= {2, 3, 4, 5},

= {3, 4, 6}.p

9. Завдання до виконання

1. Нехай А={{1,2,3}, {1,3}, 1, 2}. Чи справедливо, що

a) {1, 2}ÎА;

b) {1, 2}ÌA.

2. Перелічити елементи множини:

, n=1, 2,…}.

3. Перелічити елементи наступних множин:

a)

b)

c)

4. Нехай А – довільна множина. Що являють собою наступні множини:

a)

b)

c)

d)

5.Записати множини, перелічивши їх елементи. Яка потужність даних множин?

a) А = {n | n — додатні числа, кратні 7 і менші 60};

b) В = {x ׀ x² - 5x + 6 = 0}.

6. Записати усі підмножини множини А ={а, b, с}.

a) Чи рівні множини {a, b, c, d}і {b, d, с, а}?

b) Нехай М = {чотирикутники}. Чи належать до множини М такі фігури: квадрат, ромб, коло, шестикутник?

7. Нехай А – множина цілих чисел, що діляться на 4, а В – множина цілих чисел, що діляться на 3. Які з чисел 9, 0, -24, -53, 128, 242048 входять у множину ?

8. Нехай А = {1, 2, 3, 4, 5, 6, 7} і В = {2, 4, 6}. Знайти:

a) суму С;

b) різницю R;

c) переріз Р множин А і В.

9. Нехай Ν = {натуральні числа}, М ={додатні раціональні числа}, Р={прості числа}, Q = {додатні непарні числа}. Чи правильне твердження ?

10. Нехай А – множина, що складається з 30 стільців, а В – множина, що складається з 30 студентів. Чи А=В ? Обґрунтувати відповідь.

11. За допомогою наочного зображення на площині впевнитись, що для будь-яких трьох множин А, В і С справджуються такі рівності:

a) ;

b) .

12. Користуючись кругами Ейлера, довести рівності:

a) ;

b) .

13. Вказати, які з поданих нижче множин скінченні, а які нескінченні (поясніть, чому):

a) множина цілих чисел, що діляться на 5;

b) множина коренів заданого многочлена;

c) множина всіх рослин на Землі.

14. Записати формули, відповідні до діаграм Венна:

a) b)c)