ОДМ/Lectures/README
Raw

ОДМ — Лекції

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

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

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

Зміст

Модуль 1 — Множини та відношення

№ Назва Фокус
1 Алгебра множин множини, способи задання, порівняння, множина-ступінь, діаграми Венна й круги Ейлера, операції та закони алгебри множин, рівнопотужність
2 Алгебра відношень кортежі, декартів добуток, відношення та способи їх задання, властивості й типи відношень, функції та відображення, реляційна алгебра

Модуль 2 — Булева алгебра

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

Модуль 3 — Логіка першого порядку

№ Назва Фокус
5 Математична логіка висловлення, алгебра висловлювань, інтерпретація й формалізація, типи формул, логічний наслідок, правила виводу, числення висловлювань
6 Логіка предикатів предикати, функціональні символи, квантори, закони алгебри предикатів, випереджена нормальна форма, основи Prolog

Модуль 4 — Теорія графів

№ Назва Фокус
7 Основи теорії графів термінологія, матриці суміжності й інцидентності, орієнтовані та зважені графи, маршрути, ізоморфізм, планарність, розфарбування, дерева
8 Алгоритми на графах алгоритм Дейкстри, мінімальне остовне дерево (Прима, Крускала), транспортні мережі, алгоритм Форда — Фалкерсона

Модуль 5 — Комбінаторика

№ Назва Фокус
9 Основи комбінаторики та теорії ймовірностей події та ймовірність, умовна ймовірність, теореми додавання й множення, формула Байєса, перестановки/розміщення/сполучення, математичне сподівання й дисперсія

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

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

Слайди

Презентації — у теці 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 квантори загальності, існування
A‾\overline{A} доповнення ≡\equiv логічна рівносильність
A×BA\times B декартів добуток (nk)\binom{n}{k} біноміальний коефіцієнт
∣A∣\lvert A\rvert потужність P(A∣B)P(A\mid B) умовна ймовірність
P(A)\mathcal P(A) множина-ступінь deg⁡(v)\deg(v) степінь вершини
N,Z,Q,R\mathbb{N,Z,Q,R} числові множини ■\blacksquare кінець доведення

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

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

Lectures/README.md · 6.7 KB · updated 2026-08-04 14:08