Дискретна математика: тренувальні задачі й екзаменаційні питання

Математика інформатики й кожного доведення: логіка висловлювань і квантори, множини, відношення та функції, графи з найкоротшими шляхами й остовними деревами, а також теорія чисел аж до RSA. В екзаменаційних завданнях потрібні точні відповіді, тож акуратна таблиця чи діаграма важливіша за калькулятор.

Тренуйте цей курс безкоштовноТренувати цей курсСкласти пробний іспитБезкоштовних задач щодня: 5. Без картки.

Шпаргалка-підсумок (PDF)Аркуші з формулами, кроки методів і задачі для практики з повними розв’язками, готові до друку.

Теми цього курсу

  1. Логіка висловлювань і доведеннятаблиці істинності · еквівалентності та методи доведення · квантори та міркуваннярозрахунки
  2. Множини, відношення та функціїдіаграми Вена та підмножини · включення–виключення та відношення · функції та підрахунокрозрахунки
  3. Теорія графівстепені та ребра · ейлерові шляхи та дерева · найкоротші шляхи та остовні дереварозрахунки
  4. Теорія чисел і арифметика за модулемНСД і залишки · обернені елементи та конгруенції · степені за модулем і RSAрозрахунки

Поради до іспиту: Дискретна математика

  • Випишіть таблицю істинності або діаграму Вена: більшість помилок виникає через пропущений рядок чи область.
  • Щоб спростувати твердження, достатньо одного контрприкладу; щоб довести — перевірте всі випадки або наведіть загальне міркування.
  • В арифметиці за модулем зводьте за модулем після кожного кроку й тримайте залишки між 0 і n − 1.

Розв’язані приклади

Логіка висловлювань і доведенняЛегка
pq¬(p ∨ q) → q11100100

Рівно один рядок таблиці істинності робить ¬(p ∨ q) → q хибним. Клікніть цей рядок.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
Показати підказки
  1. a → b дорівнює 0 лише тоді, коли a = 1 і b = 0. ¬a змінює значення на протилежне. a ∨ b дорівнює 0 лише тоді, коли обидва дорівнюють 0.
  2. Спершу визначте головний зв’язник: якими мають бути його дві частини, щоб уся формула була 0?
  3. Дайте кожній частині власний стовпець: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Показати відповідь і пояснення

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

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

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

Рядок

p = 0, q = 0 → ¬(p ∨ q) → q = 0

Відповідь

p = 0, q = 0
Множини, відношення та функціїСередня
UMPC

З 53 студентів першого курсу 35 склали математику (M), 28 склали фізику (P) і 29 склали хімію (C). 20 склали M і P, 18 склали M і C, 10 склали P і C, а 6 склали всі три. Скільки не входять до жодної з трьох множин?

|U| = 53

Знайти: |(M ∪ P ∪ C)′|

Показати підказки
  1. Заповнюйте діаграму Вена від центру назовні: спочатку всі три, потім пари, потім окремі множини.
  2. Лише M і P (не C): 20 − 6 = 14. Лише M: 35 − 14 − 12 − 6 = 3.
  3. Принаймні одна множина: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.
Показати відповідь і покроковий розв’язок

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

Центр і пари

M ∩ P ∩ C: 6
M ∩ P лише: 20 − 6 = 14
M ∩ C лише: 18 − 6 = 12
P ∩ C лише: 10 − 6 = 4

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

M лише: 35 − 14 − 12 − 6 = 3
P лише: 28 − 14 − 4 − 6 = 4
C лише: 29 − 12 − 4 − 6 = 7

Відповідь

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

Відповідь

|(M ∪ P ∪ C)′| = 3

Як проходить тренування

  • «Тренувати цей курс» змішує задачі з усіх його тем, як на справжньому іспиті.
  • Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь.
  • Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.
  • Пробні іспити обмежені в часі й не мають підказок, а наприкінці ви отримуєте результат і повний розбір.

Пов’язані курси

Основи інформатикиАлгоритми та структури данихМатематичний аналіз 1Основи статистикиВища математикаСтатистика 2: Статистичне висновуванняДиференціальні рівнянняІнженерна математика 2
Тренуйте цей курс безкоштовноТренувати цей курсСкласти пробний іспитБезкоштовних задач щодня: 5. Без картки.