Дискретная математика

Фундамент для алгоритмов и теоретической информатики: логика, предикаты, отношения, комбинаторика, графы, булевы функции и рекуррентные соотношения.

Фокус: Структуры + доказательства
Ключевой навык: Формализовать и доказывать
Контроль: Задачи + теория

1. Логика высказываний

1.1. Базовые связки

Связка	Запись	Истинна когда
Отрицание	`¬A`	A ложно
Конъюнкция	`A∧B`	A и B истинны
Дизъюнкция	`A∨B`	хотя бы одно истинно
Импликация	`A→B`	ложна только при A=1, B=0
Эквиваленция	`A↔B`	A и B равны

1.2. Ключевые эквивалентности

A→B ≡ ¬A∨B.
¬(A∧B) ≡ ¬A∨¬B и ¬(A∨B) ≡ ¬A∧¬B.
A∧(A∨B) ≡ A, A∨(A∧B) ≡ A (поглощение).
¬¬A ≡ A.

Для упрощения формул полезно сначала избавиться от импликаций, затем применить законы де Моргана и дистрибутивность.

1.3. Нормальные формы

ДНФ: дизъюнкция конъюнкций литералов.
КНФ: конъюнкция дизъюнкций литералов.
СДНФ/СКНФ строятся по таблице истинности.

2. Логика предикатов и методы доказательства

2.1. Кванторы

∀x P(x) — для всех x верно P.
∃x P(x) — существует x, для которого верно P.

Отрицание кванторов: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x).

2.2. Методы доказательств

Прямое доказательство: из посылок вывести утверждение.
Контрапозиция: доказать ¬B→¬A вместо A→B.
От противного: допустить отрицание и получить противоречие.
Математическая индукция.

Принцип индукции: если верна база P(1) и из P(k) следует P(k+1), то P(n) верно для всех натуральных n.

Частая ошибка в индукции: в шаге перехода использовать то, что еще не доказано для k+1 (скрытый круг).

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

3.1. Операции над множествами

A∪B, A∩B, A\B, дополнение.
Декартово произведение A×B.
Мощность |A| и равномощность.

3.2. Отношения

Бинарное отношение R ⊆ A×A может иметь свойства:

рефлексивность,
симметричность,
антисимметричность,
транзитивность.

Тип отношения	Свойства	Результат
Эквивалентность	рефлексивно + симметрично + транзитивно	Разбиение на классы
Частичный порядок	рефлексивно + антисимметрично + транзитивно	Структура порядка

3.3. Функции

Инъекция: разные аргументы → разные значения.
Сюръекция: каждый элемент образа покрыт.
Биекция: инъекция + сюръекция.

4. Комбинаторика

4.1. Принципы счета

Правило суммы (альтернатива): m+n.
Правило произведения (последовательность): m·n.

4.2. Базовые формулы

Объект	Без повторений	С повторениями
Перестановки	`n!`	`n!/(n1!…nk!)`
Размещения из n по k	`A(n,k)=n!/(n-k)!`	`n^k`
Сочетания из n по k	`C(n,k)=n!/(k!(n-k)!)`	`C(n+k-1,k)`

4.3. Бином Ньютона

(a+b)^n = Σ C(n,k) a^(n-k)b^k.

4.4. Включения-исключения и принцип Дирихле

|A∪B|=|A|+|B|-|A∩B|, для многих множеств формула расширяется чередованием знаков.
Принцип Дирихле: если n+1 объектов положить в n ящиков, в одном ящике будет минимум 2 объекта.

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

5.1. Базовые определения

Граф G=(V,E): V — вершины, E — ребра.

Степень вершины deg(v).
Путь, цикл, связность, компоненты связности.
Дерево: связный граф без циклов.

Факт: в дереве из n вершин ровно n-1 ребро.

5.2. Эйлеровы и гамильтоновы конструкции

Эйлеров цикл в связном графе существует, если все степени четны.
Эйлеров путь — когда ровно 0 или 2 вершины нечетной степени.
Гамильтоновость — отдельная задача, общего простого критерия нет.

5.3. Алгоритмы обхода

BFS — поиск в ширину, кратчайшие пути в невзвешенном графе.
DFS — поиск в глубину, компоненты, циклы, топологические идеи.

6. Булевы функции

6.1. Представления

Таблица истинности.
СДНФ и СКНФ.
Полином Жегалкина (над полем GF(2)).

6.2. Минимизация

Алгебраические преобразования.
Карты Карно (обычно для 2-4 переменных).
Метод Квайна-МакКласки (более системный).

Для контрольных задач чаще всего хватает карт Карно и аккуратной группировки степеней двойки.

7. Рекуррентные соотношения

7.1. Линейные рекуррентности

Пример: a_n = c1 a_{n-1} + c2 a_{n-2}. Решается через характеристическое уравнение.

7.2. Типовая схема решения

Записать характеристический многочлен.
Найти корни и построить общее решение.
Подставить начальные условия, найти константы.

Для простого корня r вклад в решение: C r^n. Для кратного корня порядка m: (C0 + C1 n + ... + C_{m-1} n^{m-1}) r^n.

8. Практика и экзаменационный минимум

8.1. Минимальный набор умений

Строить таблицы истинности и выводить СДНФ/СКНФ.
Работать с кванторами и корректно отрицать формулы.
Решать задачи на включения-исключения и Дирихле.
Решать базовые задачи на графы и обходы.
Минимизировать булевы функции.

8.2. Задачи для отработки

Упростить 15 логических формул разными методами.
Составить СДНФ/СКНФ для 10 булевых функций.
Решить 20 комбинаторных задач смешанных типов.
Решить 10 задач на графы (связность, эйлеровы пути, деревья).
Решить 8 задач на рекуррентности с начальными условиями.

Минимум к экзамену

Основные логические эквивалентности и законы де Моргана.
Индукция, принцип Дирихле, формулы комбинаторики.
Критерии эйлеровых путей, свойства дерева.
СДНФ/СКНФ и базовая минимизация булевых функций.