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

СУПЕР-ШПАРГАЛКА ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

(Для студентов МИФИ, МФТИ, МГУ на основе учебников С.В. Яблонского, Г.П. Гаврилова, В.Б. Алексеева, Н.П. Нефедова, О. Оре)

Краткий справочник символов и обозначений

1. МАТЕМАТИЧЕСКАЯ ЛОГИКА

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

Определения

1. Высказывание: Повествовательное предложение, которое либо истинно (1), либо ложно (0). Закон исключённого третьего.
2. Элементарное высказывание: Пропозициональная переменная $x$, $y$, $z$, $\dots$ — не разложимое на более простые.
3. Формула (пропозициональная форма): Строится индуктивно:
   • 0 и 1 — формулы;
   • Пропозициональная переменная — формула;
   • Если $A$ и $B$ — формулы, то $\neg A$, $A \land B$, $A \lor B$, $A \to B$, $A \leftrightarrow B$, $A \oplus B$ — формулы.
4. Интерпретация: Приписывание каждой переменной истинностного значения.
5. Тавтология (тождественно-истинная формула): Принимает значение 1 при всех интерпретациях. Обозначение: $\models A$.
6. Противоречие (тождественно-ложная формула): Всегда 0.
7. Выполнимая формула: Принимает значение 1 хотя бы при одной интерпретации.
8. Логическое следование: $A \models B$, если $A \to B$ — тавтология.

Таблицы истинности логических связок

Примечание: $\to$ — «материальная импликация». $x \to y$ ложно только при $x=1$, $y=0$. «Из лжи следует что угодно».

Приоритет логических связок (по убыванию)

$\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$, $\oplus$.

Основные законы логики высказываний (тождественно-истинные формулы)

1.2. Логика предикатов

Определения

1. Предикат: Предложение с переменными $P(x_1, \dots, x_n)$, которое становится высказыванием при подстановке конкретных значений. Пример: $P(x)$ = «$x > 0$», $x \in \mathbb{N}$.
2. Область определения предиката: Множество $M$, из которого берутся значения переменных.
3. Квантор всеобщности: $\forall x\, P(x)$ истинно $\Leftrightarrow$ $P(x)$ истинно для всех $x \in M$.
4. Квантор существования: $\exists x\, P(x)$ истинно $\Leftrightarrow$ $P(x)$ истинно хотя бы для одного $x \in M$.
5. Свободные и связанные переменные: Переменная, на которую «навешен» квантор — связана; иначе — свободна.
6. Формула логики предикатов: Строится из атомарных формул (предикатов), связок и кванторов.
7. Общезначимость: Формула истинна в любой интерпретации (на любой области $M$).
8. Выполнимость: Существует интерпретация, в которой формула истинна.

Логические эквивалентности с кванторами

$$ \begin{aligned} &\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x) \\ &\neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x) \\ &\forall x\, (P(x) \land Q(x)) \equiv (\forall x\, P(x)) \land (\forall x\, Q(x)) \\ &\exists x\, (P(x) \lor Q(x)) \equiv (\exists x\, P(x)) \lor (\exists x\, Q(x)) \\ &\forall x\, P(x) \lor \forall x\, Q(x) \models \forall x\, (P(x) \lor Q(x)) \quad \text{(обратное неверно)} \\ &\exists x\, (P(x) \land Q(x)) \models \exists x\, P(x) \land \exists x\, Q(x) \quad \text{(обратное неверно)} \end{aligned} $$

Выражение кванторов друг через друга

$$ \forall x\, P(x) \equiv \neg \exists x\, \neg P(x); \qquad \exists x\, P(x) \equiv \neg \forall x\, \neg P(x). $$

Типовые задачи и алгоритмы решения

► Задача 1. Доказательство равносильности формул. Методы:

1. Таблица истинности — универсальный метод, работает для любого числа переменных (практично до 4-5 переменных).
2. Равносильные преобразования — использование основных законов (де Моргана, дистрибутивность, поглощение).
3. Метод от противного — предположить, что формулы не равносильны, найти контрпример.

Пример: Доказать $x \to y \equiv \neg x \lor y$. Таблица истинности: обе формулы дают $(1,1,0,1)$ — равносильны.

► Задача 2. Перевод с естественного языка на язык логики предикатов. Алгоритм:

1. Выделить предметную область $M$.
2. Определить предикаты для свойств и отношений.
3. Расставить кванторы: «все» $\to \forall$, «существует» $\to \exists$, «существует единственный» $\to \exists!$.
4. Критично: порядок кванторов! $\forall x \exists y$ и $\exists y \forall x$ — разные утверждения.

Пример: «Каждый студент сдал какой-то экзамен»: $\forall x (S(x) \to \exists y (E(y) \land P(x,y)))$. «Есть экзамен, который сдали все студенты»: $\exists y (E(y) \land \forall x (S(x) \to P(x,y)))$.

► Задача 3. Отрицание высказываний с кванторами. Алгоритм: «Проносим» отрицание внутрь:

1. $\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)$
2. $\neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x)$
3. $\neg(P \land Q) \equiv \neg P \lor \neg Q$, $\neg(P \lor Q) \equiv \neg P \land \neg Q$

Пример: Отрицание «Все студенты знают хотя бы один язык программирования»: $\neg\forall s \exists l\, \text{Knows}(s,l) \equiv \exists s \forall l\, \neg\text{Knows}(s,l)$ — «Существует студент, не знающий ни одного языка».

Типовые ошибки

⚠ Ошибка 1. Импликация $A \to B$ истинна при ложном $A$. «Из лжи следует что угодно» (ex falso quodlibet). Студенты ожидают, что $0 \to 0$ должно быть ложно, но по таблице: $0 \to 0 = 1$. Пример: «Если $2\times2=5$, то я — Папа Римский» — формально истинное высказывание!

⚠ Ошибка 2. Путаница между $\to$ (импликация) и $\models$ (логическое следование). $A \to B$ — формула языка логики. $A \models B$ — метаутверждение: «$B$ истинно во всех моделях, где истинно $A$». $A \models B$ $\Leftrightarrow$ $(A \to B)$ — тавтология.

⚠ Ошибка 3. Порядок кванторов. $\forall x \exists y\, P(x,y)$ и $\exists y \forall x\, P(x,y)$ — разные утверждения! Первое: для каждого $x$ свой $y$. Второе: ОДИН $y$ для всех $x$. Пример: $\forall \text{человек } \exists \text{мать}$ — верно. $\exists \text{мать } \forall \text{человек}$ — неверно.

⚠ Ошибка 4. Неправильное отрицание импликации. $\neg(A \to B) \equiv A \land \neg B$, а не $A \to \neg B$. Импликация ложна ТОЛЬКО когда посылка истинна, а заключение ложно.

⚠ Ошибка 5. Контрапозиция vs обращение. $A \to B \equiv \neg B \to \neg A$ (контрапозиция, верно). Но $A \to B \not\equiv B \to A$ (обращение, неверно). Пример: «Если идёт дождь, то земля мокрая» $\not\equiv$ «Если земля мокрая, то идёт дождь».

Мнемонические правила

☞ Импликация как обещание: «Обещал — сделал» (1). «Обещал — не сделал» (0). «Не обещал — сделал» (1, приятный сюрприз). «Не обещал — не сделал» (1).

