Дискретна математика: шпаргалка-підсумок

Аркуші з формулами, ключові кроки методів для кожної теми та 8 задач для практики, з повними розв’язками наприкінці.

Нові задачі Назад до курсу

У вікні друку виберіть «Зберегти як PDF», щоб зберегти копію на пристрої.

1Формули та методи

Логіка висловлювань і доведення

Рядки таблиці істинності: 2ⁿ
Імплікація: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Заперечена імплікація: ¬(p → q) ≡ p ∧ ¬q
Еквіваленція: p ↔ q ≡ (p → q) ∧ (q → p)
Закони де Моргана: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Закони дистрибутивності: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Заперечення кванторів: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Метод

Порахуйте різні змінні: таблиця істинності має 2ⁿ рядків, і починається вона з рядка, де всі змінні дорівнюють 1.
Дайте кожній підформулі власний стовпець і заповнюйте стовпці зсередини назовні.
Застосовуйте правило кожного зв’язника: → дорівнює 0 лише для 1 → 0, ↔ дорівнює 1, коли обидві частини збігаються.
Для еквівалентностей порівнюйте останні стовпці рядок за рядком; для міркування дивіться лише на рядки, де кожна передумова дорівнює 1.
Щоб заперечити твердження з квантором, перенесіть ¬ досередини, поміняйте ∀ і ∃ та заперечте внутрішню формулу.

Множини, відношення та функції

Дві множини: |A ∪ B| = |A| + |B| − |A ∩ B|
Три множини: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Різниця та доповнення: A − B = A ∩ B′, |A′| = |U| − |A|
Булеан і декартів добуток: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Підмножини розміру k: C(n, k) = n!/(k!(n − k)!)
Функції A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Відношення на n елементах: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Композиція: (g ∘ f)(x) = g(f(x))

Метод

Намалюйте діаграму Вена й вирішіть область за областю, що належить множинному виразу.
У задачах на підрахунок заповнюйте області від центру назовні: спочатку всі множини, потім пари, потім окремі множини, потім зовнішню частину.
Використовуйте принцип включення–виключення для перевірки: |A ∪ B| = |A| + |B| − |A ∩ B|.
Для відношення перевіряйте кожну властивість на кожній парі й наводьте один контрприклад, коли вона не виконується.
Для функції порахуйте стрілки, що приходять до кожного елемента B: не більше однієї означає ін’єктивність, щонайменше одна — сюр’єктивність.

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

Лема про рукостискання: Σ deg(v) = 2|E|
Повні графи: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Регулярний граф: |E| = n·k/2
Дерево і ліс: |E| = n − 1, |E| = n − c
Листки дерева: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Ейлер: цикл: усі степені парні; шлях: рівно 2 непарні степені
Гамільтонові цикли в K_n: (n − 1)!/2
Оновлення в алгоритмі Дейкстри: d(v) = min(d(v), d(u) + w(u, v))
Маршрути довжиною L: (Mᴸ)_ij

Метод

Випишіть степінь кожної вершини; сума степенів дорівнює подвоєній кількості ребер.
У задачах про Ейлера перевірте, що граф зв’язний, і порахуйте вершини з непарним степенем.
Для дерев використовуйте n − 1 ребро та лему про рукостискання.
Для алгоритму Дейкстри ведіть таблицю попередніх відстаней і щоразу фіксуйте незафіксовану вершину з найменшою відстанню.
Для мінімального остовного дерева відсортуйте ребра за вагою й пропускайте кожне ребро, що замикає цикл (Крускал), або нарощуйте одне дерево від початкової вершини (Прім).

Теорія чисел і арифметика за модулем

Ділення із залишком: a = q·n + r, 0 ≤ r < n
Евклід: gcd(a, b) = gcd(b, a mod b)
Найменше спільне кратне: lcm(a, b) = a·b/gcd(a, b)
Обернена: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Лінійна конгруенція: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Функція Ейлера: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Ферма: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Метод

Спершу зведіть кожне число за модулем n; залишки лежать між 0 і n − 1.
Для НСД діліть послідовно за алгоритмом Евкліда; останній ненульовий залишок і є НСД.
Для оберненого елемента виконайте розширений алгоритм і візьміть коефіцієнт при a; якщо він від’ємний, додайте n.
Розв’язуйте a·x ≡ b множенням на a⁻¹; поєднуйте дві конгруенції, записавши x = r₁ + m₁k.
Для степенів запишіть показник у двійковому вигляді й послідовно підносьте до квадрата; в RSA d = e⁻¹ mod φ(n), де φ(n) = (p − 1)(q − 1).

