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

🎯 Вступ до дискретної математики

Дискретна математика - це галузь математики, що вивчає дискретні (окремі, перелічувані) об'єкти, на відміну від неперервних об'єктів у математичному аналізі. Вона є основою комп'ютерних наук та інформатики, оскільки комп'ютери працюють з дискретними даними.

🔑 Ключові розділи:

Теорія множин: Основи роботи з множинами та їх операціями

Логіка: Формальна логіка, булева алгебра та докази

Комбінаторика: Підрахунок та перестановки

Теорія графів: Структури та зв'язки між об'єктами

📊 Теорія множин

🔢 Основні поняття

Визначення множини

Множина - це сукупність різних об'єктів, які називаються елементами множини.

🔧 Операції над множинами

A ∪ B = {x | x ∈ A або x ∈ B}

Приклад: {1,2} ∪ {2,3} = {1,2,3}

A ∩ B = {x | x ∈ A і x ∈ B}

Приклад: {1,2} ∩ {2,3} = {2}

A \ B = {x | x ∈ A і x ∉ B}

Приклад: {1,2,3} \ {2,3} = {1}

A' = {x | x ∉ A}

Приклад: Якщо U = {1,2,3,4}, то {1,2}' = {3,4}

📋 Властивості множин

Комутативність: A ∪ B = B ∪ A, A ∩ B = B ∩ A

Асоціативність: (A ∪ B) ∪ C = A ∪ (B ∪ C)

Дистрибутивність: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Закони де Моргана: (A ∪ B)' = A' ∩ B'

// Приклади множин: A = {1, 2, 3, 4, 5} // Кінцева множина B = {x | x є парним числом} // Множина парних чисел C = ∅ // Порожня множина

🧠 Логіка

🔍 Пропозиційна логіка

Логічні операції

p ∧ q істинна тільки коли обидва p і q істинні

p ∨ q істинна коли хоча б одне з p або q істинне

p → q хибна тільки коли p істинна, а q хибна

p ↔ q істинна коли p і q мають однакові значення істинності

📜 Квантори

Універсальний квантор (∀)

∀x P(x) означає "для всіх x, P(x) істинна"

Приклад: ∀x (x² ≥ 0) - для всіх дійсних чисел x, x² ≥ 0

Екзистенційний квантор (∃)

∃x P(x) означає "існує x такий, що P(x) істинна"

Приклад: ∃x (x² = 4) - існує число x таке, що x² = 4

🔢 Комбінаторика

📊 Основні принципи підрахунку

Правило суми

Якщо задача може бути виконана n способами, а друга задача - m способами, і ці задачі не можуть бути виконані одночасно, то є n + m способів виконання однієї з цих задач.

Правило добутку

Якщо задача може бути виконана n способами, а друга задача - m способами, то є n × m способів виконання обох задач послідовно.

🔄 Перестановки та комбінації

Перестановки (P)

Кількість способів розмістити r об'єктів з n об'єктів у певному порядку:

P(n,r) = n!/(n-r)!

Приклад: P(5,3) = 5!/(5-3)! = 5!/2! = 60

Комбінації (C)

Кількість способів вибрати r об'єктів з n об'єктів без урахування порядку:

C(n,r) = n!/(r!(n-r)!)

Приклад: C(5,3) = 5!/(3!2!) = 10

🎲 Спеціальні розподіли

Біноміальний коефіцієнт

Коефіцієнти в розкладанні (a + b)ⁿ:

(a + b)ⁿ = Σ(k=0 to n) C(n,k) a^(n-k) b^k

Принцип включення-виключення

Для множин A₁, A₂, ..., Aₙ:

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)^(n+1)|A₁ ∩ A₂ ∩ ... ∩ Aₙ|

P(n,r) = n!/(n-r)!

🌐 Теорія графів

📈 Основні поняття

Граф

Граф G = (V, E) складається з множини вершин V та множини ребер E.

Неорієнтований граф: Ребра не мають напрямку

Орієнтований граф (диграф): Ребра мають напрямок

Зважений граф: Ребра мають ваги

Повний граф: Кожна вершина з'єднана з кожною іншою

🔗 Властивості графів

Кількість ребер, інцидентних вершині

Лема: Σ(deg(v)) = 2|E|

Послідовність вершин, де кожні дві сусідні вершини з'єднані ребром

Шлях, що починається і закінчується в одній вершині

Граф зв'язний, якщо між будь-якими двома вершинами існує шлях

🌳 Спеціальні типи графів

Дерево

Зв'язний граф без циклів

Властивості:

|E| = |V| - 1

Між будь-якими двома вершинами існує єдиний шлях

Біпартитний граф

Граф, вершини якого можна розділити на дві множини так, що жодне ребро не з'єднує вершини в одній множині

Планарний граф

Граф, який можна намалювати на площині без перетинів ребер

Формула Ейлера: V - E + F = 2

🔢 Теорія чисел

📊 Основні поняття

Дільність

Число a ділить число b (позначається a | b), якщо існує ціле число c таке, що b = ac.

Якщо a | b і b | c, то a | c

Якщо a | b і a | c, то a | (b + c)

Якщо a | b, то a | bc для будь-якого цілого c

🔢 НСД та НСК

gcd(a,b) - найбільше число, що ділить і a, і b

gcd(a,b) = gcd(b, a mod b)

lcm(a,b) - найменше число, що ділиться на і a, і b

lcm(a,b) = (a × b) / gcd(a,b)

🔐 Модульна арифметика

Конгруентність

a ≡ b (mod n) означає, що n ділить (a - b)

a ≡ a (mod n)

Якщо a ≡ b (mod n), то b ≡ a (mod n)

Якщо a ≡ b (mod n) і b ≡ c (mod n), то a ≡ c (mod n)

Якщо a ≡ b (mod n), то a + c ≡ b + c (mod n)

Якщо a ≡ b (mod n), то ac ≡ bc (mod n)

gcd(a,b) = gcd(b, a mod b)

🎯 Практичні застосування

💻 Програмування

Алгоритми, структури даних, оптимізація коду

🔐 Криптографія

Модульна арифметика, теорія чисел, безпека

🤖 Штучний інтелект

Логіка, графові алгоритми, комбінаторна оптимізація

🌐 Мережі

Теорія графів, алгоритми маршрутизації, топологія мереж

📚 Рекомендована література

"Discrete Mathematics and Its Applications" - Kenneth Rosen

"Concrete Mathematics" - Ronald Graham, Donald Knuth, Oren Patashnik

"Introduction to Graph Theory" - Richard Trudeau

"Discrete Mathematics" - Norman Biggs

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Spirograph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.