☞ Де Морган: «Отрицание меняет $\land$ на $\lor$ и наоборот». $\overline{AB} = \overline{A} \lor \overline{B}$ — «крыша ломается, знак переворачивается».

☞ Кванторы: $\forall$ — перевёрнутая A («All»). $\exists$ — перевёрнутая E («Exists»). При отрицании: $\neg\forall = \exists\neg$, $\neg\exists = \forall\neg$.

2.1. Множества и операции (углублённый раздел)

Базовые определения (аксиомы ZFC, операции) — см. шпаргалку по матанализу (analysis3.md). Здесь — расширенный раздел для дискретной математики.

Дополнительные операции и понятия

Свойства мощности

1. Теорема Кантора: $|\mathcal{P}(A)| > |A|$. Нет наибольшего кардинала.
2. Теорема Кантора–Бернштейна: Если $|A| \le |B|$ и $|B| \le |A|$, то $|A| = |B|$.
3. Счётность: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ счётны; $\mathbb{R}$, $\mathbb{C}$, $\mathcal{P}(\mathbb{N})$ несчётны.

2.2. Бинарные отношения

Определения

1. Бинарное отношение на $A$: Подмножество $R \subseteq A \times A$. Пишут $a R b$ вместо $(a, b) \in R$.
2. Свойства отношений:

3. Типы отношений:

Отношение эквивалентности и разбиения

Теорема: Отношение эквивалентности на $A$ задаёт разбиение $A$ на классы эквивалентности $[a] = \{b \in A \mid a R b\}$.

Фактор-множество: $A/R = \{[a] \mid a \in A\}$ — множество всех классов эквивалентности.

Замыкания отношений

Типовые задачи

► Задача 1. Доказательство свойств отношения. Алгоритм: По очереди проверяем рефлексивность, симметричность, транзитивность.

• Рефлексивность: $\forall a: (a,a) \in R$ — все ли пары $(a,a)$ есть?
• Симметричность: если $(a,b) \in R$, то $(b,a) \in R$? Проверить все пары.
• Транзитивность: если $(a,b) \in R$ и $(b,c) \in R$, то $(a,c) \in R$? Самая трудоёмкая проверка.

Контрпример для транзитивности: Достаточно найти ОДНУ тройку $a,b,c$ такую, что $(a,b)$ и $(b,c)$ есть, а $(a,c)$ — нет.

► Задача 2. Классы эквивалентности. Алгоритм:

1. Убедиться, что отношение — эквивалентность.
2. Взять произвольный элемент $a$, найти все $b: a R b$ — это класс $[a]$.
3. Взять элемент не из найденных классов, повторить.

Пример: Отношение «сравнимости по модулю 3» на $\mathbb{Z}$. Классы: $[0] = \{..., -6, -3, 0, 3, 6, ...\}$, $[1]$, $[2]$. Всего 3 класса = $\mathbb{Z}_3$.

Типовые ошибки

⚠ Ошибка 1. Симметричность + транзитивность $\not\Rightarrow$ рефлексивность. Контрпример: отношение «быть братом» на множестве людей. Симметрично, транзитивно (среди братьев), но не рефлексивно (человек не брат самому себе).

⚠ Ошибка 2. Антисимметричность $\neq$ отсутствие симметричности. $a R b \land b R a \Rightarrow a = b$ — это не значит, что $a R b \Rightarrow \neg(b R a)$. В частичном порядке ($\le$) может быть $a \le b$ и $b \le a$ одновременно — только если $a=b$.

⚠ Ошибка 3. Транзитивное замыкание — все пути произвольной длины. $R^+ = \bigcup_{n \ge 1} R^n$, а не только $R^2$. Для проверки принадлежности $(a,b)$ к $R^+$ нужно найти цепочку $(a, c_1), (c_1, c_2), \dots, (c_k, b) \in R$ произвольной длины.

⚠ Ошибка 4. Путаница между типами отображений. Инъекция = «разные прообразы $\to$ разные образы». Сюръекция = «каждый элемент $B$ имеет прообраз». Биекция = и то, и другое. $f: \mathbb{R} \to \mathbb{R}$, $f(x)=x^2$ — не инъекция ($f(-2)=f(2)=4$) и не сюръекция (нет прообраза для $-1$).

2.3. Функции и отображения

Определения

1. Функция $f: A \to B$: Отношение $f \subseteq A \times B$, где $\forall a \in A\ \exists! b \in B: (a, b) \in f$.
2. Инъекция: $a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$. Разные прообразы $\to$ разные образы.
3. Сюръекция: $\forall b \in B\ \exists a \in A: f(a) = b$. Образ совпадает с $B$.
4. Биекция: Инъекция + сюръекция. Взаимно-однозначное соответствие.
5. Обратная функция $f^{-1}$: Существует $\Leftrightarrow$ $f$ — биекция.
6. Композиция: $(g \circ f)(x) = g(f(x))$. $g \circ f$ определена $\Leftrightarrow$ $\operatorname{Im} f \subseteq \operatorname{Dom} g$.
7. Характеристическая функция множества $A \subseteq U$: $\chi_A(x) = 1$ при $x \in A$, $0$ при $x \notin A$.

Свойства композиции

1. Ассоциативность: $(h \circ g) \circ f = h \circ (g \circ f)$.
2. Не коммутативна (в общем случае).
3. $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$, если $f$, $g$ биективны.
4. Композиция инъекций — инъекция; сюръекций — сюръекция; биекций — биекция.

3. КОМБИНАТОРИКА (РАСШИРЕННЫЙ РАЗДЕЛ)

Базовые формулы (факториал, $A_n^k$, $C_n^k$, $P_n$, размещения/сочетания с повторениями, полиномиальная теорема, формула Стирлинга, свёртка Вандермонда, треугольник Паскаля) — см. шпаргалку по терверу (terver.md, раздел 1). Здесь — расширенный раздел.

3.1. Принципы и правила

Определения и методы

1. Принцип Дирихле: Если $n$ объектов размещены по $m$ ящикам и $n > m$, то хотя бы в одном ящике более одного объекта. Обобщение: если $n > k m$, то в каком-то ящике $\ge k+1$ объектов.
2. Правило включения-исключения (полная форма): $$ \left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|. $$
3. Число элементов, не принадлежащих ни одному $A_i$: $$ |U \setminus \bigcup A_i| = |U| - \sum_i |A_i| + \sum_{i
4. Задача о беспорядках (субфакториал $!n$): Число перестановок $n$ элементов, где ни один не стоит на своём месте: $$ !n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor. $$ Рекуррентно: $!n = (n-1)(!(n-1) + !(n-2))$, $!0 = 1$, $!1 = 0$.

3.2. Числа Стирлинга и разбиения

Определения

1. Число Стирлинга II рода $\{^n_k\}$: Число способов разбить $n$-элементное множество на $k$ непустых непересекающихся подмножеств (блоков).
2. Число Стирлинга I рода (без знака) $\left[^n_k\right]$: Число перестановок $n$ элементов, имеющих ровно $k$ циклов.
3. Число Белла $B_n$: Общее число всех разбиений $n$-элементного множества: $B_n = \sum_{k=1}^n \left\{^n_k\right\}$.
4. Число Каталана $C_n$: $C_n = \frac{1}{n+1} \binom{2n}{n}$.

Рекуррентные соотношения и формулы

Числа Стирлинга I рода (рекуррентно)

$$ \left[^n_k\right] = (n-1) \left[^{n-1}_{\;\;k}\right] + \left[^{n-1}_{k-1}\right], \quad \left[^n_0\right] = 0\ (n \ge 1), \quad \left[^0_0\right] = 1. $$

3.3. Производящие функции

Определения

1. Обычная производящая функция (ОПФ): Для последовательности $\{a_n\}_{n=0}^\infty$: $$ A(x) = \sum_{n=0}^\infty a_n x^n. $$
2. Экспоненциальная производящая функция (ЭПФ): $E(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}$.
3. Коэффициент: $a_n = [x^n] A(x)$ — оператор взятия коэффициента при $x^n$.

Таблица основных производящих функций

Операции с производящими функциями

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

Методы решения линейных рекуррент

Общий вид: $a_n + c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} = f(n)$.

