Дискретна математика

\ Bookfoldsheets0 Федеральне агентство з освіти РФ
«Дискретна математика»
(КОНСПЕКТ ЛЕКЦІЙ)

Викладач: професор,

Архипов Ігор Костянтинович

1. МНОЖИНИ
Безліч - сукупність елементів, що володіють якимось одним загальним властивістю. (Це визначення не є строгим, воно лише показує особливості побудови множин, тобто для побудови безлічі важливо вказати властивість, яке мають усі його елементи).
Якщо кожному елементу безлічі можна присвоїти номер і цей номер не повторюється, то така безліч називається рахунковим або кінцевим.
Якщо такого номера для кожного елемента не існує, то така безліч називається нескінченним.
Нескінченна безліч часто називають континуумом (наприклад: сукупність точок на площині).
Якщо можна перерахувати всі число елементів у рахунковому безлічі, то ця сума називається потужністю множини.
Множини задаються різними способами:
1. За допомогою перерахування всіх його елементів.
{0,1,2,3,4,5,6,7,8,9}
2. Алгоритмічна форма (у вигляді послідовності або фомула).
а) кінцеве
М = {2; 4; 6; 8} <=> М = {m | 2n; n-ціле; 1 <= n <= 4}
б) нескінченне
А = {х | | х-1 | <3}