2Задачі для практики

1.Логіка висловлювань і доведенняСередня

У скількох із 8 рядків таблиці істинності (b ∨ c) → (b ∧ (c ∨ a)) істинне? Позначте це число N.

(b ∨ c) → (b ∧ (c ∨ a))

N =

2.Логіка висловлювань і доведенняСкладна

Яке твердження еквівалентне ¬∀x ∀y (R(x, y) → R(y, x)), якщо заперечення перенесено повністю досередини? Клікніть його.

¬∀x ∀y (R(x, y) → R(y, x))

1∃x ∃y (¬R(x, y) ∧ ¬R(y, x))
2∀x ∀y (R(x, y) ∧ ¬R(y, x))
3∃x ∃y (R(x, y) ∧ ¬R(y, x))
4∃x ∃y (R(x, y) → ¬R(y, x))

3.Множини, відношення та функціїСередня

У групі з 42 студентів 15 розмовляють французькою (F), 35 — німецькою (G), а 17 — іспанською (S). 11 розмовляють французькою й німецькою, 5 — французькою й іспанською, 12 — німецькою й іспанською, а 2 розмовляють усіма трьома. Скільки не входять до жодної з трьох множин?

|U| = 42

|(F ∪ G ∪ S)′| =

4.Множини, відношення та функціїСкладна

Функції f і g на {1, 2, 3, 4, 5} задано таблицями. Знайдіть (f ∘ g)(3).

f: 1 ↦ 4, 2 ↦ 4, 3 ↦ 2, 4 ↦ 4, 5 ↦ 4g: 1 ↦ 3, 2 ↦ 2, 3 ↦ 3, 4 ↦ 2, 5 ↦ 2

(f ∘ g)(3) =

5.Теорія графівСередня

Скільки різних гамільтонових циклів H має повний граф K₆? Цикли, що відрізняються лише початковою вершиною чи напрямком, вважаються однаковими.

K₆

H =

6.Теорія графівСкладна

Алгоритм Крускала будує мінімальне остовне дерево. Клікніть ребро, яке він додає як ребро номер 3; пропущені ребра не враховуються.

k = 3

1ребро AB
2ребро AC
3ребро BC
4ребро CE
5ребро DF
6ребро EF
7ребро GC
8ребро GD
9ребро GE

7.Теорія чисел і арифметика за модулемСередня

Знайдіть обернений до 41 за модулем 62: число x, де 0 < x < 62 і 41·x ≡ 1 (mod 62).

a = 41n = 62

41⁻¹ mod 62 =

8.Теорія чисел і арифметика за модулемСкладна

Скористайтеся повторним піднесенням до квадрата, щоб знайти 10¹⁷² mod 23.

a = 10k = 172n = 23

10¹⁷² mod 23 =

3Розчини

1.Логіка висловлювань і доведення

Відповідь: N = 5

Таблиці істинності: формула з n різними змінними має 2ⁿ рядків, по одному для кожної комбінації значень істинності (1 = істина, 0 = хибність). Працюйте зсередини назовні й дайте кожній підформулі власний стовпець. ¬a змінює значення; a ∧ b дорівнює 1 лише тоді, коли обидва дорівнюють 1; a ∨ b дорівнює 0 лише тоді, коли обидва дорівнюють 0; a → b дорівнює 0 лише тоді, коли a = 1 і b = 0; a ↔ b дорівнює 1, коли обидві частини рівні.

Таблиця істинності рядок за рядком

a = 1, b = 1, c = 1: b ∨ c = 1, c ∨ a = 1, b ∧ (c ∨ a) = 1, (b ∨ c) → (b ∧ (c ∨ a)) = 1

a = 1, b = 1, c = 0: b ∨ c = 1, c ∨ a = 1, b ∧ (c ∨ a) = 1, (b ∨ c) → (b ∧ (c ∨ a)) = 1

a = 1, b = 0, c = 1: b ∨ c = 1, c ∨ a = 1, b ∧ (c ∨ a) = 0, (b ∨ c) → (b ∧ (c ∨ a)) = 0

