Дискретная математика: множества, отношения, комбинаторика
Операции над множествами и диаграммы Эйлера-Венна, свойства отношений, отношение эквивалентности и порядка, формулы комбинаторики, принцип включений и исключений.
Дискретная математика — база для теории алгоритмов, баз данных и криптографии. Курсовые здесь обычно строятся на трёх темах: множества, отношения и подсчёт числа вариантов.
Операции над множествами
| Операция | Обозначение | Смысл |
|---|---|---|
| Объединение | A ∪ B | Элементы хотя бы одного множества |
| Пересечение | A ∩ B | Элементы обоих множеств |
| Разность | A \ B | Из A, но не из B |
| Симметрическая разность | A △ B | Ровно в одном из двух |
| Дополнение | Ā | Всё, что не входит в A |
| Декартово произведение | A × B | Все упорядоченные пары (a, b) |
Основные тождества:
Коммутативность: A ∪ B = B ∪ A
Ассоциативность: (A ∪ B) ∪ C = A ∪ (B ∪ C)
Дистрибутивность: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Законы де Моргана:
(A ∪ B)‾ = Ā ∩ B̄
(A ∩ B)‾ = Ā ∪ B̄
Мощность булеана (множества всех подмножеств): |P(A)| = 2^|A|
Принцип включений и исключений
|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C|
− |A∩B| − |A∩C| − |B∩C|
+ |A∩B∩C|
Пример: из 100 студентов 60 знают Python, 45 — C++, 25 — оба языка.
Хотя бы один язык знают: 60 + 45 − 25 = 80.
Ни одного: 100 − 80 = 20.
Отношения и их свойства
| Свойство | Условие | Пример |
|---|---|---|
| Рефлексивность | ∀a: (a, a) ∈ R | Равенство, «не больше» |
| Антирефлексивность | ∀a: (a, a) ∉ R | «Строго больше» |
| Симметричность | (a,b) ∈ R → (b,a) ∈ R | «Быть родственником» |
| Антисимметричность | (a,b) и (b,a) ∈ R → a = b | «Не больше» |
| Транзитивность | (a,b) и (b,c) ∈ R → (a,c) ∈ R | «Больше», «делится на» |
- Отношение эквивалентности: рефлексивно, симметрично, транзитивно. Разбивает множество на непересекающиеся классы — например, сравнение по остатку от деления.
- Отношение частичного порядка: рефлексивно, антисимметрично, транзитивно. Пример — включение множеств или отношение делимости.
- Отношение линейного порядка: частичный порядок, в котором любые два элемента сравнимы.
- Функция — частный случай отношения, где каждому элементу области определения соответствует ровно один образ.
Комбинаторика
Перестановки n элементов: Pₙ = n!
Размещения (порядок важен): A(n,k) = n! / (n−k)!
Сочетания (порядок не важен): C(n,k) = n! / (k!·(n−k)!)
С повторениями:
размещения: nᵏ
сочетания: C(n+k−1, k)
перестановки с повторами: n! / (n₁!·n₂!·…·nₖ!)
| Задача | Формула | Ответ |
|---|---|---|
| Сколько трёхзначных PIN из 10 цифр | 10³ | 1000 |
| Сколько способов выбрать 3 из 10 книг | C(10,3) | 120 |
| Сколько способов расставить 3 из 10 книг по порядку | A(10,3) | 720 |
| Сколькими способами рассадить 5 человек | 5! | 120 |
| Число «слов» из букв слова МАТЕМАТИКА | 10!/(3!·2!·2!) | 151 200 |
Свойства сочетаний: C(n,k) = C(n, n−k) C(n,k) = C(n−1,k−1) + C(n−1,k) — правило треугольника Паскаля Σ C(n,k) при k от 0 до n = 2ⁿ — общее число подмножеств Бином Ньютона: (a + b)ⁿ = Σ C(n,k)·a^(n−k)·b^k
Элементы теории графов
Сумма степеней вершин = 2·(число рёбер) Число рёбер полного графа Kₙ = n(n−1)/2 Дерево с n вершинами имеет ровно n−1 ребро Формула Эйлера для планарного графа: В − Р + Г = 2
- Эйлеров цикл (обход всех рёбер) существует, если все вершины имеют чётную степень.
- Эйлеров путь существует при ровно двух вершинах нечётной степени — задача о кёнигсбергских мостах.
- Гамильтонов цикл проходит через все вершины по одному разу; задача о его существовании NP-полна.
- Двудольный граф не содержит циклов нечётной длины — критерий для проверки.
Логика высказываний
| Связка | Обозначение | Ложна только когда |
|---|---|---|
| Конъюнкция | A ∧ B | Хотя бы одно ложно |
| Дизъюнкция | A ∨ B | Оба ложны |
| Импликация | A → B | A истинно, B ложно |
| Эквивалентность | A ↔ B | Значения различны |
| Исключающее ИЛИ | A ⊕ B | Значения совпадают |
Импликация — источник постоянной путаницы: из ложной посылки следует что угодно, поэтому A → B истинна, когда A ложно. Полезное тождество для преобразований: A → B равносильно Ā ∨ B.
Частые вопросы
Чем размещения отличаются от сочетаний?
В размещениях учитывается порядок элементов, в сочетаниях — нет. Поэтому A(n,k) всегда в k! раз больше C(n,k).
Почему 0! = 1?
Это соглашение, которое делает формулы согласованными: C(n,n) = n!/(n!·0!) должно равняться единице. Содержательно: существует ровно один способ ничего не выбрать.
Как отношение эквивалентности связано с классами?
Оно разбивает множество на непересекающиеся классы, объединение которых даёт всё множество. Такое разбиение называется фактор-множеством и лежит в основе модульной арифметики.