Дискретная математика: тренировочные задачи и экзаменационные вопросы

Математика информатики и любого доказательства: логика высказываний и кванторы, множества, отношения и функции, графы с кратчайшими путями и остовными деревьями, а также теория чисел вплоть до 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. Без карты.