2. ВЛАСТИВОСТІ РАХУНКОВОЇ МНОЖИН
1. Будь-яке підмножина рахункового безлічі звичайно або лічильно
Підмножиною множини А називається безліч А `всі елементи якого належать безлічі А

Приклад:
2. Сума кінцевого або рахункового числа кінцевих або лічильних множин є кінцеве або зліченна множина.
3. Безліч всіх раціональних чисел зліченна.
4. Алфавітом називається будь-яке непорожнє безліч.
Порожня множина - безліч, яке не містить жодного елемента.
Елементи множини під назвою Алфавіт називають буквами (символами).
Символом в даному алфавіті будь-яка кінцева послідовність літер.
Для кожного безлічі А існують множини, елементами якого є тільки всі його підмножини.
Таке підмножина називають сімейством множин А чи булеаном. (Позначається В (А))
Будемо називати вектором (кортежем) упорядкований набір елементів і позначати його , Зауважимо, що на відміну від безлічі, елементи у векторі можуть повторюватися. Ці елементи називаються координатами або проекціями.
Кількість елементів у векторі називається його довжиною, якщо у векторі 2 елементи, то двійка, якщо n елементів, то n-ка.
Теорія множин будується на основі систем аксіом.
1. Аксіома існування: Існує принаймні одну безліч.
2. Аксіома об'ємності: Якщо множини А і В складені з одних і тих же елементів, то вони збігаються.
3. Аксіома об'єднання: Для довільних множин А і В існує безліч, елементами якого є всі елементи множини А і всі елементи множини В і ніякі інші елементи безліч не містить.
4. Аксіома різниці: Для довільних множин А і В існує безліч, елементами якої є ті й тільки ті елементи множини А, які не містяться в множині В.
5. Аксіома існування порожньої множини: Існує безліч не містить жодного елемента.

3. ОСНОВНІ ОПЕРАЦІЇ над безліччю
1. Включення (об'єднання)
Безліч А входить (включено) у множину B, або А є підмножиною В.
Якщо будь-який об'єкт, що володіє властивістю , Також має властивість , То говорять, що властивість включає властивість , Тобто
2. Сума
Сума множин А і В є безліч С, що включає в себе всі елементи безліч А і В.
Об'єкт входить в безліч якщо він входить у безліч А або в безліч В.

3. Перетин (твір)
Перетином безліч А і В називається нова безліч С. Елементи множини З належать безлічі А (мають його властивостями) і безлічі В (мають його властивостями).

4. Віднімання (різниця)
Різниця множин А і В є безліч С, елементи якого володіють властивостями множини А і не мають властивості безлічі В або належать безлічі А і не належать безлічі В.

5. Доповнення
Якщо є якийсь універсальний безліч (універсум) U і всі розглянуті множини є його підмножини, то доповненням називається така безліч, елементи якого не входять в А, але належать U.

ГРАФІЧНЕ ПРЕДСТАВЛЕННЯ

(Діаграми еймерій, Венна)

А

У

1.

А

У

2.

У

А

3.

А

U

4.

4. ПРЯМЕ ТВІР А х В
Прямим твором множин А і В називається множина М всіх пар ( ), Таких, що
Якщо А = В, то такий твір називається
Аналогічно можна вивести операцію прямого твори більшого числа множин.


Якщо зокрема однакові то отримуємо
(Наприклад, безліч точок на площині є прямим добутком двох множин).
Якщо безлічі кінцеві, потужність творів дорівнює потужності творів
5. ОСНОВНІ Тотожність АЛГЕБРИ МНОЖИН
Незалежність розташування:
(1)
(2)
Асоціативність:
(3)
(4)
Дистрибутивність:

(7)
(8)
(9)
(10)
(11)
(12)

ЗАКОНИ де Моргана

6. Елементи комбінаторики І ЇХ ЗАСТОСУВАННЯ В ТЕОРІЇ МНОЖИН
Основне завдання комбінаторики - перерахунок та перелік елементів в кінцевих множинах.
1. Якщо нас цікавить, скільки елементів належать даному кінцевому безлічі мають деяким властивістю, то це завдання перерахунку.
2. Якщо необхідно виділити всі елементи множини, що володіють заданими властивостями, то це завдання перерахування.
Розглянемо наступні елементи комбінаторики, що дозволяють вирішувати вищезазначені завдання. До таких об'єктів належать:
- Перестановки (з повторенням і без них);
- Розміщення (з повторенням і без них);
- Поєднання (з повторенням і без них);
Перестановками називають комбінації, що складаються з одних і тих же елементів і відрізняються лише порядком їх розташування. Число всіх можливих перестановок позначається (Без повторень).
Перестановки з повтореннями обчислюються за формулою:
, Де - Число повторень елементів кожного виду.
Поєднанням називаються такі комбінації елементів, які відрізняються між собою в кожній групі тільки самими елементами (але не порядком їх розташування в групі).
(Без повторення)
(З повторенням)
Розміщенням називаються такі комбінації елементів, які відрізняються між собою або самими елементами або порядком їх розташування в групі.
(Без повторення)
(З повторенням)

7. ПРИНЦИПИ МАТЕМАТИЧНОЇ ІНДУКЦІЇ
При обчисленні елементів множин потрібно наводити доказ, по якому обчислюються наступні елементи за попереднім. Один з алгоритмів цих доказів - принцип математичної індукції.
Цей принцип полягає в наступному:
Нехай при n = 1 доказ очевидно. Приймаються гіпотезу, що воно очевидно при n = k, яке не дорівнює 1 ( ). Тоді, якщо доведено, що потрібне рівність очевидно при k +1, то рівність доведено при будь-якому n.
8. ВІДОБРАЖЕННЯ ВІДНОСИНИ ФУНКЦІЇ
Поняття відображення та функції виражають залежністю одних змінних величин від інших, при цьому слово величина може мати різне смислове навантаження. Це може бути елемент будь-якої безлічі, число, вектор і т.д.
Відображення - безлічі x в безліч y визначається тим, що кожному елементу ставиться у відповідність
- Графічне зображення відображення, f - позначення відображення. Закон, який виражається або у вигляді формули або у вигляді алгоритму, тобто послідовність дій, які треба вжити, щоб отримати залежність елементів безлічі y від елементів x. Наприклад: будь-яка нумерація рахункового множини є його відображенням на безліч натуральних чисел N.
Так як відображення може бути витлумачено як відповідність, то для того, щоб показати, що даний елемент x поставлений у відповідність елементу y, пишуть і кажуть, що y є образ елемента x при даному відображенні f.
Нехай x `- підмножина безлічі x
y `- підмножина безлічі y
тоді

Сукупність елементів множини x, чином яких є y, називається прообразом і позначається
Розглянемо окремі випадки відображення однієї множини в іншу.
1. Якщо кожен елемент множини Y має прообраз, являючи елементом множини X, то в цьому випадку відображення f називається сюр'єктивним.
2. Відображення f називається ін'єктивні, якщо для кожного елемента існує не більше одного прообразу, тобто за будь-яких , Якщо .
Якщо відображення f сюр'єктивним і ін'єктивні, то воно називається біетківним або взаємооднозначної.
Розглянемо на прикладі три функції, що відображають безліч F дійсних чисел саме на себе:
1) - Ін'єктивні, але не сюр'єктивним тому , Проте не кожен y має прообраз x тому y> 0
2) - Сюр'єктивним, але не ін'ектіна, тому що y існує при будь-якому x, однак для образу y існує кілька прообразів, тому що існує кілька коренів кубічного рівняння
3) - Біектівна, тому що x однозначно виражається через x і x однозначно виражається через y.
Два безлічі називаються еквівалентними, якщо між ними можна встановити біектівное відображення.
ТОДІ:
Підмножина називається функцією .
Таким чином функцію можна представити у вигляді графіка, причому безліч А - область визначення функції, а безліч В - область значення функції.
Розглянемо, наприклад, взаємно однозначне відображення множини R на R1, де R1 є безліч всіх позитивних чисел . Зворотним йому буде відображення . Для таких відображень справедливо наступне тотожність:

9. КОМПОЗИЦІЯ
, То їх композицією (твором) називають , Причому, якщо здійснюється композиція, то . У математиці таке відображення називають складною функцією, y - проміжний аргумент.
Для композиції справедливо наступні відображення:
- Комутативне -
- Асоціативне -
10. Бінарні відносини
Квадратом множини А називається декартово твір безлічі саме на себе
Бінарним відношенням Т в багатьох А будемо називати підмножина його квадрата

1. Ставлення виконується для пар (6,8) (6,6)
2. Ставлення має загальний дільник не рівний 1. Виконується для пар (6,4) (4,2) (8,8) але не виконується для пар (5,4) (3,8)
3. Будь-які елементи декартового добутку знаходяться в бінарному відношенні, якщо , Говорять, що пов'язані ставленням Т.
4. Областю значень (зміною бінарного відношення) називається безліч , Підпорядковане умові

Як відомо з курсу математики пару (x, y), де зображують на координатній площині точкою, сукупність усіх відобразиться координатною площиною, а його підмножина, тобто бінарне відношення відобразиться відповідними графіками цих відносин.

2

2

(1)

2

2

(2)
Бінарні відносини на площині можна відобразити за допомогою графів. Елементи множини позначаються вершинами графів. Якщо пара , То вершини а і в з'єднуються ланкою.
Наприклад:
(Ав) (НД) (ас) (аа)

а

в

з

11. ВІДНОСИНИ ЕКВІВАЛЕНТНОСТІ
Визначимо деякі важливі властивості бінарних відносин і розглянемо бінарні відносини, які володіють трьома з цих властивостей і часто зустрічаються в математиці. Таке бінарне відношення називається еквівалентністю.
ВЛАСТИВОСТІ:
1. 1.1 Нехай - Бінарне відношення, - Область його завдання, тоді називається рефлексивним, якщо , Граф таких відносин має вид петлі при кожній вершині

.

.

.

а1

а2

а3

1.2 називається антірефлексівним, якщо
2. 2.1 Ставлення може бути симетричним, якщо
(Зображується будь-яким графом)
2.2 антисиметричних, якщо (Зображується орієнтованим графом)
3. 3.1 транзитивне. Відношення називається транзитивним, якщо (Зображується транзитивним графом - всі вершини перетинаються)
Якщо для бінарного відношення дотримується три умови: рефлексивність, симетричність і транзитивність, то таке відношення називається еквівалентністю.

12. МАТРИЦІ І ГРАФИ
Поняття матриці. Види матриць. Властивості матриць. Лінійні операції над матрицями. Одиничні матриці. Зворотні матриці
Матрицею називається прямокутна таблиця чисел розміром , Де m - число рядків, а n - число стовпців.
Якщо m = n - матриця називається квадратної.
Якщо m-1 - матриця-рядок.
Якщо n = 1 - матриця-стовпець.
Всі числа, що входять у матрицю називаються її елементами. Якщо всі елементи складаються їх нулів, то це нульова матриця, вона грає роль нуля в матричному численні.
Розглянемо деякі лінійні операції над матрицями:
1. Сума

Виходячи з визначення можна складати і віднімати матриці тільки одного розміру.
2. Твір матриці на число називається матриця, де кожен елемент матриці множиться на це число.

3. Матриця множиться на матрицю за правилом рядок на стовпець






таке правило не годиться для всіх матриць, а саме, кількість рядків у другій матриці повинна дорівнювати кількості стовпців у першому матриці.
Квадратні матриці перемножуються тільки одного розміру.
4. Одиничною матрицею називається квадратна матриця будь-якого розміру, де по головній діагоналі стоять одиниці, а всі інші елементи дорівнюють нулю.
, Грає роль одиниці в матричному численні.
Якщо таку матрицю помножити на іншу матрицю (при можливості множення) дасть вихідну матрицю.
- Дельта Кронекера
5. Зворотною матрицею називається матриця, яка , Зауважимо, що Е - квадратна, відповідно теж квадратні.
6. (Визначник), якщо , То зворотна матриця існує, якщо , То матриця називається вироджена.
Знаходження оберненої матриці
1. Метод приєднаної матриці
1.
2.
3.
3.1 (Взаємна)
3.2
4.
5.
2. Метод елементарних перетворень