Характеристическое уравнение: $\lambda^k + c_1 \lambda^{k-1} + \dots + c_k = 0$.

Однородный случай ($f(n) = 0$)

Если корни $\lambda_1, \dots, \lambda_k$ характеристического уравнения различны: $$ a_n^{\text{(общ. однор.)}} = C_1 \lambda_1^n + C_2 \lambda_2^n + \dots + C_k \lambda_k^n. $$

Если корень $\lambda$ имеет кратность $r$, ему соответствуют слагаемые: $(C_0 + C_1 n + \dots + C_{r-1} n^{r-1}) \lambda^n$.

Неоднородный случай

Частное решение ищется в виде, подобном правой части:

• $f(n) = P_m(n)$ (многочлен степени $m$) $\to$ ищем $Q_m(n)$;
• $f(n) = b \cdot d^n$ $\to$ ищем $C \cdot d^n$ (умножаем на $n^s$, где $s$ — кратность $d$ как корня характеристического уравнения);
• $f(n) = b \cos\omega n$ или $b \sin\omega n$ $\to$ ищем $C_1 \cos\omega n + C_2 \sin\omega n$.

Общее решение: $a_n = a_n^{\text{(общ. однор.)}} + a_n^{\text{(частн.)}}$.

Таблица классических рекуррент

4. БУЛЕВЫ ФУНКЦИИ И БУЛЕВА АЛГЕБРА

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

Определения

1. Булева функция: Отображение $f: \mathbb{B}^n \to \mathbb{B}$, $\mathbb{B} = \{0, 1\}$.
2. $P_2$: Множество всех булевых функций от любого числа переменных.
3. $P_2(n)$: Множество булевых функций от $n$ переменных. $|P_2(n)| = 2^{2^n}$.
4. Существенные и фиктивные переменные: $x_i$ — фиктивная, если $f_{x_i=0} = f_{x_i=1}$.
5. Таблица истинности: Перечисление всех $2^n$ наборов значений переменных в стандартном порядке (лексикографическом).
6. Формула: Выражение, построенное из переменных, констант 0,1, и операций над $P_2$.
7. Суперпозиция (композиция): Подстановка функций в функцию.
8. Операция замыкания: $[K]$ — множество всех функций, получаемых из $K$ суперпозициями (и переименованием переменных).
9. Замкнутый класс: $[K] = K$.
10. Полная система: $[K] = P_2$ (класс $K$ порождает все булевы функции).
11. Базис: Полная система, из которой нельзя удалить ни одной функции без потери полноты.

Элементарные булевы функции

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

Определения

1. Элементарная конъюнкция (минтерм): Конъюнкция литералов (переменных или их отрицаний), где каждая переменная входит не более одного раза.
2. Дизъюнктивная нормальная форма (ДНФ): Дизъюнкция элементарных конъюнкций.
3. Совершенная ДНФ (СДНФ): Каждая элементарная конъюнкция содержит все $n$ переменных.
4. Элементарная дизъюнкция (макстерм): Дизъюнкция литералов.
5. Конъюнктивная нормальная форма (КНФ): Конъюнкция элементарных дизъюнкций.
6. Совершенная КНФ (СКНФ): Каждая элементарная дизъюнкция содержит все $n$ переменных.

Построение СДНФ и СКНФ по таблице истинности

СДНФ: Для каждого набора, где $f = 1$, строим конъюнкцию литералов: $x_i$, если $x_i = 1$, и $\overline{x}_i$, если $x_i = 0$. Все конъюнкции соединяем $\lor$.

СКНФ: Для каждого набора, где $f = 0$, строим дизъюнкцию литералов: $\overline{x}_i$, если $x_i = 1$, и $x_i$, если $x_i = 0$. Все дизъюнкции соединяем $\land$.

Алгоритм минимизации: метод Куайна–Мак-Класки

1. Строим СДНФ.
2. Склеиваем конъюнкции, отличающиеся ровно в одной переменной (одна с $x_i$, другая с $\overline{x}_i$).
3. Повторяем склеивание, пока возможно.
4. Строим таблицу покрытия: строки — исходные конституенты, столбцы — простые импликанты.
5. Находим минимальное покрытие (ядро + добираем).

Карты Карно (диаграммы Вейча)

Визуальный метод минимизации для $n \le 4$ (иногда 5) переменных. Принцип: соседние клетки отличаются ровно в одной переменной. Склеиваем прямоугольники размером $2^k$ клеток, содержащие только единицы. Получаем минимальную ДНФ.

Порядок строк/столбцов в карте Карно (код Грея):

4.3. Замкнутые классы и теорема Поста

Определения и обозначения замкнутых классов

Теорема Поста (критерий полноты)

Система булевых функций $K$ полна ($[K] = P_2$) $\Leftrightarrow$ $K$ не содержится целиком ни в одном из пяти замкнутых классов: $$ K \not\subseteq T_0,\ K \not\subseteq T_1,\ K \not\subseteq S,\ K \not\subseteq M,\ K \not\subseteq L. $$

Проверка полноты: протокол (алгоритм)

1. Для каждой $f \in K$ проверяем принадлежность классам $T_0, T_1, S, M, L$.
2. Строим таблицу «функция $\times$ класс».
3. Если каждый столбец $T_0, T_1, S, M, L$ содержит хотя бы один «$\times$» (не принадлежит) — система полна.
4. Для поиска базиса: проверяем все собственные подсистемы на полноту.

Предполные классы

Это в точности пять классов Поста: $T_0, T_1, S, M, L$. Любой собственный замкнутый класс содержится хотя бы в одном из них.

4.4. Полином Жегалкина (алгебраическая нормальная форма)

Определение

