- •Буковинський університет
- •Дискретна математика
- •Навчально-методичний посібник
- •Чернівці
- •Задачі та вправи 12
- •Задачі та вправи 28
- •Операції над множинами
- •Тема „Алгебра лінійних множин”
- •Способи задання множин
- •Порожня множина ()
- •Універсум (u)
- •Множина підмножин
- •Алгебра множин
- •Узагальнення операцій над множинами
- •Задачі до теми „Алгебра лінійних множин”
- •Тема „Відношення і функції”
- •Окремі випадки відношень
- •Властивості композицій:
- •Властивості відношень
- •Основні властивості відображень
- •Відношення еквівалентності
- •Відношення порядку
- •Відношення рівнопотужності
- •Властивості скінченних множин
- •Властивості зчисленних множин
- •Задачі до теми „Відношення і функції”
- •Тема „Булеві функції”
- •Способи задання булевих функцій
- •Булеві функції однієї змінної
- •Область визначення булевих функцій
- •Елементарні функції алгебри логіки
- •Булевий простір
- •Властивості функцій
- •Деякі операції над висловленнями
- •Формули в алгебрі логіки
- •Основні тотожності
- •Правила
- •Принцип двоїстості
- •Типи булевих функцій
- •Канонічні форми перемикальних функцій
- •Досконалі диз’юнктивні нормальні форми перемикальних функцій
- •Досконалі кон’юнктивні нормальні форми перемикальних функцій
- •Властивості досконалих форм
- •Скорочена диз’юнктивна нормальна форма перемикальних функцій
- •Утворення скороченої диз’юнктивної нормальної форми методом Квайна
- •Метод Квайна-Маккласкі
- •Утворення мінімальних кон’юктивних нормальних форм
- •Алгоритм утворення мінімальної кнф
- •Геометричне подання функцій алгебри логіки
- •Спрощення булевих функцій
- •Задачі до теми „Способи задання булевих функцій. Операція суперпозиції”
- •Задачі до теми „Істотні та фіктивні змінні”
- •Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
- •Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
- •Задачі до теми „Класи функцій, що зберігають константи”
- •Задачі до теми „Двоїстість і клас самодвоїстих функцій”
- •Задачі до теми „Монотонність і клас монотонних функцій”
- •Повнота систем булевих функцій
- •Тема „Рекурсивні функції”
- •Частково-рекурсивні функції
- •Тема „Скінченні автомати. Машина Тьюринга”
- •Машина Тьюринга
- •Тема „Основні поняття і властивості алгоритмів”
- •Основні вимоги до алгоритмів
- •Основні властивості алгоритму
- •Тема „Формальні системи. Алгебра висловлювань”
- •Аксіоматичний спосіб опису висловлювань
- •Властивості числення висловлювань
- •Задачі до теми „Алгебра висловлювань”
- •Тема „Логіка і числення предикатів”
- •Рівносильність формул
- •Задачі до теми „Логіка і числення предикатів”
- •Тема „Алгебри. Типи алгебр. Алгебраїчні системи”
- •Гомоморфізм та ізоморфізм алгебри
- •Типи алгебр
- •Алгебраїчні системи
- •Тема „Елементи комбінаторики”
- •Формула включень і виключень
- •Рекурентні співвідношення
- •Основні властивості кількості сполук
- •Біном Ньютона
- •Властивості розкладу бінома Ньютона і біномних коефіцієнтів
- •Поліномні твірні функції
- •Розміщення і функціональні відображення
- •Розбиття
- •Поліномна формула
- •Задачі до теми „Комбінаторика”
- •Тема „Графи”
- •Задання графа за допомогою матриці інцидентності та списку ребер
- •Задання графа за допомогою матриці суміжності
- •Локальні степені вершин графа
- •Частини графа, суграфи та підграфи
- •Операції з частинами графа
- •Маршрути, ланцюги та цикли
- •Цикломатичне число графа
- •Задачі до теми „Графи”
- •Дискретна математика
- •Література
- •Навчальне видання Пукальський Іван Дмитрович,
- •Лусте Ірина Петрівна,
Розміщення і функціональні відображення
Позначимо через Y* множину всіх відображень f: X Y.
Твердження 1. Нехай |X| = r, |Y| = n. Тоді
|Y*| = U(n, r) = nr = |Y||x|. (1)
Нехай X = {x1, ..., xr}. Тоді будь-яке відображення f: X Y можна подати у вигляді впорядкованої послідовності <f(x1), ..., f(x2)> значень функції f у точках X, де f(xi) Y. Очевидно, що цим самим установлено взаємно однозначну відповідність між множиною функціональних відображень та множиною впорядкованих вибірок із повторенням обсягу r із множини Y обсягом n (тобто множиною r-перестановок з n елементів із повторенням). Звідси випливає правильність рівності (1).
Твердження
2.
Нехай |X|
= r,
|Y|
= n.
Тоді кількість всіх ін’єктивних
відображень вигляду f:
X
Y
дорівнює P(n,
r)
=
.
Наслідок
1.
Для Sn
– множини всіх бієктивних відображень
n-елементної
множини в себе маємо |Sn|
=
= P(n,
n)
= n!.
Приклад 2. Задано квадрат, розділений на чотири частини:
-
1
2
4
3
Скількома способами можна розфарбувати квадрат п’ятьма кольорами, якщо: а) допускається фарбування різних частин в один колір; б) різні частини зображаються різними кольорами?
Для
розв’язання будемо розглядати кожне
розфарбування як функціональне
відображення множини номерів квадрата
X
= {1, 2, 3, 4}
у множину кольорів Y,
де |Y|
= 5.
Тоді використовуючи твердження 1, 2,
маємо: а) 54
= 625; б)
= 5! = 120.
Приклад
3.
Знайти, скількома способами можна
вибрати 5 номерів із 36. Розв’язком буде
число (36,5)-сполучень:
= 376992.
Приклад 4. У скількох випадках при грі “Спортлото” (угадування 5 номерів з 36) будуть правильно вибрані: а) рівно 3 номери; б) рівно 4 номери; в) рівно 5 номерів; г) не менше як 3 номери.
Маємо:
а) 3 правильні номери із 5 можна вибрати
способами, а 2 неправильних номери, що
залишилися, –
способами. Далі за правилом множення
визначаємо, що шукана кількість дорівнює
=
= 4650.
В інших випадках відповідно знаходимо:
б)
= 155;
в) 2;
г) 4650 + 155 +
1 = 4806.
Розбиття
Підрахуємо
кількість розбиттів скінченної множини
X,
де |X|
= n,
на k
підмножин X1,
..., Xk
(k
1), де
=
n,
таких, що кожне Xi
містить ni
елементів, тобто
= X,
Xi
Xj
=
при i
j,
|Xi|
= ni,
i
= 1, 2, ..., k. (2)
Нехай
для деяких номерів i
матимемо Xi
= .
Кількість зазначених розбиттів при
фіксованих ni
позначимо через
.
У цьому випадку набір підмножин множини X у розбитті є впорядкованим (тобто X1, ..., Xk – впорядкована послідовність множин).
Справджується
рівність
=
.
Для
утворення сполучення, що відповідає
множині X1,
можуть бути використані всі елементи
множини X,
тобто множина X1
може бути вибрана
способами. Після вибору X1
множина X2
може бути вибрана
способами (оскільки X2
є підмножиною множини X
\ X1
та |X
\ X1|
= n
– n1)
і для будь-якого i,
де 2
i
k,
після вибору множин X1,
..., Xi
– 1
множина Xi
може бути вибрана
способами.
...
=
...
=
=
=
=
.
Приклад. У студентській групі, яка складається з 25 осіб, при виборі старости за висунену кандидатуру проголосували 12 чоловік, проти – 10, утрималися – 3. Скількома способами могло бути проведене таке голосування?
Розв’язування.
Нехай X
– множина студентів у групі: X1
– множина студентів, які проголосували
за висунену кандидатуру; X2
– множина студентів, які проголосували
проти; X3
– множина студентів, які утрималися
від голосування. Тоді |X|
= 25, |X1|
= 12, |X2|
= 10, |X3|
= 3, X
= X1
X2
X3,
Xi
Xj
= ,
i
j,
а, отже, шукана кількість дорівнює
=
= 1487285800.
Кількість , де ni 0, = n, дорівнює числу Pn(n1, ..., nk) переставлень n елементів зі специфікацією {n1, n2, ..., nk}, серед елементів яких міститься n1 елементів першого типу, n2 елементів другого типу і т.д., аж до елементів k-го типу.
Підрахуємо
тепер, скількома способами можна розбити
множину X,
де |X|
= n,
на підмножини, серед яких для кожного
i
= 1, 2, ..., n
існують mi
0 підмножин з i
елементами, де
= n.
При цьому набір множин не є впорядкованим.
Так розбиття множини X
= {1, 2, 3, 4, 5} вигляду
{1, 3}, {4}, {2, 5}; {4}, {2, 5}, {1, 3}; {2, 5}, {4}, {1, 3}
вважають однаковими. Позначимо кількість невпорядкованих розбиттів множини X через N(m1, ..., mn).
Справедлива рівність
N(m1,
..., mn)
=
.
Кожне з невпорядкованих розбиттів, розглянутих при визначені величини N(m1, ..., mn), можна, нумеруючи множини в цьому розбитті, привести m1! ... mn! способами до впорядкованих розбиттів вигляду
X1,
...,
,
,
...,
,
...,
,
...,
, (1)
де
|X1| = ... = | | = 1, | | = ... = | | = 2, ...,
| =... = | | = n. (2)
При цьому об’єднанні попарно непересічних множин число розбиттівдорівнює
N(m1, ..., mn) = .
Приклад. Скількома способами з групи 25 чоловік можна сформувати 5 коаліцій по 5 чоловік.
Розв’язування.
Нехай X
– множина людей у групі, mi
– кількість коаліцій по i
осіб, де i
= 1, 2, ..., 25. Тоді за умовою задачі |X|
= 25, m5
= 5, mi
= 0, i
{1, 2, ..., 25} \ {5}, а отже, шукана кількість
дорівнюватиме N(0,
0, 0, 0, 5, 0, ..., 0) =
=
.
