- •Буковинський університет
- •Дискретна математика
- •Навчально-методичний посібник
- •Чернівці
- •Задачі та вправи 12
- •Задачі та вправи 28
- •Операції над множинами
- •Тема „Алгебра лінійних множин”
- •Способи задання множин
- •Порожня множина ()
- •Універсум (u)
- •Множина підмножин
- •Алгебра множин
- •Узагальнення операцій над множинами
- •Задачі до теми „Алгебра лінійних множин”
- •Тема „Відношення і функції”
- •Окремі випадки відношень
- •Властивості композицій:
- •Властивості відношень
- •Основні властивості відображень
- •Відношення еквівалентності
- •Відношення порядку
- •Відношення рівнопотужності
- •Властивості скінченних множин
- •Властивості зчисленних множин
- •Задачі до теми „Відношення і функції”
- •Тема „Булеві функції”
- •Способи задання булевих функцій
- •Булеві функції однієї змінної
- •Область визначення булевих функцій
- •Елементарні функції алгебри логіки
- •Булевий простір
- •Властивості функцій
- •Деякі операції над висловленнями
- •Формули в алгебрі логіки
- •Основні тотожності
- •Правила
- •Принцип двоїстості
- •Типи булевих функцій
- •Канонічні форми перемикальних функцій
- •Досконалі диз’юнктивні нормальні форми перемикальних функцій
- •Досконалі кон’юнктивні нормальні форми перемикальних функцій
- •Властивості досконалих форм
- •Скорочена диз’юнктивна нормальна форма перемикальних функцій
- •Утворення скороченої диз’юнктивної нормальної форми методом Квайна
- •Метод Квайна-Маккласкі
- •Утворення мінімальних кон’юктивних нормальних форм
- •Алгоритм утворення мінімальної кнф
- •Геометричне подання функцій алгебри логіки
- •Спрощення булевих функцій
- •Задачі до теми „Способи задання булевих функцій. Операція суперпозиції”
- •Задачі до теми „Істотні та фіктивні змінні”
- •Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
- •Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
- •Задачі до теми „Класи функцій, що зберігають константи”
- •Задачі до теми „Двоїстість і клас самодвоїстих функцій”
- •Задачі до теми „Монотонність і клас монотонних функцій”
- •Повнота систем булевих функцій
- •Тема „Рекурсивні функції”
- •Частково-рекурсивні функції
- •Тема „Скінченні автомати. Машина Тьюринга”
- •Машина Тьюринга
- •Тема „Основні поняття і властивості алгоритмів”
- •Основні вимоги до алгоритмів
- •Основні властивості алгоритму
- •Тема „Формальні системи. Алгебра висловлювань”
- •Аксіоматичний спосіб опису висловлювань
- •Властивості числення висловлювань
- •Задачі до теми „Алгебра висловлювань”
- •Тема „Логіка і числення предикатів”
- •Рівносильність формул
- •Задачі до теми „Логіка і числення предикатів”
- •Тема „Алгебри. Типи алгебр. Алгебраїчні системи”
- •Гомоморфізм та ізоморфізм алгебри
- •Типи алгебр
- •Алгебраїчні системи
- •Тема „Елементи комбінаторики”
- •Формула включень і виключень
- •Рекурентні співвідношення
- •Основні властивості кількості сполук
- •Біном Ньютона
- •Властивості розкладу бінома Ньютона і біномних коефіцієнтів
- •Поліномні твірні функції
- •Розміщення і функціональні відображення
- •Розбиття
- •Поліномна формула
- •Задачі до теми „Комбінаторика”
- •Тема „Графи”
- •Задання графа за допомогою матриці інцидентності та списку ребер
- •Задання графа за допомогою матриці суміжності
- •Локальні степені вершин графа
- •Частини графа, суграфи та підграфи
- •Операції з частинами графа
- •Маршрути, ланцюги та цикли
- •Цикломатичне число графа
- •Задачі до теми „Графи”
- •Дискретна математика
- •Література
- •Навчальне видання Пукальський Іван Дмитрович,
- •Лусте Ірина Петрівна,
Відношення порядку
Означення. Бінарне відношення R на множині A називають відношенням порядку, якщо воно антисиметричне ((xiAxj) (xjAxi) xi = xj) і транзитивне ((xiAxj) (xjAxk) (xiAxk).
Якщо
ж відношення порядку до того ще й
рефлексивне (xiAxi),
то воно називається відношенням
нестрогого порядку
і позначається символом „
”.
Якщо
відношення порядку антирефлексивне
((xiAxj)
xi
xj),
то воно називається відношенням строгого
порядку (
).
Приклад. Для відношення нестрогого порядку А = „буде дільником” на множині X = {1, 2, 3, 4} й Y = {1, 2, 3, 4, 6, 7, 12} мають вигляд
A
X
X
=
,
A
Y
Y
=
.
Приклад. Для відношення строгого порядку „>” на множині X = {1, 2, 3, 4, 5} матриця має вигляд
.
Граф цього відношення має вигляд
Якщо A є відношення строгого (нестрогого) порядку, то A -1 теж є відношенням строгого (нестрогого) порядку.
Відношення рівнопотужності
Означення. Множина A рівнопотужна множині B (потужність множини A дорівнює потужності множини B), якщо існує взаємно однозначна відповідність (бієкція) множини A на множину B. Цей факт записують як A ~ B.
Кількість елементів скінченої множині A називають потужністю множини A.
Відношення рівнопотужності має такі властивості:
рефлективності (A ~ A) – відношення, яке виконується між елементом і ним самим;
симетричності (A ~ B B ~ A), що випливає з того, що відображення обернене до взаємно однозначного, також є взаємно однозначним;
транзитивності (A ~ B і B ~ C A ~ C), що випливає з того, що композиція двох взаємно однозначних відображень також взаємно однозначна.
Властивості скінченних множин
Переріз скінченної кількості скінченних множин є скінченним.
Об’єднання скінченної кількості скінченних множин – скінченне.
Декартів добуток скінченної кількості скінченних множин є скінченним.
Множини, що не є скінченними, називаються нескінченними.
Нескінченна множина, рівнопотужна множині натуральних чисел N, називається зчисленною.
Властивості зчисленних множин
Будь-яка підмножина зчисленної множини – скінченна або зчисленна.
Об’єднання скінченної кількості зчисленних множин є зчисленним.
Об’єднання зчисленної кількості скінченних множин є зчисленним.
Об’єднання зчисленної кількості зчисленних множин є зчисленним.
Теорема Кантора. Множина всіх дійсних чисел відрізка [0, 1] не є зчисленною.
Всі числа з відрізка [0, 1] не можуть бути пронумеровані, оскільки множина всіх дійсних чисел відрізка [0, 1] є незчисленною. Її потужність називається континуумом.
Будь-який відрізок дійсної осі має потужність континуум.
Множина правильних дробів має потужність континуум.
Множина, утворена внаслідок вилучення з нескінченної множини елементів зчисленної – рівнопотужна початковій.
Задачі до теми „Відношення і функції”
Схема дослідження бінарних відношень:
а) з’ясувати, до якого типу належить відношення R (відношення еквівалентності, порядку, функціональне відношення);
б) якщо R – відношення еквівалентності, то з’ясувати, які елементи входять у класи еквівалентності;
в) якщо R – відношення порядку, то доцільно з’ясувати якого порядку: строгого, нестрогого чи лінійного;
г) Якщо R (R A B) – функціональне відношення, то з’ясувати, чи є воно відображенням;
д) якщо R – відображення, то яке воно: сюр’єктивне, ін’єктивне чи бієктивне;
е) доцільно записати обернене відношення R–1 і дослідити його за наведеною вище схемою.
Приклад 1. Задати матричним способом та за допомогою діаграми Хассе бінарне відношення на множинах A = {1, 2, 3, 4, 5, 6, 7, 8} і B = {2, 9, 11, 17, 18, 19, 20}:
1) R = {(a, b) | a A, b B; a – дільник b};
2) R = {(a, b) | a A, b B; a – взаємно просте із b};
3) R = {(a, b) | a A, b B; a b};
4) R = {(a, b) | a A, b B; a b};
5) R = {(a, b) | a A, b B; a – b 0};
6) R = {(a, b) | a A, b B; a3 b2};
7) R = {(a, b) | a A, b B; a2 b}.
Розв’язування 1). Зобразимо дане бінарне відношення матрицею
|
2 |
9 |
11 |
17 |
18 |
19 |
20 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
За допомогою діаграми Хассе точками зобразимо елементи множини A B, потім проведемо стрілки від a до b, якщо aRb. Коли ж eRc, то проведемо „петлю” від e до c:
1
2
3
4
5
6
7
8
9
20
11
17
18
19
Приклад
2.
Скільки бінарних відношень існує на
множині з n
елементів? (Відповідь:
).
Приклад 3. Визначити, які з наведених відношень на множині натуральних чисел N рефлексивні, симетричні, анстисиметричні, транзитивні:
1) m + n – парне; 2) m + n 17; 3) m + n – непарне;
4)
–
степінь двійки; 5)
– нескоротний
дріб;
6) mn
– непарне.
Приклад 4. Доведіть, що
1)
якщо R1
R2,
то
;
2)
(
)–1
=
;
3) (R2 R1)–1 = .
Розв’язування задачі 4, 3). Нехай (a, b) (R2 R1)–1, тоді (b, a) R2 R1. А це означає, що при деякому c: (b, c) R2, (c, a) R1. Тоді (a, c) (R1)–1, (c, b) . Звідки (a, b) , Отже, (R2 R1)–1 .
Проведемо доведення у зворотному порядку. Нехай (a, b) . Тоді при деякому c: (a, c) (R1)–1, (c, b) , а це означає, що (c, a) R1 і (b, c) R2. Звідси (b, a) R2 R1. Тоді (a, b) (R2 R1)–1. Отже, (R2 R1)–1. Розглянуту властивість доведено.
Приклад 5. Нехай R1, R2 – рефлексивні та симетричні відношення. Показати, що такі умови еквівалентні:
1) R1 R2 – симетричне;
2) R1 R2 = R2 R1;
3) R1R2 = R1 R2.
Приклад 6. На множині A = {1, 2, ..., 10} визначено відношення: елемент a перебуває у відношенні R з елементом b, якщо a і b мають однакову кількість натуральних дільників. Покажіть, що R – відношення еквівалентності, та випишіть усі класи еквівалентності за відношенням R.
Приклад 7. Розгляньте відношення і з’ясуйте, чи це відношення: а) порядку; б) строгого порядку; в) нестрогого порядку:
1) R = {(1, 2), (2, 2), (2, 3), (1, 3), (4, 3)};
2) R = {(1, 2), (2, 3), (1, 3), (4, 3), (1, 4), (4, 2)};
3)
R
= {(a,
b)
| a
N,
b
N;
b
a}.
Розв’язування задачі 7, 3). Дане відношення рефлексивне, оскільки кожне натуральне число ділиться само на себе. Це відношення – антисиметричне. Справді, якщо (a, b) R, то a b, якщо (b, a) R, то b a, а це можливо лише тоді, коли a = b.
Це відношення – транзитивне, оскільки дільник дільника числа сам є дільником.
Отже, R – відношення нестрогого порядку, причому 2 4, 3 3, оскільки (2, 4) R, (3, 3) R (але (4, 6) R і (6, 4) R).
Приклад 8. Довести, що об’єднання (перетин) двох функцій f1, f2 з A в B є функцією з A в B тоді і тільки тоді, коли f1 = f2.
Приклад 9. Довести, що для кожної функції f
1) f(A B) = f(A) f(B);
2)
f(A
B)
f(A)
f(B);
3) f –1(A B) = f –1(A) f –1(B);
4) f –1(A B) = f –1(A) f –1(B).
Приклад 10. Скільки існує сюр’єктивних відображень з триелементої множини в двоелементну?
Приклад 11. Нехай f, g, h: R R відображення множини дійсних чисел в себе: f(x) = x3 – 4x, g(x) = (x2 + 1)–1, h(x) =x4. Знайти f g h, f h g, h g f, f f, g g, h h, g h, h g.