Полином Жегалкина — представление булевой функции в виде суммы по модулю 2 конъюнкций (без отрицаний): $$ f(x_1, \dots, x_n) = a_0 \oplus \bigoplus_{i} a_i x_i \oplus \bigoplus_{i

Методы построения

1. Метод неопределённых коэффициентов: Подставляем все $2^n$ наборов значений переменных и решаем систему линейных уравнений над $\mathbb{B}$ относительно $a_I$.
2. Метод преобразования СДНФ: Заменяем $\lor$ на $\oplus$ (после проверки ортогональности конъюнкций), $\overline{x}$ на $x \oplus 1$, раскрываем скобки и приводим подобные ($x \oplus x = 0$).
3. Метод треугольника (через таблицу истинности): Рекуррентное преобразование строк таблицы.

Линейность

Функция линейна $\Leftrightarrow$ её полином Жегалкина имеет степень $\le 1$. Это критерий принадлежности классу $L$.

Типовые ошибки

⚠ Ошибка 1. Проверка монотонности: просмотр не всех пар. Для проверки $a \preceq b$ нужно перебрать ВСЕ наборы, где $a$ предшествует $b$ (покоординатно не больше). Если хотя бы для одной такой пары $f(a) > f(b)$ — функция не монотонна.

⚠ Ошибка 2. Линейная функция: забывают константу. $f(x) = x_1 \oplus 1$ — линейна! Полином Жегалкина: $x_1 \oplus 1$ (степень 1). Константа допустима в линейной функции.

⚠ Ошибка 3. Самодвойственность: ошибка в построении двойственной. $f^*(x_1,\dots,x_n) = \overline{f(\overline{x}_1,\dots,\overline{x}_n)}$. Студенты часто берут отрицание ТОЛЬКО результата или ТОЛЬКО аргументов, забывая про второе.

⚠ Ошибка 4. Полнота системы: достаточно найти представителя. Если функция НЕ принадлежит классу $K$, то в столбце $K$ ставим «$\times$». Если в каждом из 5 столбцов есть хотя бы один «$\times$» — система полна. Не нужно проверять принадлежность всех функций ко всем классам.

⚠ Ошибка 5. СДНФ vs СКНФ: путают построение. СДНФ: берём наборы где $f=1$, строим конъюнкции, переменная $0$ входит с отрицанием. СКНФ: берём наборы где $f=0$, строим дизъюнкции, переменная $1$ входит с отрицанием. Мнемоника: «ищем противоположное значение переменной для включения в элементарную форму».

⚠ Ошибка 6. Полином Жегалкина: забывают $a_0$. При построении полинома Жегалкина нужно найти ВСЕ коэффициенты $a_I$, включая $a_0$ (свободный член). Подстановка нулевого набора даёт $a_0 = f(0,\dots,0)$.

Мнемонические правила

☞ Пять классов Поста (для запоминания): «ТоТаСамМоЛ» — $T_0$, $T_1$, $S$ (Self-dual), $M$ (Monotone), $L$ (Linear). Система полна, если НЕ содержится ни в одном из них.

☞ Проверка $T_0$ и $T_1$: «$T_0$ — функция сохраняет 0»: подставить все нули, результат должен быть 0. «$T_1$ — функция сохраняет 1»: подставить все единицы, результат должен быть 1.

☞ Карта Карно: порядок переменных — код Грея (00, 01, 11, 10). Соседние клетки отличаются ровно в одной переменной. Можно склеивать прямоугольники $1\times2^k$, $2^k\times1$, $2^k\times2^m$ клеток.

☞ Штрих Шеффера $x \mid y$ — универсальный базис. Из одной этой функции можно построить все булевы функции. $\neg x = x \mid x$, $x \land y = \neg(x \mid y) = (x \mid y) \mid (x \mid y)$.

Приложения

Схемотехника: булевы функции — основа проектирования логических схем процессоров и микроконтроллеров. Минимизация ДНФ снижает число логических вентилей. Релейно-контактные схемы: реализация булевых функций на реле. SQL: WHERE-условия — булевы выражения. Условная компиляция: препроцессорные условия. Базы знаний: логический вывод на основе булевых функций.

5. ТЕОРИЯ ГРАФОВ

5.1. Основные понятия

Определения

Лемма о рукопожатиях

$$ \sum_{v \in V} \deg(v) = 2|E|. $$

Следствие: Число вершин нечётной степени в графе чётно.

Способы задания графов

5.2. Деревья

Определения и теоремы

1. Дерево: Связный граф без циклов.
2. Лес: Граф без циклов (каждая компонента — дерево).

Критерии дерева (для графа с $n$ вершинами следующие утверждения эквивалентны):

1. $G$ — дерево (связный и без циклов).
2. $G$ связен и $|E| = n-1$.
3. $G$ без циклов и $|E| = n-1$.
4. Для любой пары вершин существует единственная простая цепь.
5. $G$ связен, но при удалении любого ребра перестаёт быть связным.
6. $G$ без циклов, но добавление любого ребра создаёт цикл.

Остовное дерево

Остов (остовное дерево, spanning tree): Остовный подграф (включает все $n$ вершин), являющийся деревом. Каждый связный граф имеет хотя бы один остов.

Число остовных деревьев (теорема Кирхгофа, матричная теорема о деревьях): $$ \tau(G) = \frac{1}{n} \prod_{i=1}^{n-1} \lambda_i, $$ где $\lambda_i$ — ненулевые собственные значения матрицы Кирхгофа (лапласиана) $L = D - A$, или любой алгебраический кофактор $L$.

5.3. Циклы и связность

Определения

1. Вершинная связность $\varkappa(G)$: Минимальное число вершин, удаление которых делает граф несвязным.
2. Рёберная связность $\lambda(G)$: Минимальное число рёбер, удаление которых делает граф несвязным.
3. Теорема Уитни: $\varkappa(G) \le \lambda(G) \le \delta(G)$, где $\delta(G)$ — минимальная степень вершины.
4. $k$-связный граф: $\varkappa(G) \ge k$.
5. Блок: Максимальный 2-связный подграф (или мост).
6. Точка сочленения: Вершина, удаление которой увеличивает число компонент.
7. Мост: Ребро, удаление которого увеличивает число компонент.

Эйлеровы графы

Эйлеров цикл: Цикл, содержащий все рёбра графа по одному разу.

Теорема Эйлера: Связный граф эйлеров (содержит эйлеров цикл) $\Leftrightarrow$ все вершины имеют чётную степень.

Эйлерова цепь (путь): Цепь, содержащая все рёбра. Существует $\Leftrightarrow$ ровно $0$ или $2$ вершины имеют нечётную степень.

Гамильтоновы графы

Гамильтонов цикл: Простой цикл, проходящий через все вершины.

Достаточные условия:

• Теорема Дирака: Если $\forall v: \deg(v) \ge n/2$, то граф гамильтонов.
• Теорема Оре: Если для любой пары несмежных вершин $\deg(u) + \deg(v) \ge n$, то граф гамильтонов.
• Теорема Хватала: Более общее условие на степенную последовательность.

Примечание: Задача распознавания гамильтоновости — NP-полна.

5.4. Планарность

Определения

1. Плоский граф: Изображён на плоскости без пересечения рёбер (рёбра пересекаются только в вершинах).
2. Планарный граф: Может быть изображён как плоский.
3. Грань: Максимальная связная область плоскости, ограниченная рёбрами. Внешняя грань — бесконечная.

Формула Эйлера

Для связного плоского графа с $n$ вершинами, $m$ рёбрами и $f$ гранями: $$ n - m + f = 2. $$

Следствия для любого планарного графа (без петель и кратных рёбер, $n \ge 3$):

1. $m \le 3n - 6$.
2. Если нет треугольников (граф свободен от $K_3$): $m \le 2n - 4$.
3. В любом планарном графе существует вершина степени $\le 5$.

Критерий Понтрягина–Куратовского

Граф планарен $\Leftrightarrow$ он не содержит подграфов, гомеоморфных $K_5$ или $K_{3,3}$.

Гомеоморфность: возможность получить один граф из другого подразбиением рёбер (вставкой вершин степени 2).

Критерий Вагнера

Граф планарен $\Leftrightarrow$ он не содержит миноров $K_5$ или $K_{3,3}$. (Минор получается удалением вершин/рёбер и стягиванием рёбер.)

5.5. Раскраска графов

Определения

1. Правильная раскраска вершин: Приписывание цветов вершинам так, что смежные вершины имеют разные цвета.
2. Хроматическое число $\chi(G)$: Минимальное число цветов, необходимое для правильной раскраски вершин.
3. $k$-раскрашиваемый граф: $\chi(G) \le k$.
4. Рёберная раскраска: $\chi_E(G)$ — минимальное число цветов для рёбер.
5. Хроматический многочлен $P_G(k)$: Число правильных раскрасок вершин $k$ цветами (как функция от $k$). $P_G(k)$ — многочлен от $k$ степени $|V|$.

Основные теоремы

1. Теорема о четырёх красках: Любой планарный граф 4-раскрашиваем: $\chi(G) \le 4$.
2. Теорема о пяти красках (Хивуд): Каждый планарный граф 5-раскрашиваем. (Доказательство конструктивно.)
3. Теорема Визинга: $\Delta \le \chi_E(G) \le \Delta + 1$, где $\Delta$ — максимальная степень вершины.
4. Теорема Брукса: Если $G$ — связный граф, не являющийся полным и не являющийся нечётным циклом, то $\chi(G) \le \Delta$.

Хроматический многочлен

Рекуррентное соотношение (удаление–стягивание): $$ P_G(k) = P_{G-e}(k) - P_{G/e}(k), $$ где $G-e$ — удаление ребра, $G/e$ — стягивание (склеивание концов). Для графа из $n$ изолированных вершин: $P(k) = k^n$.

5.6. Паросочетания и покрытия

Определения

1. Паросочетание: Множество попарно несмежных рёбер.
2. Максимальное паросочетание: Нельзя добавить ни одного ребра (по включению).
3. Наибольшее паросочетание: Содержит максимально возможное число рёбер. Обозначение: $\nu(G)$.
4. Совершенное паросочетание: Покрывает все вершины ($\nu = n/2$).
5. Вершинное покрытие: Множество вершин, инцидентных всем рёбрам.
6. Число вершинного покрытия $\tau(G)$: Минимальный размер вершинного покрытия.

Теорема Кёнига–Эгервари (для двудольных графов)

В двудольном графе размер наибольшего паросочетания равен размеру минимального вершинного покрытия: $\nu(G) = \tau(G)$.

Теорема Холла (условие существования совершенного паросочетания в двудольном графе)

Для двудольного графа $G = (X \sqcup Y, E)$ совершенное паросочетание, покрывающее $X$, существует $\Leftrightarrow$ для любого $S \subseteq X$: $|N(S)| \ge |S|$, где $N(S)$ — множество соседей вершин из $S$.

5.7. Потоки в сетях

Определения

1. Сеть: Ориентированный граф с двумя выделенными вершинами: источник $s$ и сток $t$, и функцией пропускной способности $c: E \to \mathbb{R}^+$.
2. Поток $f: E \to \mathbb{R}^+$:
   • $0 \le f(e) \le c(e)$ (ограничение пропускной способности);
   • $\sum_{u \to v} f(u,v) = \sum_{v \to w} f(v,w)$ для всех $v \neq s,t$ (сохранение потока).
3. Величина потока $\|f\| = \sum_{s \to v} f(s, v) - \sum_{v \to s} f(v, s)$.
4. Разрез $(S, T)$: $s \in S$, $t \in T = V \setminus S$.
5. Пропускная способность разреза: $c(S, T) = \sum_{u \in S, v \in T} c(u, v)$.

Теорема Форда–Фалкерсона (о максимальном потоке и минимальном разрезе)

Максимальная величина потока из $s$ в $t$ равна минимальной пропускной способности разреза: $$ \max_{f} \|f\| = \min_{(S,T)} c(S, T). $$

5.8. Алгоритмы на графах

Алгоритм Дейкстры (кратчайшие пути из одной вершины)

Для графа с неотрицательными весами. Время: $O((|V|+|E|)\log |V|)$ с двоичной кучей. Идея: на каждом шаге выбираем непосещённую вершину с минимальной оценкой расстояния, релаксируем рёбра.

Алгоритм Флойда–Уоршелла (кратчайшие пути между всеми парами)

Динамическое программирование. $d_{ij}^{(0)} = w_{ij}$ (вес ребра, $\infty$ если нет). Итерация: $$ d_{ij}^{(k)} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}). $$ Время: $O(|V|^3)$.

