Ім'я файлу: Дискретна математика. Методичний посібник.pdf
Розширення: pdf
Розмір: 1376кб.
Дата: 22.04.2021
скачати
1.3. Основні закони алгебри множин Розширення: pdf
Розмір: 1376кб.
Дата: 22.04.2021
скачати
Для зручності нижче вказано основні закони алгебри множин, які використовуються у подальшому:
1) Закони комутативності:
,
A
B
B
A
A
B
B
A
,
A
B
B
A
2) Закони асоціативності:
A
B
C
A
B
C
,
A
B
C
A
B
C
,
A B
C
A
B C
3) Закони ідемпотентності:
A
A
A
,
A
A
A
4) Закони дистрибутивності:
A
B
C
A
B
A
C
,
A
B
C
A
B
A
C
,
9
A
B C
A
B
A
C
5) Властивості універсальної множини:
A
U
A
,
A
U
U
,
A U
A
6) Властивості порожньої множини:
A
,
A
A
,
A
A
7) Закон подвійного доповнення:
A
A
8) Властивості доповнення:
A
A
,
A
A U
,
A A U
9) Закони де Моргана:
A
B
A
B
,
A
B
A
B
10) Властивості різниці:
\
A B
A
B
,
\
A A
,
\
U A
A
11) Властивості симетричної різниці:
\
\
A B
A B
B A
,
\
A B
A
B
A
B
,
A B
A
B
A
B
,
A B
A B
A B
,
A A
Приклад 1.6. З використанням властивостей операцій довести, що у алгебрі множин виконуються наступні рівності:
10 а)
A
A
B
A
(закон поглинання); б) A
A
B
A
B
; в)
\
\
A
B
C A
A B
; г)
\
\
A
A
B
B C
A C
B C
Розв’язок. а) Використаємо перший дистрибутивний закон та властивості універсальної множини:
5 4
5 5
A
A
B
A
U
A
B
A
U
B
A
U
A
Над рівностями у попередньому рядку вказані номери законів алгебри множин, які використовуються при переході від множини у лівій частині рівності до множини у правій частині. б) Використаємо другий дистрибутивний закон, властивості доповнення та універсальної множини:
4 7
5
A
A
B
A
A
A
B
U
A
B
A
B
в) Використаємо закони де Моргана, закон асоціативності, комутативності та дистри- бутивності, властивості операції віднімання та закон ідемпотентності:
2,9,10 1,9 9
4
\
\
A
B
C A
A
B
C A
A
B
C
A
B
A
C
A
a)
4 3
10
\
B
A
C
A
A
B
A
C
A
B
A A B
г) Використаємо закон асоціативності, комутативності, дистрибутивності та ідемпо- тентності, властивості універсальної та порожньої множин а також властивості операції віднімання та симетричної різниці множин:
3 2
A
A
B
B C
A
B
A
C
A
B
B
A
B
C
2,3 2
A
B
A
C
A
B
B
A
B
C
A
C
A
B
A
B
5, 6 11 4
A
B
C
A
C
A
B
C
A
C
U
A
C
B
1, 2,3, 7 4
5 10
\
\
A
C
U
B
A
C
B
A
C
B
C
A C
B C
1.4. Метод математичної індукції
Метод математичної індукції заснований на принципі математичної індукції, який полягає у наступному: твердження справедливе для всіх натуральних n, якщо
1) твердження справджується при n = 1 (база індукції);
2) із виконання твердження для довільного натурального n = k випливає його спра-
ведливість для n = k + 1.
11
Приклад 1.7. Довести, що сума квадратів n перших натуральних чисел рівна
1 2 1
6
n n
n
Розв’язок. Нехай
2 2
2 2
1 2
S n
n
1) База індукції. Нехай
1
n
. Тоді
2 2
1 1 1 2 1 1 1
1 6
S
2) Припустимо, що при n
k
твердження виконується, тобто
2 1 2 1
6
k k
k
S k
і нехай
1
n
k
. Тоді
2 2
2 2
2 2
2 1 2 1
1 1
2 1
1 6
k k
k
S n
S k
k
k
k
2 1 2 7
6 1
2 1
6 1
1 2 2 3
6 6
6
k
k
k
k
k
k
k
k
k
k
1 2 2 1
1 1 2 1
6 6
k
k
k
n n
n
1.5. Задачі для самостійного розв’язування
1. Нехай
5,6,...,30
U
— універсальна множина,
5,7,8,10,13,19,20,27,28,30
A
,
5,7,6,11,13,18,20,24,29
B
,
|
, 2 1 просте число
C
x x U
x
. Знайти
1)
\
\
A B
C A
2)
\
A C
A
B
3)
\
C
B
B
A
4)
\
A
C
B A
5)
\
A
B
C
A
6)
\
B C
A B
7)
\
B C
A
B
C
8)
\
\
A C
B A
9)
\
\
B
B C
B
A
10)
\
C A
B
A
2. На діаграмі Ейлера-Венна зобразити множини
1)
\
\
C
B C
A
2)
A
B
C
3)
\
C
A
B
12 4)
\
A C
B
5)
\
C
B A
6)
C
A
B
7)
\
\
A B
C A
8)
\
B A
C
9)
\
B
C
A
10)
\
C
B
A
3. Довести, що в алгебрі множин справджуються рівності
1)
\
\
\
A
B
C
C
B
A
A C
B
2)
\
\
\
A
B C
B
C
A
3)
\
\
A B
C
A
C
B
4)
\
C B
A
A
B
C
5)
\
\
\
B
C
A
B C A
6)
\
\
A
B
C
A B
C
7)
\
\
A
B
C
C A
A B
C
8)
\
\
\
C A
A B
A B
C
9)
\
\
\
A B
A
C
C
A
B
10)
\
\
B A
A C
B
B
C
A
4. Розв’язати наступні задачі
1) За результатами сесії жоден з 24 студентів групи не отримав двійку, 7 мають при- наймні одну оцінку «задовільно», 16 — «добре», 8 — «відмінно». У трьох сту- дентів є обидві оцінки «добре» і «відмінно», у двох — «задовільно» і «відмінно», у чотирьох — «задовільно» і «добре». Знайти кількість студентів, усі оцінки яких однакові.
2) У класі навчається 20 учнів. Із них 7 відвідують танцювальний гурток, 6 — дра- матичний, 8 — гурток з малювання. Троє школярів займаються і у танцювальному
і у драматичному гуртках, 5 — і у танцювальному і гуртку з малювання, 1 — лише у драматичному, 2 — в усіх трьох гуртках. Скільки школярів не відвідують жодний гурток?
3) Із 40 туристів 8 чоловік знають французьку мову, 16 — англійську, 8 — німецьку.
Троє знають французьку і англійську, один — французьку і німецьку, четверо — англійську і німецьку, один — усі три мови. Знайти кількість туристів, які не знають жодної з трьох мов.
4) У групі вчиться 25 студентів. Відомо, що 5 студентів отримали п’ятірку з мате- матики, 8 — з програмування, 7 — з фізики. Троє студентів отримали п’ятірки з математики і програмування, 4 — з програмування та фізики, 2 — з математики та
13 фізики. Один студент отримав п’ятірки з усіх трьох дисциплін. Знайти кількість студентів, які a. Не отримали жодної п’ятірки; b. Отримали рівно одну п’ятірку.
5) Троє з 23 мандрівників не були жодного разу ні у Парижі, ні у Лондоні, ні у Римі,
12 було у Лондоні, 10 — у Римі, 4 — тільки у Парижі, 4 — і у Парижі, і у Лондоні,
6 — і у Лондоні, і у Римі, 5 — і у Парижі, і у Римі. Знайти кількість мандрівників, які були в усіх трьох містах.
6) За результатами сесії жоден з 25 студентів групи не отримав двійку, 9 мають при- наймні одну оцінку «задовільно», 16 — «добре», 8 — «відмінно». Десять студентів склали усі свої іспити на оцінку «добре», 4 — на «відмінно», 4 — на «задовільно».
Один студент має усі три можливі позитивні оцінки. Знайти кількість студентів, які склали усі свої іспити на "відмінно" та "добре".
7) У класі навчається 24 учнів. Із них 9 відвідують танцювальний гурток, 8 — дра- матичний, 8 — гурток з малювання. Троє школярів займаються і у танцювальному
і у драматичному гуртках, 5 — і у танцювальному і гуртку з малювання, 3 — лише у драматичному, 2 — в усіх трьох гуртках. Скільки школярів відвідують хоча б один гурток?
8) Із 25 туристів 15 чоловік знають англійську мову, 8 — німецьку. Троє знають французьку і англійську, один — французьку і німецьку, четверо — англійську і німецьку, один — усі три мови. Знайти кількість туристів, які знають лише французьку мову, за умови, що двоє туристів не знають жодної з трьох мов.
9) У групі вчиться 27 студентів. Відомо, що 6 студентів отримали п’ятірку з мате- матики, 7 — з програмування, 8 — з фізики. Троє студентів отримали п’ятірку з математики і програмування, 4 — з програмування та фізики, 2 — з математики та фізики. Один студент отримав п’ятірки з усіх трьох дисциплін. Знайти кількість студентів, які отримали не більше однієї п’ятірки.
10) Двоє з 23 мандрівників не були жодного разу ні у Парижі, ні у Лондоні, ні у Римі,
12 було у Лондоні, 10 — у Римі, 4 — тільки у Парижі, 4 — і у Парижі, і у Лондоні,
6 — і у Лондоні, і у Римі, 5 — і у Парижі, і у Римі. Знайти кількість мандрівників, які були більше, ніж у одному місті.
5. З використанням методу математичної індукції довести, що для довільного нату- рального n
1) Число
1 2
1 7
8
n
n
націло ділиться на 19.
2)
1 2
3 1 2 3 2 3 4 ...
1 2
4
n n
n
n
n n
n
3)
1 2
2 2
2 1
2
(
1)
1 2
3 4
... ( 1)
1 2
n
n
n n
n
4)
1 1
1 2 2 3 ...
1 3
n
n n
n
n
5) Число
3 7
n
n
націло ділиться на 6.
6)
2 4
4 4
1 2 1
1 1
1 9
1 2 2
1
n
n
n
14 7) Число
2 2
1
n
закінчується цифрою 7
1
n
8)
2 4
3
n
n
n
9)
1 1
1 1 3 3 5 2
1 2 1
2 1
n
n
n
n
10)
1 1
1 1 4 4 7 3
2 3 1
3 1
n
n
n
n
6. Нехай S — множина усіх квадратів, R — множина усі прямокутників, L — множина усіх ромбів, Р — множина усіх правильних многокутників площини. Знайти множини
1)
\
\
L S
R P
2)
\
\
P S
R L
3)
\
R
S
L P
4)
\
\
S L
P R
5)
\
S
P
L R
6)
L
P
R
S
7)
\
P S
R
L
8)
P
S
L
R
L
9)
\
\
L P
S
R
10)
\
R
P
L S
15
2. БІНАРНІ ВІДНОШЕННЯ
2.1. Основні означення та позначення
Декартовим добутком множин А та В називається множина
A B
усіх упоряд- кованих пар, перший елемент яких належить множині А, а другий — множині В. Тобто,
def
,
,
A B
a b a
A b
B
. При цьому порядок множників є суттєвим.
Бінарним відношенням, визначеним на базисних множинах А та В, називається довільна підмножина декартового добутку цих множин. Той факт, що елементи a A
та
b
B
перебувають у бінарному відношенні R позначається як a Rb або
,
a b
R
Бінарне відношення називається однорідним, якщо його базисні множини спів- падають.
Оскільки бінарні відношення є множинами, то для їх задання можна використо- вувати ті самі способи, що і для множин. Крім того, якщо бінарні відношення задані на скінченних множинах, то їх можна задавати за допомогою матриць відношень та графів
(діаграм) відношень.
При матричному способі задання відношення елементам множини А ставляться у відповідність рядки матриці
M R , елементам множини В — стовпці. Якщо пара
,
a b перебуває у відношенні R, то на перетині відповідного їм рядка та стовпця матриці запи- сується одиниця, інакше — нуль.
При графічному способі задання відношень елементам множин А та В ставляться у від- повідність точки на площині. Якщо пара
,
a b перебуває у відношенні, то точка, яка від- повідає елементу а, з’єднується направленим відрізком із точкою, яка відповідає елементу b.
Проілюструємо матричний та графічний спосіб задання відношень на прикладі відношення
,1 ,
,2 ,
,4 ,
,1 ,
,4
R
a
a
b
d
f
, заданого на множинах
, , , , ,
A
a b c d e f
та
1,2,3,4
B
. Тоді матриця відношення R має вигляд
1 1
0 0
0 0
0 1
0 0
0 0
1 0
0 0
0 0
0 0
0 0
0 1
M R
Граф відношення наведено на рис. 6.
Рис. 6. Граф відношення R
16
Множини
1
pr
,
R
x x y
R
та
2
pr
,
R
x x y
R
відповідно називаються першою та другою проекціями відношення R. Для відношення R із попереднього прик- ладу
1
pr
, , ,
R
a b d f
,
2
pr
1,2,4
R
Множина
,
,
R C
y c y
R c
C
називається зрізом бінарного відношення R за підмножиною С першої базисної множини А.
Для відношення R із попереднього прикладу
,
1,2
R
a d
Зріз
R
a
називається зрізом бінарного відношення за елементом а. Часто для од- ноелементних зрізів використовують позначення
R a .
Множина усіх одноелементних зрізів бінарного відношення R, визначеного на мно- жині А, називається фактор-множиною множини А за відношенням R і позначається
/
A R .
Наприклад, для відношення R із діаграмою, наведеною на рис. 6,
1,2
R a
,
4
R b
R f
,
R c
R e
. Тому
/
1,2 , 4 ,
R A
1 2 3 4 5 6 7