a = 1, b = 0, c = 0: b ∨ c = 0, c ∨ a = 1, b ∧ (c ∨ a) = 0, (b ∨ c) → (b ∧ (c ∨ a)) = 1

a = 0, b = 1, c = 1: b ∨ c = 1, c ∨ a = 1, b ∧ (c ∨ a) = 1, (b ∨ c) → (b ∧ (c ∨ a)) = 1

a = 0, b = 1, c = 0: b ∨ c = 1, c ∨ a = 0, b ∧ (c ∨ a) = 0, (b ∨ c) → (b ∧ (c ∨ a)) = 0

a = 0, b = 0, c = 1: b ∨ c = 1, c ∨ a = 1, b ∧ (c ∨ a) = 0, (b ∨ c) → (b ∧ (c ∨ a)) = 0

a = 0, b = 0, c = 0: b ∨ c = 0, c ∨ a = 0, b ∧ (c ∨ a) = 0, (b ∨ c) → (b ∧ (c ∨ a)) = 1

Порахуйте рядки зі значенням 1

(b ∨ c) → (b ∧ (c ∨ a)): 1, 1, 0, 1, 1, 0, 0, 1

N = 5

Відповідь

N = 5

2.Логіка висловлювань і доведення

Відповідь: ∃x ∃y (R(x, y) ∧ ¬R(y, x))

Квантори та міркування: ¬∀x P(x) ≡ ∃x ¬P(x) і ¬∃x P(x) ≡ ∀x ¬P(x). Переносьте заперечення досередини, міняйте кожен квантор, який воно проходить, і заперечуйте внутрішню формулу за законами логіки висловлювань, наприклад ¬(a → b) ≡ a ∧ ¬b. Міркування коректне, коли висновок дорівнює 1 у кожному рядку, де всі передумови дорівнюють 1. Один рядок з істинними передумовами та хибним висновком — це контрприклад, який показує, що міркування некоректне.

Перенесіть заперечення досередини

¬∀x ∀y (R(x, y) → R(y, x)) ≡ ∃x ∃y (R(x, y) ∧ ¬R(y, x))

Відповідь

∃x ∃y (R(x, y) ∧ ¬R(y, x))

Інші варіанти або залишають квантор без змін, або змінюють порядок кванторів, або неправильно заперечують внутрішню формулу.

3.Множини, відношення та функції

Відповідь: |(F ∪ G ∪ S)′| = 1

Множини та діаграми Вена: A ∪ B містить елементи з A або B (або з обох), A ∩ B — елементи з обох, A − B — елементи A, яких немає в B, а доповнення A′ — усе в U, чого немає в A. На діаграмі Вена кожен множинний вираз — це об’єднання областей, тож рахуйте його область за областю. Включення–виключення: |A ∪ B| = |A| + |B| − |A ∩ B| і |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Центр і пари

F ∩ G ∩ S: 2

F ∩ G лише: 11 − 2 = 9

F ∩ S лише: 5 − 2 = 3

G ∩ S лише: 12 − 2 = 10

Окремі множини

F лише: 15 − 9 − 3 − 2 = 1

G лише: 35 − 9 − 10 − 2 = 14

S лише: 17 − 3 − 10 − 2 = 2

Відповідь

|F ∪ G ∪ S| = 41

|(F ∪ G ∪ S)′| = 42 − 41 = 1

Відповідь

|(F ∪ G ∪ S)′| = 1

4.Множини, відношення та функції

Відповідь: (f ∘ g)(3) = 2

Функції та підрахунок: функція f: A → B дає кожному елементу A рівно один образ у B. f ін’єктивна (один до одного), коли різні елементи мають різні образи, сюр’єктивна (на), коли кожен елемент B є образом, і бієктивна, коли виконується і те, і те. За |A| = m і |B| = n існує nᵐ функцій, n!/(n − m)! ін’єктивних (m ≤ n), а за принципом включення–виключення Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ сюр’єктивних. |𝒫(A)| = 2ᵐ і |A × B| = m·n.

Внутрішня функція

g(3) = 3

Зовнішня функція

f(3) = 2

(f ∘ g)(3) = 2

Відповідь

(f ∘ g)(3) = 2

5.Теорія графів

Відповідь: H = 60