Алгоритм Форда–Беллмана

Кратчайшие пути при любых (в т.ч. отрицательных) весах, но без циклов отрицательного веса. Время: $O(|V| \cdot |E|)$.

Алгоритм Крускала (минимальный остов)

1. Сортируем рёбра по возрастанию веса.
2. Просматриваем рёбра: если концы в разных компонентах — добавляем ребро в остов (система непересекающихся множеств, DSU). Время: $O(|E| \log |V|)$.

Алгоритм Прима

Начинаем с одной вершины. На каждом шаге добавляем минимальное ребро, соединяющее дерево с новой вершиной. Время: $O(|E| \log |V|)$ с кучей.

Поиск в глубину (DFS) и ширину (BFS)

Типовые задачи и алгоритмы решения

► Задача 1. Проверка графа на эйлеровость. Алгоритм:

1. Проверить связность (DFS от любой вершины).
2. Подсчитать число вершин нечётной степени.
3. $0$ вершин нечётной степени $\to$ эйлеров цикл.
4. $2$ вершины нечётной степени $\to$ эйлерова цепь.
5. Иначе $\to$ не эйлеров.

Пример: Граф «конверт» (5 вершин). Степени: $3,3,3,2,1$ — три вершины нечётной степени, не эйлеров.

► Задача 2. Построение минимального остовного дерева (Крускал). Алгоритм:

1. Отсортировать рёбра по возрастанию веса.
2. Инициализировать DSU (каждая вершина в своей компоненте).
3. Для каждого ребра $(u,v)$ в порядке возрастания веса:
   • Если $u$ и $v$ в разных компонентах — добавить ребро в остов, объединить компоненты.
4. Остановиться, когда добавлено $n-1$ рёбер.

Пример: Граф из 4 городов с расстояниями. Остовное дерево даст минимальную суммарную длину дорог.

► Задача 3. Проверка двудольности. Алгоритм (BFS/DFS):

1. Покрасить стартовую вершину в цвет 0.
2. Для каждого соседа: если не покрашен — покрасить в противоположный цвет ($1-c$), если покрашен в тот же цвет — граф НЕ двудольный.
3. Повторить для всех компонент связности.

Пример: Любое дерево двудольно. $K_3$ (треугольник) — не двудольный. $K_{2,3}$ — двудольный.

► Задача 4. Поиск кратчайшего пути (Дейкстра). Алгоритм:

