Множества и отношения — формальный слой
Прикладные примеры множеств, отношений и матриц — в дискретной математике. Здесь — формальные определения из курса теории множеств: зачем нужны индукция, мощность и порядки при доказательстве корректности программ и схем данных.
Функции и биекции
Функция f : A → B каждому a ∈ A ставит в соответствие единственный f(a) ∈ B.
| Свойство | Смысл | В IT |
|---|---|---|
| Инъекция | разные аргументы → разные значения | ключ без коллизий |
| Сюръекция | каждый элемент B достижим | покрытие кодов ошибок |
| Биекция | инъекция + сюръекция | взаимно однозначное кодирование, изоморфизм структур |
Если между конечными множествами A и B есть биекция, то |A| = |B|. Сравнение мощностей бесконечных множеств (счётные и несчётные) объясняет, почему "перечислить все вещественные числа списком" принципиально отличается от перечисления целых.
Математическая индукция
Чтобы доказать свойство P(n) для всех n ∈ ℕ:
- База:
P(0)(илиP(k)с некоторогоk). - Шаг: для любого
nизP(n)следуетP(n+1).
Тогда P(n) верно для всех n ≥ начального значения. Полная индукция: доказывают P(n) из того, что P(m) верно для всех m < n — удобно для разборов по структуре дерева или рекурсивных типов.
// Инвариант цикла — частый вид индукции на практике
// После k итераций: сумма[0..k-1] = acc
база: k = 0, acc = 0 — верно
шаг: если после k верно, то после k+1 acc увеличивается на a[k] — верно
Тот же шаблон лежит в доказательстве корректности for и в анализе рекурсии (высота стека ≤ глубина вызовов).
Мощность конечных и перечислимых множеств
|A| = n для конечного A. Булеан P(A) всех подмножеств имеет мощность 2^n — источник экспоненциального перебора конфигураций в тестах и feature flags.
Для бесконечных множеств сравнивают существование биекции на ℕ (счётность). Множество строк над конечным алфавитом (при фиксированной длине или с ограничением) часто конечно или счётно; множество всех подпрограмм на языке Тьюринг-полном — несчётно — см. границы вычислений.
Порядки и изоморфизм
Частичный порядок (A, ⩽) рефлексивен, антисимметричен, транзитивен. Линейный порядок — любые два элемента сравнимы.
Любой конечный частичный порядок изоморфен семейству подмножеств A, упорядоченному по включению ⊆. В коде тот же смысл у иерархии пакетов Java, вложенных каталогов и решёток прав доступа.
Диаграмма Хассе — схема частичного порядка без лишних рёбер: рисуют только непосредственное предшествование (если a < b и нет «промежуточного» c между ними). Удобна для иерархий зависимостей и пакетов.
| Понятие | Смысл | Пример |
|---|---|---|
| Цепь | любые два элемента сравнимы | линейная цепочка версий v1 < v2 < … < vk |
| Антицепь | никакие два различных элемента не сравнимы | параллельные ветки без общего предка в DAG |
Теорема Дилуорса: в конечном частичном порядке минимальное число цепей, на которые можно разбить все элементы, равно максимальной мощности антицепи. В IT это мотивирует «сколько параллельных потоков работы нужно», если задачи попарно несравнимы (нельзя упорядочить одну раньше другой).
Топологическая сортировка DAG (ориентированный ациклический граф порядка) — линейное расширение частичного порядка; без циклов в графе зависимостей задач.
Матрицы отношений
На конечном A = {a₁,…,aₙ} отношение R ⊆ A² задаётся матрицей (rᵢⱼ) из 0 и 1. Композиция отношений связана с умножением матриц (с учётом булевого ∨ вместо +). Для эквивалентности матрицу приводят к блочно-диагональному виду — см. Дискретная математика.
Композиция, обратное отношение, замыкания
Композиция R ∘ S: пара (a,c) входит в R ∘ S, если существует b с (a,b) ∈ R и (b,c) ∈ S. На матрицах: (R ∘ S)ᵢⱼ = ∨ₖ (rᵢₖ ∧ sₖⱼ). В SQL похожий смысл у цепочки join’ов; в графе — путь длины 2 через промежуточную вершину.
Обратное отношение R⁻¹ = {(b,a) | (a,b) ∈ R} — все стрелки разворачиваются. Пример: «является родителем» ↔ «является ребёнком».
Замыкание отношения R относительно свойства — наименьшее надмножество R, в котором свойство уже выполняется:
| Замыкание | Добавляем к R | Зачем |
|---|---|---|
| Рефлексивное | все пары (a,a) | «каждый связан с собой» |
| Симметричное | все (b,a) для (a,b) ∈ R | неориентированный вид |
| Транзитивное | (a,c), если есть цепочка a → … → c | «предок предка — предок» |
Транзитивное замыкание R* — все пары, связанные путём любой длины (включая нулевую длину для рефлексивного варианта). В орграфе это матрица достижимости; алгоритм Уоршелла — см. Графы — углубление.
Дальше: реляционная алгебра и таблицы → дискретная математика (прикладная) → графы — углубление → рекуррентные соотношения.