Ейлер, Гамільтон і дерева: зв’язний граф має ейлерів цикл (кожне ребро один раз, з поверненням до початку), коли кожна вершина має парний степінь, і ейлерів шлях, що не є циклом, коли рівно дві вершини мають непарний степінь; тоді шлях іде від однієї непарної вершини до другої. Гамільтонів цикл відвідує кожну вершину один раз; у K_n їх (n − 1)!/2. Дерево на n вершинах має n − 1 ребро, а зв’язний граф з m ребрами зберігає остовне дерево після вилучення m − n + 1 ребер.

Порахуйте

H = (6 − 1)!/2 = 120/2 = 60

Відповідь

H = 60

6.Теорія графів

Відповідь: ребро GD

Найкоротші шляхи та остовні дерева: алгоритм Дейкстри фіксує одну вершину за раунд: незафіксовану вершину з найменшою попередньою відстанню. Її відстань тоді остаточна, а кожен сусід v отримує d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Крускала будує мінімальне остовне дерево, беручи ребра від легких до важких і пропускаючи кожне ребро, що замкнуло б цикл; алгоритм Пріма нарощує одне дерево від початкової вершини, завжди додаючи найлегше ребро, що виходить з нього. Остовне дерево з n вершин має n − 1 ребро.

Алгоритм Крускала

1. CE (1)

2. GE (3)

3. GD (4)

4. BC (6)

5. EF (10)

6. AC (11)

номер ребра 3

Відповідь

ребро GD

7.Теорія чисел і арифметика за модулем

Відповідь: 41⁻¹ mod 62 = 59

Обернені елементи та конгруенції: a має обернений за модулем n саме тоді, коли gcd(a, n) = 1. Розширений алгоритм Евкліда записує 1 = s·n + t·a, і тоді a⁻¹ ≡ t (mod n). Конгруенція a·x ≡ b (mod n) з gcd(a, n) = 1 має розв’язок x ≡ a⁻¹·b. Дві конгруенції x ≡ r₁ (mod m₁) і x ≡ r₂ (mod m₂) зі взаємно простими модулями мають один розв’язок за модулем m₁·m₂ (китайська теорема про лишки). Функція Ейлера φ(n) рахує числа від 1 до n, взаємно прості з n: φ(n) = n·∏(1 − 1/p).

Розширений алгоритм Евкліда

Кожен залишок r записується як r ≡ t·41 (mod 62).

r = 62, t = 0

r = 41, q = 1, t = 1

r = 21, q = 1, t = −1

r = 20, q = 1, t = 2

r = 1, q = 20, t = −3

Обернена

1 ≡ −3·41 (mod 62)

x = 59

перевірка: 41·59 = 2419 = 39·62 + 1

Відповідь

41⁻¹ mod 62 = 59

8.Теорія чисел і арифметика за модулем

Відповідь: 10¹⁷² mod 23 = 9

Степені за модулем і RSA: обчислюйте aᵏ mod n повторним піднесенням до квадрата: запишіть k у двійковому вигляді, підносьте до квадрата, зводьте після кожного кроку й перемножте степені, біти яких дорівнюють 1. Ферма: aᵖ⁻¹ ≡ 1 (mod p) для простого p, що не ділить a, тож показник можна зводити за модулем p − 1. RSA: оберіть прості p і q, n = p·q і φ(n) = (p − 1)(q − 1); відкритий показник e взаємно простий із φ(n), а закритий показник — d = e⁻¹ mod φ(n). Шифруйте за c = mᵉ mod n, а дешифруйте за m = cᵈ mod n.

Двійковий показник

172 = 10101100₂ = 128 + 32 + 8 + 4

Повторне піднесення до квадрата

10¹ ≡ 10 (mod 23)

10² ≡ 8 (mod 23)

10⁴ ≡ 18 (mod 23)

10⁸ ≡ 2 (mod 23)

10¹⁶ ≡ 4 (mod 23)

10³² ≡ 16 (mod 23)

10⁶⁴ ≡ 3 (mod 23)

10¹²⁸ ≡ 9 (mod 23)

Перемножте потрібні степені

10¹⁷² ≡ 18·2·16·9 ≡ 9 (mod 23)

Відповідь

10¹⁷² mod 23 = 9

ExamProblems · examproblems.com/courses/discrete-mathematics