1. $d[v] = \infty$, $d[\text{start}] = 0$.
2. Очередь с приоритетом по $d[v]$.
3. Извлекаем вершину с минимальным $d[v]$, релаксируем рёбра: если $d[u] + w(u,v) < d[v]$, обновляем $d[v]$.

Важно: Работает только для неотрицательных весов!

Типовые ошибки

⚠ Ошибка 1. Эйлеров ≠ Гамильтонов. Эйлеров цикл — проход по всем РЁБРАМ по одному разу. Гамильтонов — по всем ВЕРШИНАМ. Эйлеровость проверяется за $O(|V|)$, гамильтоновость — NP-полная задача.

⚠ Ошибка 2. Дерево: путают количество рёбер. В дереве с $n$ вершинами ровно $n-1$ рёбер. Лес из $k$ компонент-деревьев на $n$ вершинах: $n-k$ рёбер.

⚠ Ошибка 3. Планарность: забывают проверять $m > 3n-6$. Это НЕОБХОДИМОЕ условие. Если $m \le 3n-6$, это НЕ достаточно для планарности. Нужен критерий Понтрягина–Куратовского.

⚠ Ошибка 4. Формула Эйлера только для СВЯЗНЫХ плоских графов. $n - m + f = 2$ требует связности. Для графа с $c$ компонентами: $n - m + f = 1 + c$.

⚠ Ошибка 5. Дейкстра и отрицательные веса. Алгоритм Дейкстры даёт НЕВЕРНЫЙ результат при отрицательных весах! Для графов с отрицательными весами используйте Форда–Беллмана ($O(|V|\cdot|E|)$).

⚠ Ошибка 6. Хроматическое число полного графа. $\chi(K_n) = n$, а не $2$. Полный граф требует $n$ цветов — каждая вершина должна быть своего цвета.

⚠ Ошибка 7. Совершенное паросочетание требует чётного числа вершин. В графе с нечётным числом вершин совершенного паросочетания не существует по определению.

Мнемонические правила

☞ Эйлеров цикл — «все степени чётны». Представьте: чтобы войти и выйти из вершины, нужно чётное число рёбер при этой вершине (одно — войти, другое — выйти).

☞ Лемма о рукопожатиях: «Сумма степеней = удвоенному числу рёбер». Каждое ребро учитывается дважды — по одному разу на каждом конце.

☞ Формула Эйлера $n - m + f = 2$: «Вершины минус рёбра плюс грани равно два». Для запоминания: у тетраэдра (треугольной пирамиды) $n=4$, $m=6$, $f=4$: $4-6+4=2$.

☞ Дважды линейчатые поверхности в графике: $K_5$ и $K_{3,3}$ — два «запрещённых» подграфа для планарности. Запомнить: «пять точек — все соединены» и «три на три — все соединены между долями».

Приложения

GPS-навигация: алгоритм Дейкстры/А* ($A^*$) для построения маршрутов. Социальные сети: граф друзей, компоненты связности, центральность. Интернет: маршрутизация (протоколы OSPF, RIP — алгоритмы на графах). Проектирование сетей: минимальное остовное дерево для прокладки кабеля. Расписания: топологическая сортировка для упорядочивания задач с зависимостями. Раскраска карт: планирование частот в сотовой связи (чтобы соседние вышки не мешали друг другу).

6. ТЕОРИЯ ЧИСЕЛ И КРИПТОГРАФИЯ (ДИСКРЕТНЫЙ АСПЕКТ)

6.1. Делимость и сравнения

Определения

1. $a$ делит $b$ ($a \mid b$): $\exists k \in \mathbb{Z}: b = a k$.
2. НОД ($\gcd(a,b)$): Наибольший общий делитель.
3. НОК ($\operatorname{lcm}(a,b)$): Наименьшее общее кратное.
4. Взаимно простые числа: $\gcd(a, b) = 1$.
5. Сравнение по модулю $m$: $a \equiv b \pmod{m} \Leftrightarrow m \mid (a - b)$.
6. Кольцо вычетов $\mathbb{Z}_m$: $\{0, 1, \dots, m-1\}$ со сложением и умножением по модулю $m$.
7. Приведённая система вычетов: Числа, взаимно простые с $m$. $\mathbb{Z}_m^*$ — мультипликативная группа обратимых элементов $\mathbb{Z}_m$, $|\mathbb{Z}_m^*| = \varphi(m)$.

Алгоритм Евклида

$$ \gcd(a, b) = \gcd(b, a \bmod b); $$ итеративно, пока $b \neq 0$. Время: $O(\log \min(a,b))$.

Расширенный алгоритм Евклида

Находит $x, y \in \mathbb{Z}$ такие, что $ax + by = \gcd(a, b)$ (соотношение Безу). Позволяет найти обратный элемент в $\mathbb{Z}_m^*$: если $\gcd(a, m) = 1$, то $a^{-1} \equiv x \pmod{m}$.

Функция Эйлера $\varphi(n)$

Число натуральных $k \le n$, взаимно простых с $n$.

Свойства:

1. $\varphi(p) = p-1$ для простого $p$.
2. $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.
3. Мультипликативность: если $\gcd(m, n) = 1$, то $\varphi(mn) = \varphi(m) \varphi(n)$.
4. Для $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$: $\varphi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$.

6.2. Основные теоремы

Малая теорема Ферма

Если $p$ — простое число и $p \nmid a$, то: $$ a^{p-1} \equiv 1 \pmod{p}. $$

Теорема Эйлера

Если $\gcd(a, m) = 1$, то: $$ a^{\varphi(m)} \equiv 1 \pmod{m}. $$

Китайская теорема об остатках

Если $m_1, \dots, m_k$ попарно взаимно просты, то для любых $a_1, \dots, a_k$ система сравнений $$ x \equiv a_1 \pmod{m_1},\ \dots,\ x \equiv a_k \pmod{m_k} $$ имеет единственное решение по модулю $M = m_1 \cdots m_k$: $$ x \equiv \sum_{i=1}^k a_i M_i y_i \pmod{M}, $$ где $M_i = M/m_i$, а $y_i = M_i^{-1} \pmod{m_i}$.

Основная теорема арифметики

Любое $n > 1$ однозначно (с точностью до порядка) разлагается в произведение простых чисел: $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$.

6.3. RSA (основы)

Генерация ключей

1. Генерируем два больших простых $p$, $q$.
2. $n = pq$, $\varphi(n) = (p-1)(q-1)$.
3. Открытая экспонента $e$: $1 < e < \varphi(n)$, $\gcd(e, \varphi(n)) = 1$.
4. Секретная экспонента $d = e^{-1} \pmod{\varphi(n)}$ (расширенный алгоритм Евклида).
5. Открытый ключ: $(n, e)$. Закрытый ключ: $(n, d)$.

Шифрование и дешифрование

• Шифрование: $c \equiv m^e \pmod{n}$.
• Дешифрование: $m \equiv c^d \pmod{n}$.

Корректность: $m^{ed} \equiv m \pmod{n}$ по теореме Эйлера.

Типовые задачи

► Задача 1. Вычисление НОД (алгоритм Евклида). Алгоритм:

1. $\gcd(a, b)$: пока $b \neq 0$, заменяем $(a, b)$ на $(b, a \bmod b)$.
2. Результат — последнее ненулевое $a$.

