# ОДМ — Лекції

Лекційна складова дисципліни **«Основи дискретної математики»** (українська мова
навчання). Файли `ODM-L<NN>.md` — це **підручникового типу, самодостатні** конспекти
лекцій: мотивація, означення, **доведені** теореми, розв'язані приклади, зауваження,
типові помилки, вправи та підсумок — по одному розділу на лекцію. Курс має **9
лекційних занять** (по 2 год), згрупованих у 5 змістових модулів.

## Розташування

Тут лежать розділи `ODM-L01.md … ODM-L09.md`, їхні ілюстрації в [`img/`](img/) та
презентації в [`Slides/`](Slides/). Номер розділу збігається з номером лекції.

## Зміст

### Модуль 1 — Множини та відношення
| № | Назва | Фокус |
|:--:|---|---|
| 1 | [Алгебра множин](ODM-L01.md) | множини, способи задання, порівняння, множина-ступінь, діаграми Венна й круги Ейлера, операції та закони алгебри множин, рівнопотужність |
| 2 | [Алгебра відношень](ODM-L02.md) | кортежі, декартів добуток, відношення та способи їх задання, властивості й типи відношень, функції та відображення, реляційна алгебра |

### Модуль 2 — Булева алгебра
| № | Назва | Фокус |
|:--:|---|---|
| 3 | [Основи булевої алгебри. Алгебра Жегалкіна](ODM-L03.md) | алфавіт, таблиця істинності, булеві операції, аксіоми й закони, базиси (ТА-АБО-НІ, NAND, NOR), алгебра Жегалкіна |
| 4 | [Мінімізація виразів. Логічні схеми](ODM-L04.md) | логічні елементи й мікросхеми, мінімізація законами, канонічні форми (ДДНФ/ДКНФ), карти Карно, побудова логічних схем |

### Модуль 3 — Логіка першого порядку
| № | Назва | Фокус |
|:--:|---|---|
| 5 | [Математична логіка](ODM-L05.md) | висловлення, алгебра висловлювань, інтерпретація й формалізація, типи формул, логічний наслідок, правила виводу, числення висловлювань |
| 6 | [Логіка предикатів](ODM-L06.md) | предикати, функціональні символи, квантори, закони алгебри предикатів, випереджена нормальна форма, основи Prolog |

### Модуль 4 — Теорія графів
| № | Назва | Фокус |
|:--:|---|---|
| 7 | [Основи теорії графів](ODM-L07.md) | термінологія, матриці суміжності й інцидентності, орієнтовані та зважені графи, маршрути, ізоморфізм, планарність, розфарбування, дерева |
| 8 | [Алгоритми на графах](ODM-L08.md) | алгоритм Дейкстри, мінімальне остовне дерево (Прима, Крускала), транспортні мережі, алгоритм Форда — Фалкерсона |

### Модуль 5 — Комбінаторика
| № | Назва | Фокус |
|:--:|---|---|
| 9 | [Основи комбінаторики та теорії ймовірностей](ODM-L09.md) | події та ймовірність, умовна ймовірність, теореми додавання й множення, формула Байєса, перестановки/розміщення/сполучення, математичне сподівання й дисперсія |

## Як користуватися

Опрацьовуйте розділи послідовно — кожен спирається на попередні. Читайте доведення
**активно**: на кожному кроці запитуйте «чому цей крок дозволений?». Означення
подано **напівжирним**; результати, які варто вміти доводити, оформлені як
**Теореми / Твердження / Леми**. Виконуйте вправи для розігріву під час читання та
кілька задач наприкінці.

## Слайди

Презентації — у теці [`Slides/`](Slides/), по одній на лекцію: `ODM-L01`…`ODM-L09`,
а також вступний огляд `ODM-L00` (структура курсу).

## Швидкий довідник позначень

| Символ | Значення | | Символ | Значення |
|:--:|---|---|:--:|---|
| $\in,\notin$ | (не)належність | | $\wedge,\vee,\neg$ | і, або, не |
| $\subseteq,\subset$ | підмножина, власна підмножина | | $\to,\leftrightarrow$ | імплікація, еквіваленція |
| $\varnothing$ | порожня множина | | $\oplus$ | додавання за модулем 2 (XOR) |
| $\cup,\cap,\setminus$ | об'єднання, перетин, різниця | | $\forall,\exists$ | квантори загальності, існування |
| $\overline{A}$ | доповнення | | $\equiv$ | логічна рівносильність |
| $A\times B$ | декартів добуток | | $\binom{n}{k}$ | біноміальний коефіцієнт |
| $\lvert A\rvert$ | потужність | | $P(A\mid B)$ | умовна ймовірність |
| $\mathcal P(A)$ | множина-ступінь | | $\deg(v)$ | степінь вершини |
| $\mathbb{N,Z,Q,R}$ | числові множини | | $\blacksquare$ | кінець доведення |

## Додаткова література

- Бондаренко М. Ф., Білоус Н. В., Руткас А. Г. *Комп'ютерна дискретна математика*.
- Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. *Дискретна математика*.
- Тмєнова Н. П. *Дискретна математика: теорія множин і відношень, комбінаторика,
  числення висловлювань*.