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

Аркуші з формулами, ключові кроки методів для кожної теми та 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.Логіка висловлювань і доведенняСередня

Яка формула логічно еквівалентна ¬(r → p)? Клікніть її.

¬(r → p)

1r ∧ ¬p
2¬r ∧ p
3r → ¬p
4¬r ∨ ¬p

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

Міркування з передумовами a → c; b → c і висновком a → b некоректне. Клікніть рядок таблиці істинності, що є контрприкладом.

a → cb → c∴ a → b

1a = 1, b = 1, c = 1
2a = 1, b = 1, c = 0
3a = 1, b = 0, c = 1
4a = 1, b = 0, c = 0
5a = 0, b = 1, c = 1
6a = 0, b = 1, c = 0
7a = 0, b = 0, c = 1
8a = 0, b = 0, c = 0

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

У групі з 37 студентів 19 розмовляють французькою (F), 21 — німецькою (G), а 19 — іспанською (S). 11 розмовляють французькою й німецькою, 7 — французькою й іспанською, 10 — німецькою й іспанською, а 3 розмовляють усіма трьома. Скільки входять лише до F?

|U| = 37

|F − (G ∪ S)| =

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

На X = {1, 2, …, 8} відношення x ~ y виконується, коли x ≡ y (mod 2). Скільки елементів у класі еквівалентності [8]?

X = {1, …, 8}x ~ y ⟺ 2 | (x − y)

|[8]| =

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

Чи має зв’язний граф ейлерів цикл, ейлерів шлях, що не є циклом, чи нічого з цього? Клікніть свою відповідь.

|V| = 5|E| = 6

1Ейлерів цикл
2Ейлерів шлях, не цикл
3жодна з цих

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

Скільки маршрутів довжиною 2 ведуть від A до B? Маршрут може повторювати вершини й ребра. Позначте число N.

M = матриця суміжностіL = 2

N =

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

Розв’яжіть 31x ≡ 51 (mod 79). Дайте розв’язок x, де 0 < x < 79.

31x ≡ 51 (mod 79)

x =

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

Розв’яжіть 36x ≡ 48 (mod 66). Дайте найменший додатний розв’язок x.

36x ≡ 48 (mod 66)

x =

3Розчини

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

Відповідь: r ∧ ¬p

Логічна еквівалентність: дві формули еквівалентні (≡), коли мають однакове значення в кожному рядку таблиці істинності. Тавтологія дорівнює 1 у кожному рядку, суперечність — 0 у кожному рядку, а випадкова формула — ні те, ні інше. Корисні закони: закони де Моргана, ¬(a ∧ b) ≡ ¬a ∨ ¬b і ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (контрапозиція); ¬(a → b) ≡ a ∧ ¬b; а також закони дистрибутивності, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Закон

¬(a → b) ≡ ¬(¬a ∨ b) ≡ a ∧ ¬b: єдиний рядок, у якому імплікація хибна.

¬(r → p) ≡ r ∧ ¬p

Перевірте за таблицею істинності

p = 1, r = 1: 0 | 0 0 0 0

p = 1, r = 0: 0 | 0 1 1 1

p = 0, r = 1: 1 | 1 0 1 1

p = 0, r = 0: 0 | 0 0 1 1

Відповідь

r ∧ ¬p

Стовпці після риски — це варіанти в показаному порядку.

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

Відповідь: a = 1, b = 0, c = 1

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

Передумови та висновок рядок за рядком

a = 1, b = 1, c = 1: 1 1 | 1

a = 1, b = 1, c = 0: 0 0 | 1

a = 1, b = 0, c = 1: 1 1 | 0

a = 1, b = 0, c = 0: 0 1 | 0

a = 0, b = 1, c = 1: 1 1 | 1

a = 0, b = 1, c = 0: 1 0 | 1

a = 0, b = 0, c = 1: 1 1 | 1

a = 0, b = 0, c = 0: 1 1 | 1

Контрприклад

a = 1, b = 0, c = 1

Відповідь

a = 1, b = 0, c = 1

Міркування такої форми схоже на коректне правило, але одного рядка досить, щоб показати, що це не так.

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

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

Множини та діаграми Вена: 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: 3

F ∩ G лише: 11 − 3 = 8

F ∩ S лише: 7 − 3 = 4

G ∩ S лише: 10 − 3 = 7

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

F лише: 19 − 8 − 4 − 3 = 4

G лише: 21 − 8 − 7 − 3 = 3

S лише: 19 − 4 − 7 − 3 = 5

Відповідь

|F − (G ∪ S)| = 4

Відповідь

|F − (G ∪ S)| = 4

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

Відповідь: |[8]| = 4

Відношення: відношення R на множині X — це множина впорядкованих пар (x, y). R рефлексивне, коли (x, x) ∈ R для кожного x з X; симетричне, коли (x, y) ∈ R завжди супроводжується (y, x) ∈ R; антисиметричне, коли (x, y) і (y, x) одночасно належать R лише якщо x = y; і транзитивне, коли (x, y) та (y, z) в R тягнуть за собою (x, z) ∈ R. Відношення еквівалентності рефлексивне, симетричне й транзитивне та розбиває X на неперетинні класи.

Клас

[8] = {2, 4, 6, 8}

|[8]| = 4

Відповідь

|[8]| = 4

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

Відповідь: Ейлерів цикл

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

Степені

deg(A) = 2, deg(B) = 4, deg(C) = 2, deg(D) = 2, deg(E) = 2

Непарні вершини

Ейлерів цикл

Відповідь

Ейлерів цикл

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

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

Степені: степінь вершини — це кількість ребер, що в ній сходяться. Кожне ребро має два кінці, тож степені в сумі дають подвоєну кількість ребер: Σ deg(v) = 2|E| (лема про рукостискання). Тому кількість вершин з непарним степенем парна. K_n має n(n − 1)/2 ребер, k-регулярний граф на n вершинах має nk/2, а дерево на n вершинах має n − 1 ребро.

Матриця суміжності

A: 0 0 1 0 0 0

B: 0 0 1 1 1 0

C: 1 1 0 0 1 0

D: 0 1 0 0 1 1

E: 0 1 1 1 0 0

F: 0 0 0 1 0 0

Спільні сусіди

(M²)_AB = 0·0 + 0·0 + 1·1 + 0·1 + 0·1 + 0·0 = 1

Відповідь

N = 1

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

Відповідь: x = 73

Обернені елементи та конгруенції: 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).

Обернений до 31

r = 79, t = 0

r = 31, q = 2, t = 1

r = 17, q = 1, t = −2

r = 14, q = 1, t = 3

r = 3, q = 4, t = −5

r = 2, q = 1, t = 23

r = 1, q = 2, t = −28

31⁻¹ ≡ 51 (mod 79)

Розв’яжіть

x ≡ 51·51 = 2601 ≡ 73 (mod 79)

перевірка: 31·73 = 2263 ≡ 51 (mod 79)

Відповідь

x = 73

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

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

Поділіть на НСД

gcd(36, 66) = 6

6x ≡ 8 (mod 11)

Розв’яжіть скорочену конгруенцію

6⁻¹ ≡ 2 (mod 11) → x ≡ 5 (mod 11)

Розв’язки за модулем 66

x ∈ {5, 16, 27, 38, 49, 60}

x = 5

Відповідь

x = 5

ExamProblems · examproblems.com/courses/discrete-mathematics