Пример: $\gcd(48, 18)$. $48 \bmod 18 = 12$, $(18, 12)$. $18 \bmod 12 = 6$, $(12, 6)$. $12 \bmod 6 = 0$ → $\gcd = 6$.

► Задача 2. Нахождение обратного элемента в $\mathbb{Z}_m^*$ (расширенный алгоритм Евклида). Алгоритм:

1. Применить расширенный алгоритм Евклида к $(a, m)$, получить $ax + my = 1$.
2. $a^{-1} \equiv x \pmod{m}$.

Пример: Найти $7^{-1} \pmod{40}$. Расширенный алгоритм: $7 \cdot 23 + 40 \cdot (-4) = 1$. $7^{-1} \equiv 23 \pmod{40}$.

► Задача 3. Решение системы сравнений (Китайская теорема об остатках). Алгоритм:

1. $M = m_1 \cdots m_k$, $M_i = M/m_i$.
2. Для каждого $i$ найти $y_i = M_i^{-1} \pmod{m_i}$.
3. $x \equiv \sum a_i M_i y_i \pmod{M}$.

Пример: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$. $M=105$, $M_1=35$, $M_2=21$, $M_3=15$. $y_1=35^{-1}=2 \pmod{3}$, $y_2=21^{-1}=1 \pmod{5}$, $y_3=15^{-1}=1 \pmod{7}$. $x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 233 \equiv 23 \pmod{105}$.

Типовые ошибки

⚠ Ошибка 1. Обратный элемент существует не всегда. $a^{-1} \pmod{m}$ существует $\Leftrightarrow$ $\gcd(a,m) = 1$. Для $2^{-1} \pmod{4}$ обратного нет.

⚠ Ошибка 2. Малая теорема Ферма: забывают условие $p \nmid a$. $a^{p-1} \equiv 1 \pmod{p}$ верно только при $p \nmid a$. Если $p \mid a$, то $a \equiv 0 \pmod{p}$ и $a^{p-1} \equiv 0 \pmod{p}$.

⚠ Ошибка 3. Функция Эйлера: путают формулу для степени простого. $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$, а не $p^k-1$. Для $p=2$, $k=3$: $\varphi(8) = 8-4 = 4$, а не $7$.

⚠ Ошибка 4. Китайская теорема об остатках: модули должны быть попарно взаимно просты. Если $\gcd(m_i, m_j) \neq 1$ для какой-то пары, метод не работает напрямую.

⚠ Ошибка 5. RSA: путают открытую и секретную экспоненту. $e$ — открытая (public), $d$ — секретная (private). Шифрование: $c \equiv m^e \pmod{n}$. Дешифрование: $m \equiv c^d \pmod{n}$.

Мнемонические правила

☞ Малая теорема Ферма: «Если $p$ простое и не делит $a$, то $a^{p-1}$ даёт остаток 1 при делении на $p$». Полезно для быстрой проверки простоты.

☞ Алгоритм Евклида: «Всё время делим большее на меньшее и берём остаток, пока не получим ноль». На каждом шаге $\gcd(a,b) = \gcd(b, a \bmod b)$.

☞ Функция Эйлера: «Сколько чисел до $n$ взаимно просты с $n$». Для простого $p$: $\varphi(p) = p-1$ (все, кроме самого $p$).

7. ОСНОВЫ ФОРМАЛЬНЫХ ЯЗЫКОВ И АВТОМАТОВ

7.1. Алфавит, слова, языки

Определения

1. Алфавит $\Sigma$: Конечное множество символов.
2. Слово (цепочка): Конечная последовательность символов из $\Sigma$.
3. Пустое слово $\varepsilon$: Слово длины 0.
4. $\Sigma^*$: Множество всех слов над $\Sigma$ (включая $\varepsilon$).
5. $\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}$.
6. Язык: Произвольное подмножество $L \subseteq \Sigma^*$.
7. Конкатенация: $xy$, $\|xy\| = \|x\| + \|y\|$. $x \varepsilon = \varepsilon x = x$.
8. Степень слова: $w^0 = \varepsilon$, $w^n = w w^{n-1}$.

Операции над языками

7.2. Регулярные языки и конечные автоматы

Определения

1. Детерминированный конечный автомат (ДКА): $A = (Q, \Sigma, \delta, q_0, F)$, где $Q$ — конечное множество состояний, $\delta: Q \times \Sigma \to Q$, $q_0 \in Q$ — начальное, $F \subseteq Q$ — допускающие.
2. Недетерминированный конечный автомат (НКА): $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$.
3. Язык, допускаемый автоматом: $L(A) = \{w \in \Sigma^* \mid \delta^*(q_0, w) \in F\}$.
4. Регулярный язык: Язык, допускаемый некоторым конечным автоматом.

Регулярные выражения (определение индуктивно)

1. $\varnothing$, $\varepsilon$, $a$ ($a \in \Sigma$) — регулярные выражения.
2. Если $R$, $S$ — регулярные выражения, то $(R+S)$ (объединение), $(RS)$ (конкатенация), $(R^*)$ (звезда Клини) — регулярные выражения.

Основные теоремы

1. Теорема Клини: Класс регулярных языков = класс языков, описываемых регулярными выражениями = класс языков, допускаемых конечными автоматами.
2. Теорема о разрастании (pumping lemma): Если $L$ регулярен, то $\exists n > 0$ такое, что любое $w \in L$, $\|w\| \ge n$, можно разбить $w = xyz$, где $\|xy\| \le n$, $\|y\| > 0$, и $\forall k \ge 0: x y^k z \in L$.
3. Детерминизация: Для любого НКА существует эквивалентный ДКА (конструкция подмножеств — теорема Рабина–Скотта). Число состояний ДКА может быть экспоненциально большим: $|Q_{\text{ДКА}}| \le 2^{|Q_{\text{НКА}}|}$.

7.3. Иерархия Хомского

Включения строгие: Регулярные $\subset$ КС $\subset$ КЗ $\subset$ Рекурсивные $\subset$ Рекурсивно перечислимые.

Типовые задачи

► Задача 1. Построение ДКА по регулярному выражению. Алгоритм (синтез):

1. Построить НКА по регулярному выражению (метод Томпсона).
2. Детерминизировать НКА: каждое состояние ДКА — подмножество состояний НКА.
3. Минимизировать ДКА (алгоритм Хопкрофта или Мура).

Пример: Регулярное выражение $(a|b)^*abb$. ДКА будет иметь 4 состояния и распознавать строки, заканчивающиеся на $abb$.

► Задача 2. Доказательство нерегулярности языка (pumping lemma). Алгоритм:

1. Предположить, что язык $L$ регулярен, пусть $n$ — константа из леммы.
2. Выбрать строку $w \in L$, $|w| \ge n$, «проблематичную» для pumping.
3. Показать, что $\forall$ разбиений $w = xyz$ с $|xy| \le n$, $|y| > 0$ найдётся $k$ такое, что $xy^kz \notin L$.

Пример: Язык $L = \{a^m b^m \mid m \ge 0\}$ нерегулярен. Выбираем $w = a^n b^n$. $y$ состоит только из $a$ (т.к. $|xy| \le n$). При $k=2$ число $a$ становится $n+|y|$, а число $b$ — $n$. Строка не в $L$.

► Задача 3. Определение типа грамматики/языка по иерархии Хомского. Алгоритм: Проверить ограничения на правила грамматики:

1. Все правила $A \to aB$ или $A \to a$ или $A \to \varepsilon$ $\to$ регулярная (тип 3).
2. Все правила $A \to \gamma$ (нет контекста) $\to$ КС (тип 2).
3. Правила $\alpha A \beta \to \alpha \gamma \beta$ $\to$ КЗ (тип 1).
4. Иначе — тип 0.

Типовые ошибки

⚠ Ошибка 1. Конечный автомат vs Регулярное выражение. Не всякий язык, допускаемый конечным автоматом, описывается простым регулярным выражением — но по теореме Клини такое выражение ВСЕГДА существует.

⚠ Ошибка 2. Pumping lemma: направление импликации. Лемма работает ТОЛЬКО в одну сторону: «Если язык регулярен, то выполняется свойство разрастания». Обратное неверно! Существуют нерегулярные языки, удовлетворяющие pumping lemma.

⚠ Ошибка 3. НКА может иметь $\varepsilon$-переходы. Недетерминированный автомат может иметь переходы по пустому слову ($\varepsilon$). При детерминизации нужно сначала вычислить $\varepsilon$-closure для каждого состояния.

⚠ Ошибка 4. Детерминизация: экспоненциальный взрыв состояний. ДКА, построенный по НКА с $n$ состояниями, может иметь до $2^n$ состояний. На практике это редкость, но теоретически возможно.

Приложения

Лексический анализ в компиляторах: регулярные выражения $\to$ ДКА для распознавания токенов (lex, flex). Синтаксический анализ: КС-грамматики для разбора языков программирования (yacc, bison). Поиск по тексту: регулярные выражения (grep, sed). Валидация ввода: проверка email, телефонов, паролей. Сетевые протоколы: конечные автоматы для описания состояний протоколов (TCP).

ПРИЛОЖЕНИЕ A: АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ (КРАТКИЙ СПРАВОЧНИК)

A.1. Группы

Определения

1. Группоид: Множество $G$ с бинарной операцией $\cdot: G \times G \to G$.
2. Полугруппа: Группоид с ассоциативностью: $a(bc) = (ab)c$.
3. Моноид: Полугруппа с единичным элементом $e$: $ae = ea = a$.
4. Группа: Моноид, где у каждого элемента есть обратный: $\forall a\ \exists a^{-1}: aa^{-1} = a^{-1}a = e$.
5. Абелева (коммутативная) группа: $ab = ba$ для всех $a, b$.

Теорема Лагранжа

Порядок подгруппы делит порядок конечной группы: $|H| \mid |G|$.

Следствие: Порядок элемента (наименьшее $n: a^n = e$) делит порядок группы.

Циклическая группа

Порождена одним элементом: $G = \langle a \rangle = \{a^n \mid n \in \mathbb{Z}\}$. Все циклические группы порядка $n$ изоморфны $\mathbb{Z}_n$.

A.2. Кольца и поля

A.3. Решётки

Определения

1. Решётка (lattice): Частично упорядоченное множество $(L, \le)$, в котором для любых $a, b$ существуют супремум $a \lor b$ (наименьшая верхняя грань) и инфимум $a \land b$ (наибольшая нижняя грань).
2. Дистрибутивная решётка: $a \land (b \lor c) = (a \land b) \lor (a \land c)$.
3. Булева алгебра: Дистрибутивная решётка с дополнениями ($\forall a\ \exists \overline{a}: a \land \overline{a} = 0, a \lor \overline{a} = 1$).
4. Атом: Элемент $a \neq 0$, не имеющий предшественников, кроме $0$ (покрывает $0$).

Изоморфизм Стоуна: Любая конечная булева алгебра изоморфна булеану $\mathcal{P}(X)$ с операциями $\cap, \cup, \overline{\cdot}$.

ПРИЛОЖЕНИЕ B: ШПАРГАЛКА ПО ФОРМУЛАМ (QUICK REFERENCE)

B.1. Логика и булевы функции

B.2. Теория графов

B.3. Комбинаторика

B.4. Теория чисел

B.5. Формальные языки

ПРИЛОЖЕНИЕ C: ТИПОВЫЕ ЗАДАЧИ И АЛГОРИТМЫ РЕШЕНИЯ

C.1. Проверка полноты системы булевых функций

1. Для каждой функции заполняем таблицу принадлежности классам $T_0, T_1, S, M, L$.
2. $T_0$: подставляем $0,\dots,0$ — если результат $0$, принадлежит.
3. $T_1$: подставляем $1,\dots,1$ — если результат $1$, принадлежит.
4. $S$: строим двойственную ($f^* = \overline{f(\overline{x}_1, \dots, \overline{x}_n)}$), сравниваем с $f$ по таблице.
5. $M$: проверяем монотонность — если есть пара $a \prec b$, а $f(a) > f(b)$, не монотонна.
6. $L$: строим полином Жегалкина. Если содержит конъюнкции (степень $\ge 2$) — не линейна.
7. Если в каждом из 5 столбцов есть «не принадлежит» — система полна.

C.2. Построение минимальной ДНФ (карта Карно для $n=4$)

1. Заполняем карту по таблице истинности (код Грея $00, 01, 11, 10$).
2. Ищем максимальные прямоугольные блоки из единиц размера $1, 2, 4, 8, 16$ (степени двойки).
3. Для каждого блока выписываем конъюнкцию: переменные, не меняющие значение в блоке (для меняющихся — исключаем).
4. Выбираем минимальное покрытие (ядро + добавляем до покрытия всех единиц).

C.3. Проверка планарности графа

1. Если $n \ge 3$ и $m > 3n-6$ — граф не планарен (необходимое условие).
2. Ищем подграф, гомеоморфный $K_5$ или $K_{3,3}$.
3. Или: последовательно стягиваем рёбра и удаляем вершины, проверяя наличие $K_5$ или $K_{3,3}$ как минора.

C.4. Решение линейных рекуррент

1. Выписываем характеристическое уравнение: $\lambda^k + c_1 \lambda^{k-1} + \dots + c_k = 0$.
2. Находим корни $\lambda_i$ и их кратности.
3. Записываем общее решение однородного: $a_n = \sum (C_0 + C_1 n + \dots) \lambda_i^n$.
4. Находим частное решение неоднородного (если есть правая часть), методом неопределённых коэффициентов.
5. Определяем константы $C_k$ из начальных условий.

ПРИЛОЖЕНИЕ D: БИБЛИОГРАФИЯ И РЕСУРСЫ

D.1. Классические учебники

D.2. Онлайн-ресурсы и материалы

D.3. Рабочая программа (МИФИ/МФТИ/МГУ — типовые темы)

1. Математическая логика: исчисление высказываний, исчисление предикатов.
2. Булевы функции: нормальные формы, замкнутые классы, теорема Поста.
3. Теория множеств: отношения, функции, эквивалентности.
4. Комбинаторика: перечислительные задачи, производящие функции.
5. Теория графов: основные понятия, деревья, планарность, раскраска, потоки.
6. Теория алгоритмов: машина Тьюринга, разрешимость, NP-полнота (для продвинутых программ).
7. Конечные автоматы и регулярные языки.
8. Основы теории кодирования (для некоторых специальностей).