Справочник по дискретной математике

Опубликовано:
Изменено:

Незаконченный мини справочник по дискретной математике. Не имеющий практической пользы в текущем виде.

Логика

\(P(a)\) - Предикат
Утверждение о субъекте \(a\).
\(\forall\) - Квантор всеобщности (All)
Условие, которое верно для всех объектов/элементов
\(\exists\) - Квантор существования (Exists)
Условие, которое верно для некоторых объектов/элементов
\(\exists !\) - Квантор существования и единственности (Exists one)
Условие, которое верно для единственного объекта/элемента
\(\forall a P(a)\) - Высказывание
\(\forall a \exists b P(a, b)\) - "Для всех \(a\) существует \(b\), что \(P(a, b)\) истинно".
\((\forall a \in \mathbb{N}) P(a)\) - "Для всех \(a\) из множества натуральных чисел, \(P(a)\) истинно".
\(\neg(\forall x) P(x) \equiv (\exists x)\neg P(x)\)
\(\neg(\exists x) P(x) \equiv (\forall x)\neg P(x)\)
Правило отрицания кванторов

Множества

\(A = \{a, b, c, \dots, z\}\) - Определение множества с помощью перечисления
Множество \(A\) из элементов \(a, b, c, \dots, z\).
\(A = \{x: P(x)\}\) - Определение множества с помощью предикатов
Множество \(A\) из элементов \(x\), для которых предикат \(P(x)\) истинен.
\(A = \{x: x = f(x)\}\) - Порождающая процедура
Множество \(A\) из элементов \(x\), порожденных функцией \(f(x)\).
\(\in, \notin\) - Принадлежность
\(a \in A\) - элемент \(a\) принадлежит множеству \(A\)
\(b \notin A\) - элемент \(b\) не принадлежит множеству \(A\)
\(\subseteq\) - Подмножество
\(A \subseteq B \equiv \forall x \in A(x \in B)\)
  • Рефлексивность \(\subseteq\): \(\forall A (A \subseteq A)\)
  • Антисимметричность \(\subseteq\): \((A \subseteq B) \land (B \subseteq A) \rightarrow (A = B)\)
  • Транзитивность \(\subseteq\): \((A \subseteq B) \land (B \subseteq C) \rightarrow (A \subseteq C)\)
\(=\) - Равенство
\(A = B \equiv \forall x: (x \in A) \land (x \in B)\)
\(A = B \equiv (A \subseteq B) \land (B \subseteq A)\)
  • Рефлексивность \(=\): \(\forall A (A = A)\)
  • Симметричность \(=\): \(A = B \rightarrow B = A\)
  • Транзитивность \(=\): \((A = B) \land (B = C) \rightarrow (A = C)\)
\(\subset\) - Собственное подмножество
\(A \subset B \equiv (A \subseteq B) \land (A \neq B)\)
\(\varnothing\) - Пустое множество
  • \(\forall A (\varnothing \subseteq A)\)
\(U\) - Универсальное множество
\(\hat{X}\) - Мультимножество
Мультимножество - множество, допускающее включение одного и того же элемента по нескольку раз.
$$\hat{X} = \langle a_1(x_1), \dots , a_n(x_n) \rangle, X = \{x_1, \dots x_n\}$$
  • \(a_i\) - показатель элемента \(x_i\). (количество включений элемента \(x_i\) в \(\hat{X}\))
  • \(X\) - носитель мультимножества \(\hat{X}\)
  • \(m = a_1 + \dots + a_n\) - мощность мультимножества \(\hat{X}\)
  • \(\underline{\hat{X}} = \{x_i \in X | a_i > 0\}\) - состав мультимножества \(\hat{X}\)
\(\mathbb{N} = \{0, 1, 2, 3, ...\}\) - множество натуральных чисел
\(\mathbb{Z} = \{0, \pm 1, \pm 2, \pm 3, ...\}\) - множество целых чисел
\(\mathbb{Q} = \{\frac{p}{q}: p, q \in \mathbb{Z}, q \neq 0\}\) - множество рациональных чисел
\(\mathbb{R}\) = {десятичные дроби} - множество вещественных чисел
\((a_1, a_2, \dots , a_n)\) - Кортеж - упорядоченный набор фиксированной длины.
Индуктивное оперделение:
\(T = (a_2, \dots a_n)\); \((a_1, a_2, \dots , a_n) = \{a_1, \{a_1, T\}\}\) - Кортеж длины n
\(() = \varnothing \)
\((a_3) = \{a_3, \{a_3, ()\}\} = \{a_3, \{a_3, \varnothing \}\}\)
\((a_2, a_3) = \{a_2, \{a_2, (a_3)\}\} = \{a_2, \{a_2, \{a_3, \{a_3, \varnothing \}\}\}\} \)
\((a_1, a_2, a_3) = \{a_1, \{a_1, (a_2, a_3)\}\} = \{a_1, \{a_1, \{a_2, \{a_2, \{a_3, \{a_3, \varnothing \}\}\}\} \}\} \)
\(\sqcup\) - Дизъюнктное объединение - Объединении непересекающихся «копий» множеств.
Дизъюнктное объединение двух конечных множеств, состоящих из \(a\) и \(b\) элементов, будет содержать ровно \(a+b\) элементов, даже если сами множества пересекаются. \(|A| + |B| = |A \sqcup B|\)
\(A \times B\) - Декартово произведение
\(A \times B = \{(a, b): (a \in A) \land (b \in B)\}\)
Элементы \(A \times B\) \((a, b)\) - упорядоченные пары (кортеж длины 2).
  • \(A \times (B \times C) \equiv (A \times B) \times C\)
  • \(A^n = A \times A \times \dots \times A\) (\(n\) раз)
  • \(A^n \times A^m = A^{n+m} \)
  • \((A^n)^m = A^{nm} \)
\(\mathbb{R} \times \mathbb{R}\) или \(\mathbb{R}^2\) - Декартова плоскость
\(V^*\) - Звезда Клини (Вики)
Замыкание Клини множества \(V\)
\(V^* = \bigcup_{i=0}^{\infty} V^i = \{\varnothing\} \cup V \cup V^2 \cup V^3 \cup ...\)
\(V^0 = \left\{\varepsilon \right\} = \left\{\varnothing \right\}\)
\(V^+\) - Плюс Клини
\(V^+ = \bigcup_{i=1}^{\infty} V^i = V^* \cap V^0\)
\(\mathcal{P} (A)\) или \(2^A\) - Показательное множество, Булеан
\(\mathcal{P} (A) = \{C: C \subset A\}\)

Базовые операции

Логические связки Операции над множествами
\(\land\) - Конъюнкция (И)
\(a\) \(b\) \(a \land b\)
1 1 1
1 0 0
0 1 0
0 0 0
  • \(a \land b \equiv \neg (\neg a \lor \neg b)\)
\(\cap\) - Пересечение
SVG не поддерживается браузером.
  • \(A \cap B = \{x: (x \in A) \land (x \in B)\}\)
  • \(A \cap B \equiv \overline{(\overline{A} \cup \overline{B})}\)
\(\lor\) - Дизъюнкция (ИЛИ)
\(a\) \(b\) \(a \lor b\)
1 1 1
1 0 1
0 1 1
0 0 0
  • \(a \lor b \equiv \neg (\neg a \land \neg b)\)
\(\cup\) - Объединение
SVG не поддерживается браузером.
  • \(A \cup B = \{x: (x \in A) \lor (x \in B)\}\)
  • \(A \cup B \equiv \overline{(\overline{A} \cap \overline{B})}\)
\(-\) - Разность
SVG не поддерживается браузером.
  • \(A - B = \{x: (x \in A) \land (x \notin B)\}\)
  • \(A - B \equiv A \cap \overline{B}\)
\(\neg\) - Отрицание (НЕ)
\(a\) \(\neg a\)
1 0
0 1
\(\overline{X}\) - Дополнение
SVG не поддерживается браузером.
  • \(\overline{A} = \{x: x \notin A\}\)
  • \(\overline{A} \equiv U - A \)
\(\underline{\vee}\) - Исключающее или
\(a\) \(b\) \(a \underline{\vee} b\)
1 1 0
1 0 1
0 1 1
0 0 0
  • \(a \underline{\vee} b \equiv (a \land \neg b) \lor (\neg a \land b)\)
\(\bigtriangleup\) - Симметрическая разность
SVG не поддерживается браузером.
  • \(A \bigtriangleup B = \{x: ((x \in A) \land (x \notin B)) \lor ((x \in B) \land (x \notin A))\}\)
  • \(A \bigtriangleup B \equiv (A - B) \cup (B - A) \equiv (A \cap \overline{B}) \cup (\overline{A} \cap B)\)
\(\rightarrow\) - Импликация (условная связка)
\(a\) \(b\) \(a \rightarrow b\)
1 1 1
1 0 0
0 1 1
0 0 1
  • \(a \rightarrow b \equiv \neg a \lor b\)
  • \(b \rightarrow a\) - конверсия высказывания \(a \rightarrow b\)
  • \(\neg a \rightarrow \neg b\) - инверсия высказывания \(a \rightarrow b\)
  • \(\neg b \rightarrow \neg a\) - контрапозиция высказывания \(a \rightarrow b\)
\(\leftrightarrow\) - Эквиваленция (логическая равнозначность)
\(a\) \(b\) \(a \leftrightarrow b\)
1 1 1
1 0 0
0 1 0
0 0 1
  • \(a \leftrightarrow b \equiv (a \rightarrow b) \land (b \rightarrow a)\)
\(\mid\) - штрих Шеффера (НЕ И)
\(a\) \(b\) \(a \mid b\)
1 1 0
1 0 1
0 1 1
0 0 1
  • \(a \mid b \equiv \neg (a \land b)\)
\(\downarrow\) - стрелка Пирса (НЕ ИЛИ)
\(a\) \(b\) \(a \downarrow b\)
1 1 0
1 0 0
0 1 0
0 0 1
  • \(a \downarrow b \equiv \neg (a \lor b)\)

Эквивалентности

Логика Множества
Законы идемпотентности
\(a \land a \equiv a\)
\(a \lor a \equiv a\)
\(A \cap A \equiv A\)
\(A \cup A \equiv A\)
Свойства коммутативности
\(a \land b \equiv b \land a\)
\(a \lor b \equiv b \lor a\)
\(A \cap B \equiv B \cap A\)
\(A \cup B \equiv B \cup A\)
\(A \bigtriangleup B \equiv B \bigtriangleup A\)
Свойства ассоциативности
\(a \land (b \land c) \equiv (a \land b) \land c\)
\(a \lor (b \lor c) \equiv (a \lor b) \lor c\)
\(A \cap (B \cap C) \equiv (A \cap B) \cap C\)
\(A \cup (B \cup C) \equiv (A \cup B) \cup C\)
\(A \bigtriangleup (B \bigtriangleup C) \equiv (A \bigtriangleup B) \bigtriangleup C\)
Законы тождества
\(a \land 1 \equiv a\)
\(a \land 0 \equiv 0\)
\(a \lor 1 \equiv 1\)
\(a \lor 0 \equiv a\)
\(A \cap U \equiv A\)
\(A \cap \varnothing \equiv \varnothing\)
\(A \cup U \equiv U\)
\(A \cup \varnothing \equiv A\)
Свойства дистрибутивности
\(a \land (b \lor c) \equiv (a \land b) \lor (a \land c)\)
\(a \lor (b \land c) \equiv (a \lor b) \land (a \lor c)\)
\(A \cap (B \cup C) \equiv (A \cap B) \cup (A \cap C)\)
\(A \cup (B \cap C) \equiv (A \cup B) \cap (A \cup C)\)
Законы дополнения/отрицания
\(a \land \neg a \equiv 0\)
\(a \lor \neg a \equiv 1\)
\(\neg 0 \equiv 1\)
\(\neg 1 \equiv 0\)
\(A \cap \overline{A} \equiv \varnothing\)
\(A \cup \overline{A} \equiv U\)
\(\overline{\varnothing} \equiv U\)
\(\overline{U} \equiv \varnothing\)
Законы двойного отрицания
\(\neg(\neg a) \equiv a\) \(\overline{\overline{A}} \equiv A\)
Законы де Моргана
\(\neg (a \land b) \equiv \neg a \lor \neg b\)
\(\neg (a \lor b) \equiv \neg a \land \neg b\)
\(\overline{(A \cap B)} \equiv \overline{A} \cup \overline{B}\)
\(\overline{(A \cup B)} \equiv \overline{A} \cap \overline{B}\)
Законы поглощения
\(a \lor (a \land b) \equiv a\)
\(a \land (a \lor b) \equiv a\)
\(A \cup (A \cap B) \equiv A\)
\(A \cap (A \cup B) \equiv A\)
Закон контрапозиции
\(a \rightarrow b \equiv \neg b \rightarrow \neg a\)
Другии свойства
\(a \rightarrow a \equiv 1\)

Умозаключения (аксиоматические системы), логика, доказательства

\( \begin{equation} \frac{ \begin{array}[b]{r} H_1\\ H_2\\ ...\\ H_n \end{array} }{ C } \end{equation} \)
Умозаключение является правильным, если \((H_1 \land H_2 \land ... \land H_n) \rightarrow C\) является тавтологией (истина при любых значениях).
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a \rightarrow b\\ a \end{array} }{ b } \end{equation} \)
Правило отделения (Modus Ponens)
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a \rightarrow b\\ b \rightarrow c \end{array} }{ a \rightarrow c } \end{equation} \)
Силлогизм
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a \rightarrow b\\ \neg b \end{array} }{ \neg a } \end{equation} \)
Modus Tollens
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a \end{array} }{ a \lor b } \end{equation} \)
Расширение
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a \land b \end{array} }{ a } \end{equation} \)
Специализация
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a\\ b \end{array} }{ a \land b } \end{equation} \)
Конъюнкция
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a\\ a \rightarrow (b \lor c)\\ b \rightarrow d\\ c \rightarrow d \end{array} }{ d } \end{equation} \)
Выбор
\( \begin{equation} \dfrac{ \begin{array}[b]{l} a \lor b\\ a \rightarrow (c \land \neg c) \end{array} }{ b } \end{equation} \)
Исключающий выбор
\( \begin{equation} \dfrac{ \begin{array}[b]{l} \neg a \rightarrow (b \land \neg b) \end{array} }{ a } \end{equation} \)
Сведение к абсурду (Reductio ad Absurdum). Доказательство от противного.
\((P(1) \land ((\forall k)P(k) \rightarrow P(k+1))) \rightarrow (\forall n)P(n)\)
Принцип математической индукции

Отношения / соответствия множеств

\(R : A \rightarrow B; aRb; (a, b) \in R; R \subseteq A \times B; b \in R(a)\) - отношение \(R\) множеств \(A\) и \(B\)
  • Бинарное отношение на \(A\) - если \(A = B\); \(R \subseteq A \times A\)
\(f: A \rightarrow B\) - Функция - Отношение \(f\) на \(A \times B\)
  • \(f: a \mapsto b\) - Однозначная функция (отображение): \(\forall (a \in A) \exists !(b \in B) ((a, b) \in f)\); \(b \in f\)
  • Частично определённая функция: \(\neg\forall (a \in A) \exists (b \in B) ((a, b) \in f)\)
  • \(f: A \rightrightarrows B\) - Многозначная функция: \(\neg(\forall (a \in A)) \exists (b \in B) ((a, b) \in f)\)
\(Dom F = F^{-1}(B)\) - Область определения
\(Dom F = \{a: a \in A \land (a, b) \in F\}\)
\(B\) - Область потенциальных значений для \(f: A \rightarrow B\)
\(Ran F = F(A)\) - Область значений
\(Ran F = \{b: b \in B \land (a, b) \in F\}\)
Инъекция
Если \(A\) - Область определения, \(\forall (a \in A) (f(a) = f(a') \rightarrow a = a')\)
Сюръекция
\(\forall (b \in B) \exists (a \in A) (f(a) = b)\)
  • \(F: A \rightarrow B\) - Сюръекция, если \(Ran F = F(A) = B\)
Биекция - Взаимно однозначное соответствие
Однозначная функция, которая является одновременно и инъективной, и сюръективной.
\(R^{-1} = \{(b, a): (a, b) \in R\}\) - Обратное отношение
Образ множества \(S\)
Если \(F : A \rightarrow B\) и \(S \subseteq A\), то образ множества \(S\) будет \(F(S) = \bigcup_{\substack{s \in S}} F(s) \subseteq B\)
  • для однозначных функций: \(S\) будет \(F(S) = \{F(s): s \in S\}\)
Прообраз множества \(T\)
Если \(F : A \rightarrow B\) и \(T \subseteq B\), то прообраз множества \(T\) будет \(F^{-1}(T) = \{a: F(a) \cap T \not = \varnothing \} \subseteq A\)
  • для однозначных функций: \(F^{-1}(T) = \{a: F(a) \in T \}\)
\(F|_S : S \rightarrow B\) сужение соответствия \(F\) на \(S\), если \(F : A \rightarrow B\) и \(S \subset A\)
\(\forall (a \in S) (b \in F|_S(a) \leftrightarrow b \in F(a))\)
  • \(F : A \rightarrow B\) - частично определённая функция, если \(F|_{Dom F}\) - однозначная функция
\(T = S \circ R\) - Композиция
\(T = \{(a, c): \exists (b \in B)((a, b) \in R \land (b, c) \in S)\}\), где \(R \subseteq A \times B\) и \(S \subseteq B \times C\)
  • \(G \circ F : X \rightarrow Z\):
    • \(F : X \rightarrow Y\), \(G : Y \rightarrow Z\), \(F(x) \subset Y\)
    • \((G \circ F)(x) = G(F(x))\), \(x \in X\)
  • Композиция ассоциативна: \((H \circ G) \circ F = H \circ (G \circ F)\)
  • \((G \circ F)^{-1} = F^{-1} \circ G^{-1}\):
\(id_A : A \rightarrow A\) - Тождественное отображение
\(id_A(x) = x\)
  • \(F \circ id_A = F\)
  • \(id_B \circ F = F\)
  • \(F^{-1} \circ F = id_A\) - только для инъективного, непустозначного соответствия
  • \(F^{-1} \circ F = id_A\) и \(F \circ F^{-1} = id_B\) - только для биекций
\(F^n\) - Возведение отношения \(F : A \rightarrow A\) в степень
\(F^0 = id_A\); \(F^{n+1} = F \circ F^n\)
  • \(F^n \circ F^k = F^{n+k}\)
  • \((F^n)^k = F^{nk}\)
\(B^A\) - множество всех отношений из \(A\) в \(B\)
  • \((A \times B)^C \sim A^C \times B^C \)
  • \(A^{B \cup C} \sim A^B \times A^C \) - если \(B\) и \(C\) не пересекаются
  • \((A^B)^C \sim A^{B \times C}\)
  • Для любого \(A\): \(A^{\varnothing} = \{\varnothing\}\)
  • Для непустого \(A\): \(\varnothing^A = \varnothing\)
\(\sim\) - "элементы множеств могут быть естественным образом отождествлены"
Перестановка множества \(A\)
Если \(A = B\) и \(f: A \rightarrow B\) является биекцией.
Рефлексивное бинарное отношение - \(\forall(a \in A)aRa\)
\(\{(1, 1), (2, 2), (3, 3), ...\}\)
Антирефлексивное отношение - \(\forall((a, b) \in R) \rightarrow a \neq b\)
Рефлексивное замыкание \(R^*\) - наименьшее рефлексивное отношение на \(A\), \(R \subset R^*\)
\(R^* = R \cup I, I = \{x: x=(a, a), a \in A\}\)
Симметричное бинарное отношение - \(\forall(a \in A)\forall(b \in A)((a, b) \in R \rightarrow (b, a) \in R)\)
\(\{(1, 2), (2, 1), (2, 3), (3, 2), ...\}\)
Антисимметричное отношение - \(\forall(a \in A)\forall(b \in A)((a, b) \in R \land (b, a) \in R \rightarrow a = b)\)
Симметричное замыкание \(R^*\) - наименьшее рефлексивное отношение на \(A\), \(R \subset R^*\)
\(R^* = R \cup R^{-1}\)
Тразитивное бинарное отношение - \(\forall(a \in A)\forall(b \in A)\forall(с \in A)((a, b) \in R \land (b, с) \in R \rightarrow (a, с) \in R)\)
\(\{(1, 2), (2, 3), (1, 3), ...\}\)
Тразитивное замыкание \(R^*\) - наименьшее рефлексивное отношение на \(A\), \(R \subset R^*\)
\(R^* = R \cup R^{2} \cup R^{3} \cup ... \cup R^{n}, n = |A|\)
Отношение эквивалентности - рефлексивное, симметричное и транзитивное отношение.
Класс эквивалентности \(E_a = [a], a \in A\). \([a] = \{x: xRa\} = \{x: (x, a) \in R\}\)
\([A]_R\) - Множество всех классов эквивалентности множества \(А\) по отношению \(R\).
Разбиение множества - \(\langle A \rangle = \{A_i: i \in I\}\).
\(A\) - множество, \(I\) - множество не пустых подмножеств
Условие:
  • \(A_i \cap A_j = \varnothing, i \neq j\)
  • \(A = \bigcup_{\substack{i \in I}} A_i\)
Множество всех классов эквивалентности множества \(А\) по отношению \(R\) - \([A]_R\) - образует разбиение \(А\)
Отношение частичного порядка - \(\leq\) - рефлексивное, aнтисимметричное и транзитивное отношение.
Частично упорядоченные множества - \((A, R)\) или \((A, \preceq)\)
Если отношение \(R\) на \(A\) является отношением частичного порядка.
Два элемента \(a\) и \(b\) частично упорядоченного множества \((S, \preceq)\) сравнимы, если \(а \prec b\) или \(b \prec а\).
Линейный порядок: Если каждые два элемента частично упорядоченного множества \((S, \preceq)\) сравнимы, то \((S, \preceq)\) называется вполне упорядоченным множеством, или цепью.
Предшественник: если \(R\) является отношением частичного порядка \((xRy)\), то \(x\) называется предшественник.
Непосредственный предшественник - если \(R\) является отношением частичного порядка \((xRy)\), и \(x\) является предшественником, и \(\neg(\exists z)((x, z) \in R \land (z, y) \in R)\).
  • TODO:
    • Свойства, бинарные отношения, предикаты валентности
    • Характеристики бинарных отношений: рефлексивность, симметричность, транзитивность, полнота, трихотомические, замыкания относительно булеана
    • Отношения эквивалентности
    • Частичный порядок, операции над упорядоченными множествами, экстримальные точки упорядоченных множеств
    • Плотный порядок
    • Предпорядок
    • Терминалогии отношений, соответствий, отображений
    • Переработать с подразделами

Мощность множеств. Счетность.

\(|\varnothing| = 0\)
Пустое множество есть конечное множество мощности 0.
\(|A| = n\) - \(n\) является мощностью конечного множества \(A\) (Число элементов множества)
если существует Биекция \(\forall (a \in A) (f: A \rightarrow \{1, 2, 3, \dots n\})\). Такое множество является счетным.
  • \(|A \times B| = |A| \cdot |B|\)
  • \(|A \cup B| = |A| + |B| - |A \cap B|\)
Счетно бесконечное множество \(A\)
если существует Биекция \(\forall (a \in A) (f: A \rightarrow \mathbb{N})\);
или если \(A \cong \mathbb{N}\)
Множество называется счетным, если оно конечно или счетно бесконечно.
  • Если \(A\) и \(B\) - непересекающиеся счетные множества, то \( A \cup B\) - счетное множество.
  • Если \(A\) и \(B\) - непересекающиеся счетно бесконечные множества, то \( A \cup B\) - счетное бесконечное множество.
  • Если \(A\) — счетно, то \(B \subseteq A\) — счетно или конечно
  • Если \(A\) — счетно, а \(B\) - конечно, то \(A \cup B\) — счетно
  • Если \(S\) — счетно бесконечно, то \(S \cdot S\) — счетно бесконечно
  • \(\mathbb{Z}, \mathbb{Q}\) — счетно бесконечны
  • \(\mathbb{R}\) — НЕ счетно
  • Не существует взаимно однозначного соответствия между множеством \(S\) и его булеаном \(\mathcal{P} (S)\).
  • Если \(A\) — счетно, то \(2^A\) — несчетно
\(|A| = |B| \leftrightarrow A, B\) - Равномощные множества \(A \cong B\)
Множества равномощны - если сущестувет биекция \(\forall (a \in A) (f: A \rightarrow B)\)
  • Рефлексивность \(A \cong A\)
  • Симметричность \(A \cong B \rightarrow B \cong A\)
  • Транзитивность \((A \cong B) \land (B \cong C) \rightarrow A \cong C\)
  • \(|A| > |B| \leftrightarrow (A \not \cong B)\ \land \exists(C \subset A)(C \cong B)\)
  • \(|A| < |B| \leftrightarrow (A \not \cong B)\ \land \exists(C \subset B)(C \cong A)\)
  • Теорема Кантора — Бернштейна:
    • \((|A| > |B|) \land (|A| < |B|) \rightarrow A \cong B\)
    • \((A \cong B' \subset B) \land (B \cong A' \subset A) \rightarrow A \cong B\)
  • Если \(A\) — бесконечно, а \(B\) - счетно, то \(A \cup B \cong A\)
Несчетное множество – бесконечное множество, мощность которого больше, чем мощность счетного множества.
\((|A| > |B|) \land (B \cong \mathbb{N}) \rightarrow A\) - Несчетное множество
Диагональный метод Кантора - доказывающий несчетность множества из всех бесконечных последовательности из нулей и единиц
Континуальное множество – бесконечное множество, равномощное \(2^{\mathbb{N}}\).
  • \(\mathbb{R}\) — континуальное множество
  • Если \(A\) — конечно или счетно, то \(\mathbb{R}^A\) — континуально

Абстрактная вычислительная машина

Машина Тьюринга - \((\Sigma, \Gamma, Q, q_1, q_0, \delta)\)
Состоит из:
  • Бесконечная лента с ячейками.
  • Управляющий блок с конечным числом внутренних состоянией, указывающий на текущую ячейку ленты.
  • В зависиомости от текущего состояния и текущего значения в ячейке, машина переходит в новое состояние, может изменить значение в ячейке, и сдвигается по ленте направо, налево или остается на месте.
  • Если машина перешла в завершающее состояние, то процесс останавливается.
Формально: \((\Sigma, \Gamma, Q, q_1, q_0, \delta)\)
  • \(\Sigma\) - входной алфавит, конечное множество, к примеру: \(\Sigma = \{0, 1\}\)
  • \(\Gamma = \Sigma \cup S\) - ленточный алфавит, \(S\) - служебный алфавит, к примеру: \(\Gamma = \{0, 1, \#\}\)
  • \(Q\) - конечное множество внутренних состояний \(Q \cap \Gamma = \varnothing\), к примеру: \(Q = \{q_1, q_2, q_3, q_0\}\)
  • \(q_1 \in Q\) - начальное состояние
  • \(q_0 \in Q\) - конечное состояние
  • \(\delta: (Q - \{q_0\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L, R, N\} \) - функция перехода/программа; \(L\) - сдвиг налево; \(R\) - сдвиг направо; \(N\) - остается на месте;
    • \(q_i a_j \rightarrow q_k a_l \begin{pmatrix} L\\ R\\ N \end{pmatrix} \)
Конфигурация: \(AqaB\)
  • \(q \in Q\) - текущее состояние
  • \(a \in \Gamma\) - текущий элемент в ленте
  • \(A,B \in \Gamma^*\) - конечниые слова в ленте слева и справа до значащегося символа \(\#\)
Начальная конфигурация - \(q_1X\)
  • \(q_1\) - начальное состояние
  • \(X\) - входные данные
  • Вычисление на входе \(X\) - это конечная или бесконечная последовательность конфигураций, такая что каждая следующая конфигурация получается из предыдущий, согласно программе некоторой фиксированной машины Тьюринга.
Завершающее состояние - \(q_0\)
  • Если вычисление заканчивается конфигурацией с состоянием \(q_0\) - ответом может считаться слово, которое начинается от ячейки на которую указывает машина, до ближайшего \(\#\) (не включительно)
  • Если вычисление бесконечно, то у машины нет ответа.
Вычисление конфигурации, по функции перехода, пример:
  • функции перехода - \(qa \rightarrow rbL\)
  • текущая конфигурация: \(AqaB\)
  • текущую конфигурацию можно представить как: \(AqaB = A'xqaB; A'x = A' \cup \{x\} = A\)
  • переход/смена конфигурации, если \(A\) не пусто: \(A'xqaB \mapsto A'rxbB\)
  • переход/смена конфигурации, если \(A\) пусто (\(\#\)): \(qaB \mapsto r\#bB\)
\(f\) вычислима, если существует машина Тьюринга \(M\), такая что при всех \(X\)
  • если \(f(X)\) определена, то машина \(M\) начав из конфигурации \(q_1X\), остановится с конфигурацией \(q_0\) с ответом \(f(X)\)
  • если \(f(X)\) не определена, то машина \(M\) начав из конфигурации \(q_1X\), не останавливается
Существуют невычислимые функции:
  • Любая машина Тьюринга имеет конечное описание, поскольку описание состоит из конечных множеств.
  • Множество всех машин Тьюринга счетно.
  • Разных машинт Тьюринга - счетное число
  • Каждая машина Тьюринга вычисляет одну функцию.
  • Вычислимых функций - счетное число.
  • Всех функций - несчетное число. (даже существует несчетно число функций которые отображают множество натуральных чисел в последовательность из 0 и 1)
Тезис Чёрча-Тьюринга
  • Любую вычислимую функцию, на реальном вычислительном устроистве, можно вычислить на машине Тьюринга.
Универсальная Машина Тьюринга - \(U\) (Универсальная вычислимая функция)
  • \(U: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\)
  • \(U(p, x)\) - результат работы Машина Тьюринга с программой \(p\), на входе \(x\)
  • Свойство универсальности без привязки к коду \(p\) (способу кодирования): $$\forall f_{\text{вычислимой}} \exists p \forall x f(x) = U(p, x)$$

Вычислимость, разрешимость, перечислимость

Вычислимая функция.
  • \(f\) вычислима, если существует машина Тьюринга \(M\), такая что
    • если \(f(x)\) определено, то \(M\) на входе \(X\) останавливается и возвращает \(f(x)\).
    • если \(f(x)\) не определено, то \(M\) на входе \(X\) не остановится.
  • Если \(f: \mathbb{N} \rightarrow \mathbb{N}\) и \(g: \mathbb{N} \rightarrow \mathbb{N}\) вычислимы, то \(g \circ f\) вычислима.
  • Если \(f: \mathbb{N} \rightarrow \mathbb{N}\), \(g: \mathbb{N} \rightarrow \mathbb{N}\), \(h: \mathbb{N} \rightarrow \mathbb{N}\) вычислимы, то \(f(g(n), h(n))\) вычислима.
  • Любая композиция вычислимых функций, будет вычислимой функцией.
  • Любая функция с конечной областью определения вычислима.
  • Функция \(f\) с натуральными аргументами и значениями вычислима тогда и только тогда, когда её график \(F = \{\langle x, y \rangle | f(x) \text{ определено и равно }y\}\) является перечислимым множеством пар натуральных чисел.
  • Прообраз и образ перечислимого множества при вычислимой функции перечислимы
Разрешимые множества
  • Пусть \(A \subseteq \mathbb{N}\). Тогда \(A\) разрешимo, если существует алгоритм \(M\), такой что,
    • если \(x \in A\), то \(M(x) = 1\),
    • если \(x \notin A\), то \(M(x) = 0\).
    Иначе говоря, вычислима характеричтияеская функция \(\mathcal{X}_A(x) = \begin{cases} 1, x \in A\\ 0, x \notin A \\ \end{cases}\)
  • Существуют не разрешимые множества.
    • Всего множеств - несчетное число
    • Разрешимых множеств счетно.
  • Если \(A\) и \(B\) - разрешимы, то разрешимы:
    • \(A \cup B\); \(\mathcal{X}_{A \cup B}(x) = \mathcal{X}_{A}(x) \lor \mathcal{X}_{B}(x)\)
    • \(A \cap B\); \(\mathcal{X}_{A \cup B}(x) = \mathcal{X}_{A}(x) \land \mathcal{X}_{B}(x)\)
    • \(\overline{A}\); \(\mathcal{X}_{\overline{A}}(x) = 1 - \mathcal{X}_{A}(x)\)
  • Любое конечное множество разрешимо
    • Любое дополнение к конечному множеству разрешимо (коконечное множество)
  • Подмножество разрешимого множества, не обязательно будет разрешимо.
Перечислимые множества
  • Перечиcлитель - машина Тьюринга с дополнительной лентой, только для записи, и соответственно специальные состояни: "записать 0", "записать 1", "записать #". На ленте для записи не может возникнуть бесконечная последовательность 0 и 1.
    Любая \(x \in \mathbb{N}\) либо появится на ленте, либо не появится.
    Машина перечисляет множество всех слов, которые появятся.
  • Множество перечислимо - если оно перечисляется какойто машиной - перечислителем.
  • Множество \(A\) перечислимо, тогда и только тогда, когда вычислима полухарактеристическая функция \(\overline{\mathcal{X}}_A(x) = \begin{cases} 1, x \in A\\ \text{не определена}, x \notin A \\ \end{cases}\)
    • Программа вычисляющая \(\overline{\mathcal{X}}_A(x)\): Запустим перечислитель, будем читать его выход и ждать \(x\). Если совпало - вернем 1.
    • "Параллельный запуск" \(\overline{\mathcal{X}}_A(x)\) на всех входах.
      Для \(k=0,1,2,...\) запустить вычислитель \(\overline{\mathcal{X}}_A(0), ..., \overline{\mathcal{X}}_A(k)\)
      Печатаем те \(i\), для которых \(\overline{\mathcal{X}}_A(i)\) завершилось.
  • \(A\) - перечислимо, тогда и только тогда, когда \(A\) область определения вычислимой функции.
  • \(A\) - перечислимо, тогда и только тогда, когда \(A\) область значений вычислимой функции.
  • Если \(A\) - разрешимо, то \(A\) перечислимо.
  • \(A\) - перечислимо, тогда и только тогда, когда \(A\) пусто, или является областью значений всюду определенной вычислимой функции.
  • \(A\) - перечислимо, тогда и только тогда, когда \(A = \{x: \exists(x, y) \in B\}\), для некоторого разрешимого \(B \subseteq \mathbb{N}^2\)
  • Если \(A\) и \(B\) - перечислимо, то \(A \cup B\) и \(A \cap B\) перечислимы
  • Если \(A\) и \(B\) - перечислимо, то \(A \times B\) перечислимы (при \(A \subset \mathbb{N}, B \subset \mathbb{N}, A \times B \subset \mathbb{N} \times \mathbb{N}\))
  • Любое перечислимое множество можно алгоритмически перечислить без повторений, но не любое перечислимое множество можно алгоритмически перечислить в определенном порядке (по возрастанию или убыванию)
  • Подмножество перечислимого множества, не обязательно будет перечислимо.
Теорема Поста
\(A\) - разрешимо, тогда и только тогда, когда \(A\) и \(\overline{A}\) перечислимо
Проблема самоприменимости
Остановится ли программа \(p\), на входе \(p\)
  • \(S = \{p: U(p,p) \text{ определена}\}\)
  • \(S\) - перечислимое, но не разрешимое множество
Проблема остановки
Остановится ли программа \(p\), на входе \(x\)
  • \(H = \{(p, x): U(p,x) \text{ определена}\}\)
  • \(H\) - перечислимое, но не разрешимое множество
Проблема остановки в 0
Проблема остановки в 0 перечислима, но не разрешима
Теорема Райса-Успенского
  • Пусть \(\mathscr{A}\) - нетривиальное свойство вычислимых функций
  • \(\mathscr{A} \not = \varnothing\) и \(\overline{\mathscr{A}} \not = \varnothing\)
  • тогда множество Машин Тьюринга, вычисляющих функции, обладающих свойством \(\mathscr{A}\) - неразрешимо.
  • (Нельзя определить - обладает ли программа свойством \(\mathscr{A}\) или нет)
Тотально вычислимая функция
  • Вычислимая функция, которая всюду определена
Тотальная универсальная вычислимая функция
  • \(U: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\)
    • \(U\) - Тотально вычислимая функция
    • \(\forall f_{\text{тотально вычислимая функция}} \exists p \forall x f(x) = U(p,x)\)
  • Тотально универсальных вычислимых функций не существует
\(m\)-сводимость
  • \(f: \mathbb{N} \rightarrow \mathbb{N}\) - тотально вычислима
    \(x \in A \leftrightarrow f(x) \in B\)
    \(A \leq_m B: A \: m-\text{сводится к } B\)
  • \(A \leq_m B \land B \leq_m C \rightarrow A \leq_m C\) (Транзитивность)
  • \(A \leq_m B \land B \text{-разрешимо} \rightarrow A \text{-разрешимо}\)
    • \(A \leq_m B \land B \text{-неразрешимо} \rightarrow A \text{-неразрешимо}\)
  • \(A \leq_m B \land A \text{-перечислимо} \rightarrow B \text{-перечислимо}\)
    • \(A \leq_m B \land A \text{-неперечислимо} \rightarrow B \text{-неперечислимо}\)
  • \(A \leq_m B \leftrightarrow \overline{A} \leq_m \overline{B}\)
  • \(A \text{-неперечислимо} \land A \leq_m B \land A \leq_m \overline{B} \rightarrow B \text{-неперечислимо} \land \overline{B} \text{-неперечислимо}\)
  • \(A \text{-неразрешимо} \land A \leq_m B \land A \leq_m \overline{B} \rightarrow B \text{-неперечислимо} \land \overline{B} \text{-неперечислимо}\)
\(\{p: \forall x U(p,x) \text{ определено}\} - \text{неперечислимо и некоперечислимо}\)

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

Правило сложения (Комбинаторный принцип сложения)
Кол-во вариантов выбора 1го элемента из объединения множеств \(\bigcup_{\substack{i = 1}}^m S_i\)
  • Для попарно непересекающихся множеств:
    \(|S_1 \cup S_2 \cup S_3 \cup \dots \cup S_m| = |S_1| + |S_2| + |S_3| + \dots + |S_m|, \forall (i \not = j) (S_i \cap S_j = \varnothing)\)
  • Для произвольных множеств - Формула включений-исключений
    \(\biggl | \bigcup_{i=1}^{m}A_i \biggl | = \sum_{i} | A_i | - \sum_{i<j} | A_i \cap A_j | + \sum_{i<j<k} | A_i \cap A_j \cap A_k | - \ldots + (-1)^{m-1} | A_1 \cap A_2 \cap \ldots \cap A_m |\)
    \(| A \cup B | = | A | + | B | - | A \cap B |\)
    \(| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C|\)
Правило умножения (Комбинаторный принцип умножения)
\(|S_1 \times S_2 \times S_3 \times \dots \times S_m| = |S_1| \times |S_2| \times |S_3| \times \dots \times |S_m|\)
Кол-во вариантов выбора по 1му элементу из каждого множества
Принцип Дирихле Вики
  • При любом распределении \(nk+1\) или более предметов по \(n\) ящикам в каком-нибудь ящике окажется не менее чем \(k+1\) предмет.
  • Если \(m\) кроликов рассажены в \(n\) клеток, то хотя бы в одной клетке находится не менее \(\left\lceil {\frac {m}{n}}\right\rceil\) кроликов, а также хотя бы в одной клетке находится не более \(\left\lfloor {\frac {m}{n}}\right\rfloor\) кроликов.
  • Пусть задана функция \(f : A \rightarrow B\) на конечных множествах \(A\) и \(B\), причём \(|A|>n|B|\), где \(n \in \mathbb {N}\). Тогда некоторое своё значение функция \(f\) примет по крайней мере \(n+1\) раз.
  • Обобщение данного принципа на случай бесконечных множеств: не существует инъекции более мощного множества в менее мощное.
Основные комбинаторные величины
  • Пусть \(A = \{a_1, a_2, \dots, a_n\}\)
    1. \(A_n^k\) - \(k\)-размещение без повторения \((1 \leq k \leq n)\) (порядок важен). (\(A\) из \(n\) по \(k\))
      • \(A_n^k = n \times (n-1) \times \dots \times (n - k + 1) = \frac{n!}{(n-k)!}\)
      • \(A_n^n = n!\) - число перестановок
    2. \(\bar{A}_n^k\) - \(k\)-размещение с повторениями (порядок важен).
      • \(\bar{A}_n^k = n^k\)
    3. \(C_n^k = \binom{n}{k}\) - \(k\)-сочетание без повторения \((1 \leq k \leq n)\) (порядок не важен). (\(C\) из \(n\) по \(k\))
      • \(C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}\)
    4. \(\bar{C}_n^k\) - \(k\)-сочетание с повторениями (порядок не важен).
      • \(\bar{C}_n^k = C_{n+k-1}^k\)
\(C_n^k\) - Биномиальный коэффициент
  • Бином Ньютона $$(x+y)^n = C_n^0x^ny^0 + C_n^1x^{n-1}y^1 + C_n^2x^{n-2}y^2 + \dots + C_n^{n-1}x^1y^{n-1} + C_n^nx^0y^n$$ $$(x+y)^n = \displaystyle\sum_{k=0}^{n} C_n^kx^ky^{n-k}$$
  • Тождества:
    • \(C_n^k = C_n^{n-k}\)
    • \(C_n^k = C_{n-1}^{k} + C_{n-1}^{k-1}\)
    • \(\displaystyle\sum_{k=0}^{n} C_n^k = 2^n\)
    • \(\displaystyle\sum_{k = 0}^{n/2} C_n^{2k} = 2^{n-1}\)
    • \(\displaystyle\sum_{k=0}^{n} (C_n^k)^2 = C_{2n}^n\)
    • \(\displaystyle\sum_{k=0}^{m} C_{n+m-1-k}^{n-1} = C_{n+m}^n\)
      • \(n = 1\): \(C_{m+1}^1 = m + 1\)
      • \(n = 2\): \(C_{m+2}^2 = \displaystyle\sum_{k=1}^{m+1} k = \frac{(m+1)(m+2)}{2}\)
      • \(n = 3\): \(\displaystyle\sum_{k=1}^{m} k^2 = \frac{m(m+1)(2m+1)}{6}\)
      • \(n = 4\): \(\displaystyle\sum_{k=1}^{m} k^3 = \dots \)
    • \(C_n^0 - C_n^1 + C_n^2 - C_n^3 + \dots + (-1)^nC_n^n = \displaystyle\sum_{k=0}^{n} (-1)^kC_n^k = \begin{cases} 1, n = 0 \\ 0, n > 0 \end{cases} \)
\(P(n_1, n_2, \dots, n_k)\) - Полиномиальные коэффициенты
  • \(P(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! n_2! \dots n_k!}\)
    • \(P(n_1, n_2, \dots, n_k)\) - кол-во способов составить последовательность из \(n\) объектов
    • \(n - \text{ кол-во объектов }\)
    • \(n_1 - \text{ кол-во объектов первого типа}\)
    • \(n_2 - \text{ кол-во объектов второго типа}\)
    • \(\dots\)
    • \(n_k - \text{ кол-во объектов } k\text{ -типа}\)
    • \(n = n_1 + n_2 + \dots + n_k\)
  • Доказательство:
    $$P(n_1, n_2, \dots, n_k) = C_n^{n_1} \cdot C_{n-n_1}^{n_2} \cdot C_{n-n_1-n_2}^{n_3} \cdot \dots \cdot C_{n-n_1-\dots-n_{k-1}}^{n_k}$$ $$C_{\underbrace{n-n_1-\dots-n_{k-1}}_{n_k}}^{n_k} = C_{n_k}^{n_k} = 1$$ $$P(n_1, n_2, \dots, n_k) = C_n^{n_1} \cdot C_{n-n_1}^{n_2} \cdot C_{n-n_1-n_2}^{n_3} \cdot \dots \cdot C_{n_k}^{n_k}$$ $$\require{cancel} P(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! \cancel{(n-n_1)!}} \cdot \frac{\cancel{(n-n_1)!}}{n_2! \cancel{(n-n_1-n_2)!}} \cdot \frac{\cancel{(n-n_1-n_2)!}}{n_3! \cancel{(n-n_1-n_2-n_3)!}} \cdot \dots \cdot \frac{\cancel{(n-n_1-\dots-n_{k-1})!}}{n_k! 0}$$ $$P(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! n_2! \dots n_k!}$$
  • \(P(k, n-k) = \frac{n!}{k!(n-k)!} = C_n^k\)
  • Полиномиальная формула $$(x_1 + x_2 + \dots + x_k)^n = \displaystyle\sum_{\substack{(n_1, \dots, n_k) \\ \forall i \; n_i \geq 0 \\ n_1 + \dots + n_k = n}} P(n_1, n_2, \dots, n_k) \cdot x_1^{n_1} \cdot x_2^{n_2} \cdot x_3^{n_3} \cdot \dots \cdot x_k^{n_k} $$
  • Тождества
    • $$\displaystyle\sum_{\substack{(n_1, \dots, n_k) \\ \forall i \; n_i \geq 0 \\ n_1 + \dots + n_k = n}} P(n_1, n_2, \dots, n_k) = k^n$$
Формула включений и исключений
  • В терминах множеств: $$\biggl | \bigcup_{i=1}^{n}A_i \biggl | = \sum_{i} | A_i | - \sum_{i<j} | A_i \cap A_j | + \sum_{i<j<k} | A_i \cap A_j \cap A_k | - \ldots + (-1)^{n-1} | A_1 \cap A_2 \cap \ldots \cap A_n |.$$
    • \(A_1, A_2, \ldots, A_n\) - конечные множества
  • В терминах свойств: $$N(\overline{a}_1 \ldots \overline{a}_n) = N - \sum_{i} N(a_i) + \sum_{i< j} N(a_i a_j) - \sum_{i< j<k} N(a_i a_j a_k) + \ldots + (-1)^n N(a_1 \ldots a_n).$$
    • \(N\) - количество/мощность множества \(U\)
    • \(a_1, \ldots , a_n\) - набор возможных свойств элементов множества \(U\)
    • \(N(a_{i_1} \ldots a_{i_s})\) - кол-во элементов множества \(U\), обладающих свойствами \(a_{i_1} \ldots a_{i_s}\)
    • \(N(\overline{a}_{i_1} \ldots \overline{a}_{i_s})\) - кол-во элементов множества \(U\), не обладающих свойствами \(a_{i_1} \ldots a_{i_s}\)
Выравнивание последовательностей
  • \(\begin{pmatrix} \varnothing & a & b & c & d \\ d & a & b & \varnothing & \varnothing \end{pmatrix}\)
  • Условия:
    • Ни в каком выравнивании не возникает ситуация, когда gap стоит над gap’ом: \(\begin{pmatrix}\cdots & \varnothing & \cdots \\ \cdots & \varnothing & \cdots \end{pmatrix}\)
    • Выравнивания вида \(\begin{pmatrix}\cdots & a & \varnothing & \cdots \\ \cdots & \varnothing & b & \cdots \end{pmatrix}\), \(\begin{pmatrix}\cdots & \varnothing & a & \cdots \\ \cdots & b & \varnothing & \cdots \end{pmatrix}\) - отождествляются
  • \(g(n,m)\) - количество всех возможных выравниваний последовательностей \(a_1 \dots a_n\) и \(b_1 \dots b_m\), удовлетворяющих условиям
    • \(g(n,m) = g(n-1,m) + g(n,m-1)\)
    • \(g(n,m) = C_{n+m}^n\)
Формула обращения Мёбиуса
  • Основная теорема арифметики
    • Пусть \(n \in \mathbb{N}\), \(n \geqslant 2\). Тогда существует и единственен такой набор простых чисел \(p_1 < p_2 < \ldots < p_s\) и натуральных чисел \(\alpha_1,\ldots,\alpha_s \geqslant 1\), что \(n=p_1^{\alpha_1}\cdot\ldots \cdot p_s^{\alpha_s}\).
  • Функция Мёбиуса
    • \( \mu(n) = \begin{cases} 1, &\text{если } n=1 ;\\ (-1)^s, &\text{если } n = p_1\cdot\ldots\cdot p_s (\text{т.е.} n = p_1^{\alpha_1}\cdot\ldots\cdot p_s^{\alpha_s} \text{ и } \forall i \quad \alpha_i=1); \\ 0,&\text{иначе } (\text{т.е. } n = p_1^{\alpha_1}\cdot\ldots\cdot p_s^{\alpha_s} \text{ и } \exists i: \alpha_i \geq 2). \end{cases} \)
  • Сумма по делителям числа
    • Используя символ "\(\mid\)" делимости, будем рассматривать суммы по всем делителям \(\sum\limits_{d\mid n}f(d)\).
    • Пример: \(\sum\limits_{d \mid 12} \mu(d) = \mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(6)+\mu(12) = 1 -1-1+0+1+0=0.\)
    • \(\sum\limits_{d \mid n}\mu(d) =\begin{cases} 1, n=1;\\ 0, n \geqslant 2.\end{cases}\)
  • Формула обращения Мёбиуса
    • Пусть \(g : \mathbb{N}\rightarrow \mathbb{N}\) - произвольная функция. Положим \(f(n)=\sum\limits_{d \mid n}g(d)\). Тогда \(g(n) = \sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right) = \sum_{d \mid n} \mu\left(\frac{n}{d}\right) f(d)\).
    • Доказательство: $$ \sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right) = \sum_{d \mid n} \mu(d) \sum_{d' \mid \frac{n}{d}} g(d') = \sum_{d \mid n, \ d' \mid \frac{n}{d}} \mu(d) g(d') = $$ $$ =\sum_{(d,d'): \ dd' \mid n} \mu(d) g(d') = \sum_{(d,d'): \ dd' \mid n} \mu(d') g(d) = \sum_{d \mid n} g(d) \left(\sum_{d' \mid \frac{n}{d}} \mu(d')\right) = $$ $$ = g(n) \cdot 1 + \sum_{d \mid n, \ d<n} g(d) \left(\sum_{d' \mid \frac{n}{d}} \mu(d')\right) = g(n) \cdot 1 + 0 = g(n). $$
Циклические последовательности
  • \(X = \{b_1,\dots,b_r\}\) - алфавит.
  • \(a_1,\ldots,a_n\) - Линейная последовательность
    • \(V\) - множество всех линейных последовательностей
    • \(|V| = \bar{A}_r^n = r^n\) - Различных слов длины \(n\) над алфавитом \(X\)
  • \((a_1,\ldots,a_n)\) - Циклическая последовательность
    • Циклическая последовательность слова длины \(n\) над алфавитом \(X\): \(a_1 \to a_2 \to a_3 \to \ldots \to a_n\), после этого, добавим \(a_n \to a_1\)
    • \(T_r(n)\) - количество различных циклических последовательностей длины \(n\) над алфавитом \(X\)
  • Циклический сдвиг - операция, которая переводит линейную последовательность \(a_1,a_2,\ldots,a_n \in V\) в \(a_2,a_3,\ldots,a_n,a_1\)
    Пример:
    • COCO \(\to\) ОСОС \(\to\) СОСО \(\to\) ОСОС
    • COCH \(\to\) ОСHС \(\to\) СHСО \(\to\) HСОС
  • Период последовательности - минимальное число \(d \geq 1\) циклических сдвигов, в результате которых, линейная последовательность, перейдет в себя.
    Пример:
    • COCO \(\to\) ОСОС \(\to\) СОСО - Период равен 2
    • COCH \(\to\) ОСHС \(\to\) СHСО \(\to\) HСОС \(\to\) COCH - Период равен 4
  • Лемма: Период любой последовательности делит ее длину без остатка: \(d\mid n\)
  • Лемма: Если линейная последовательность длины \(n\) имеет период \(d\), то она выглядит так: \(a_1\ldots a_d a_1 \ldots a_d \ldots a_1 \ldots a_d\) (количество "блоков" равно \(\frac{n}{d}\)).
    Из леммы следует наличие биекции между множеством линейных последовательностей длины \(n\) и периода \(d\) и множеством линейных последовательностей длины \(d\) и периода \(d\).
  • Формула для линейных последовательностей:
    • \(d_1, d_2, \ldots, d_s\) - все делители числа \(n\) - количество элементов последовательности
    • \(V = V(d_1) \sqcup V(d_2) \sqcup \ldots \sqcup V(d_s)\). \(V(d_i)\) - множество всех линейных последовательностей длины \(n\) периода \(d_i\).
    • \(r^n = |V| = |V(d_1)| + |V(d_2)| + \ldots + |V(d_s)| = |W(d_1)| + |W(d_2)| + \ldots + |W(d_s)|\). \(W(d_i)\) - множество всех линейных последовательностей длины \(d_i\) периода \(d_i\).
  • Формула для количества циклических последовательностей длины \(n\) и периода \(n\)
    • \(U(d_i)\) - множество различных циклических последовательностей, которые могут быть получены из линейных последовательностей \(W(d_i)\). \(|U(d_i)|d_i =|W(d_i)|\); \(M(d_i) = |U(d_i)|\)
    • \(r^n = M(d_1)d_1 + \ldots + M(d_s)d_s = \sum\limits_{d \mid n} d M(d)\), по формуле обращения Мебиуса:
      \(M(n)= \frac{1}{n} \sum\limits_{d \mid n} \mu(d) r^\frac{n}{d}\)
  • Формула для количества циклических последовательностей:
    \(T_r(n) = \sum\limits_{d \mid n} M(d) = \sum\limits_{d \mid n} \left(\frac{1}{d} \left( \sum\limits_{d' | d} \mu(d') r^{\frac{d}{d'}}\right)\right).\)
Формула обращения Мёбиуса на частично упорядоченном множестве
  • \(\mu=\mu(x,y)\), определена только для \(x \preceq y\)
  • Функция Мёбиуса на чуме определяется индуктивно:
    • \(\mu(x,x)=1\)
    • \(\mu(x,y) = - \sum\limits_{x \preceq z \prec y} \mu(x,z)\)
  • Связь с обычной функцией Мебиуса
    • Пусть \(\mu^*\) - функция Мёбиуса от одного агрумента.
    • \(\mu(x,y)=\mu^*(\frac{y}{x})\)
  • Обобщённая формула обращения Мёбиуса на чуме
    • \(\langle X,\preceq \rangle\) - Частично упорядоченное множество, и множество \(\{y \mid y \preceq x\}\) - конечно
    • Пусть \(g: X\rightarrow \mathbb{C}(\mathbb{R})\)
    • \(f(y) = \sum\limits_{x \preceq y} g(x)\). Тогда: \(g(y) = \sum\limits_{x \preceq y} \mu(x,y)f(x).\)
Разбиения чисел на слагаемые
  • \(n=x_1+...+x_t\), где \(x_t > 0\), \(x_t \in \mathbb{N}\)
  • \(F(n;n_1,\dots,n_k)\) - количество упорядоченных разбиений \(n \in \mathbb{N}\) на слагаемые \(x_1,\dots,x_t\): \forall i: x_i \in \{n_1,\dots,n_k\}
    • \(F(n;n_1,\dots,n_k) = F(n-n_1;n_1,\dots,n_k)+ \dots+F(n-n_k;n_1,\dots,n_k);\); \(F(0;n_1,\dots,n_k)=1\); \(F(-n,n_1,\dots,n_k)=0\)
    • \(\phi(n)=2^{n-1}\), где \(\phi(n)=F(n;1,2,\ldots,n)\) - количество всех упорядоченных разбиений числа \(n\) на слагаемые
  • \(\pi(n;n_1,n_2,\ldots,n_k)\) - количество неупорядоченных разбиений числа \(n\) на слагаемые, каждое из которых равно одному из чисел \(n_1,n_2,\ldots,n_k\)
    • \(\pi(n;n_1,n_2,\ldots,n_k)=\pi(n-n_1;n_1,n_2,\ldots,n_k)+\pi(n;n_2,n_3,\ldots,n_k)\)
    • \(p(n)\sim\frac{1}{4n\sqrt{3}}e^{\pi\cdot\sqrt{\frac{2}{3}}\cdot\sqrt{n-\frac{1}{24}}}\) (асимптотика величины \(p(n)\)), где \(p(n)=\pi(n;1,2,\ldots,n)\) - количество всех неупорядоченных разбиений числа \(n\) на слагаемые (Теорема Харди, Рамануджан).
  • Диаграмма Юнга
    • \(n=x_1+x_2+\ldots+x_t\), \(x_1\leqslant x_2\leqslant\ldots\leqslant x_t\)
    • Пример для \(10=1+4+5\):
                для \(1\)
              для \(3\)
                для \(5\)
    • множество всех диаграмм Юнга и неупорядоченных разбиений находятся во взаимно-однозначном соответствии друг с другом
    • Двойственная диаграмма Юнга - Диаграмма, в которой строки и столбцы поменяны местами:
                       
                       
                       
                       
                       
    • Взятие двойственных диаграмм есть биективное отображение множества диаграмм Юнга.
  • Количество неупорядоченных разбиений \(n\) на не более, чем \(k\) слагаемых равно числу разбиений числа \(n+k\) на ровно \(k\) слагаемых.
Линейные рекуррентные соотношения
  • \(a_0, a_1,...a_k \in \mathbb{C}, a_k\ne 0, a_0 \ne 0\)
    Последовательность чисел \(y_0,y_1,...,y_n ...\) удовлетворяет линейному рекуррентному соотношению \(k\)-ого порядка с коэффициентами \(a_0, a_1...,a_k\), если \(\forall n\) выполнено такое равенство \(a_k y_{n+k}=a_{k-1}y_{n+k-1}+...+a_1y_{n+1}+a_0 y_n\).
  • Линейные рекуррентные соотношения второго порядка - \(y_{n+2}=a_1 y_{n+1}+a_0y_n, a_0 \ne 0.\)
    • \(\lambda ^2=a_1\lambda+a_0\) - характеристическое уравнение для рекуррентного соотношения, \(\lambda_1, \lambda_2\) - корни.
    • Пусть \(\lambda_1\ne \lambda_2\), тогда
      • Для любых чисел \(C_1, C_2\) последовательность \(y_n = C_1 \lambda_1^n+C_2\lambda_2^n\) удовлетворяет рекуррентному соотношению
      • Пусть \(y_n\) − последовательность чисел, удовлетворяющих линейно рекуррентному соотношению. Тогда \(\exists C_1, C_2: y_n = C_1 \lambda_1^n+C_2\lambda_2^n\).
    • Пусть \(\lambda_1= \lambda_2 = \lambda\), тогда
      • Для любых чисел \(C_1, C_2\) последовательность \(y_n=(C_1n+C_2) \lambda^n\) удовлетворяет рекуррентному соотношению
      • Пусть \(y_n\) − последовательность чисел, удовлетворяющих линейно рекуррентному соотношению. Тогда \(\exists C_1, C_2: y_n=(C_1n+C_2) \lambda^n\).
  • Линейные рекуррентные соотношения \(k\)-ого порядка - \(y_{n+k}=a_{k-1}y_{n+k-1}+...+a_1y_{n+1}+a_0y_n, a_0 \ne 0.\)
    • \(\lambda^k = a_{k-1}\lambda^{k-1}+...+a_1\lambda+a_0.\) - характеристическое уравнение для рекуррентного соотношения
    • Основная теорема алгебры: Любой многочлен с коэффициентами из \(\mathbb{C}\) имеет хотя бы один корень в \(\mathbb{C}\).
    • Пусть \(\lambda_1, \lambda_2,...,\lambda_k \in \mathbb{C}\) - корни характеристического уравнения. Обозначим через \(\mu_1,...,\mu_r\) − различные числа в множестве \(\{\lambda_1, \lambda_2,...,\lambda_k\}\). Пусть \(k_1,...,k_r; k_i\) − количество \(\lambda_i\), равных \(\mu_i\).
      • Пусть \(P_1(n)\) - произвольный многочлен степени \(\le k_1-1\);
        пусть \(P_2(n)\) - произвольный многочлен степени \(\le k_2-1\);
        пусть \(P_r(n)\) - произвольный многочлен степени \(\le k_r-1\).
        Тогда последовательность \(y_n=P_1(n)\mu_1^n+P_2(n)\mu_2^n+\ldots+P_r(n)\mu_r^n\) удовлетворяет рекуррентному соотношению
      • Пусть \(y_n\) удовлетворяет рекуррентному соотношению. Тогда существуют \(~ P_1(n),...,P_r(n) ~:~ degP_i(n)\le k_i-1 \forall i\) и \(y_n =P_1(n)\mu_1^n+...+P_r(n)\mu_r^n\).
Формальные степенные ряды
  • \(a_0+a_1x+a_2x^2+...+a_nx^n+...\); \(a_0, a_1, a_2,...,a_n,... \in \mathbb{R}\)
  • \(A + B = C = C_0+C_1x+...+C_nx^n+...\); \(\forall i ~c_i=a_i+b_i\)
  • \(A \cdot B = C = C_0,...,C_n,...\); \(C_i=\sum\limits_{j=0}^i a_jb_{i-j}\)
  • \(A/B = C \leftrightarrow ~A=B \cdot C\)
    \(\begin{cases} a_0=b_0c_0\\ a_1=b_1c_0+b_0c_1 \\a_2=b_2c_0+b_1c_1+b_0c_2 \\ ...\end{cases}\)
  • \((1+x)^{\frac{1}{2}}=1+C_{1/2}^1x+C_{1/2}^2x^2+...+C_{1/2}^nx^n+...,\) где \(C_{a}^b=\frac{a!}{b!(a-b)!}=\frac{a(a-1)...(a-b+1)}{b!}.\)
  • \((1+x)^{\alpha}=1+C_{\alpha}^1x+C_{\alpha}^2x^2+...+C_{\alpha}^nx^n+...,\) где \(C_{a}^b=\frac{a!}{b!(a-b)!}=\frac{a(a-1)...(a-b+1)}{b!}.\)
Производящая функция
  • Производящая функция для последовательности чисел \(a_0, a_1,...,a_n,...\) - есть степенной ряд \(f(x)=\sum\limits_{k=0}^\infty a_k x^k\)
  • Частичная сумма - есть конечный ряд \(S_n(x)=\sum\limits_{k=0}^n a_k x^k\)
  • \(f(x)\) определена в точке x, если \(\exists \lim_{n \to \infty} S_n(x)\).
    Значение предела - есть значение ряда в точке \(x\).
  • Теорема о сходимости рядов
    • \(\rho =\frac{1}{\varlimsup_{n \to \infty} \sqrt[n]{|a_n|}}\) - радиус сходимости ряда.
    • \(f(x)\) определена в каждой точке \(x~:~|x| \lt \rho\),
  • Если \(|x| \lt \rho,\) то \(\left(\sum\limits_{n=0}^{\infty} a_n x^n\right)'=\sum\limits_{n=1}^{\infty}n a_n x^{n-1}\)

Теория алгоритмов

Асимптотические обозначения
  • Время работы алгоритма - \(T(n)\); \(n\) - размер входных данных
    • Приммер \(T(n) = c_1 + c_2n\), где \(c_1\) и \(c_2\) - постоянное время, константа, независящая от размера входных данных
  • \(\Theta\) - Точная асимпотическая оценка $$ \Theta(g(n)) = \begin{cases} f(n): \text{существуют константы } c_1 > 0, c_2 > 0, n_0 > 0 \\ \text{такие что } 0 \leq c_1g(n) \leq f(n) \leq c_2g(n), \forall n \geq n_0 \\ \end{cases}$$ $$f(n) = \Theta(g(n)) \stackrel{\text{def}}{=} \exists n_0, c_1 > 0, c_2 > 0 (\forall n > n_o (c_1 g(n) \leq f(n) \leq c_2 g(n)))$$
    • \(f(n) = \Theta(g(n))\)
    • \(g(n)\) является точной асимптотической оценкой функции \(f(n)\)
  • \(\mathcal{O}\) - верхняя асимптотическая оценка $$ \mathcal{O}(g(n)) = \begin{cases} f(n): \text{существуют константы } c > 0, n_0 > 0 \\ \text{такие что } 0 \leq f(n) \leq cg(n), \forall n \geq n_0 \\ \end{cases}$$ $$f(n) = \mathcal{O}(g(n)) \stackrel{\text{def}}{=} \exists n_0, c > 0 (\forall n > n_o (f(n) \leq c g(n)))$$
    • \(g(n)\) является верхней асимптотической оценкой функции \(f(n)\)
    • \(f(n) = \Theta(g(n) \rightarrow f(n) = \mathcal{O}(g(n))\)
  • \(\Omega\) - нижняя асимптотическая оценка $$ \Omega(g(n)) = \begin{cases} f(n): \text{существуют константы } c > 0, n_0 > 0 \\ \text{такие что } 0 \leq cg(n) \leq f(n), \forall n \geq n_0 \\ \end{cases}$$ $$f(n) = \Omega(g(n)) \stackrel{\text{def}}{=} \exists n_0, c > 0 (\forall n > n_o (f(n) \geq c g(n)))$$
    • \(g(n)\) является нижней асимптотической оценкой функции \(f(n)\)
    • \(f(n) = \Omega(g(n) \rightarrow f(n) = \Omega(g(n))\)
  • $$ f(n) = \Theta(g(n)) \leftrightarrow \begin{cases} f(n) = \mathcal{O}(g(n)) \\ f(n) = \Omega(g(n)) \\ \end{cases}$$
Математика

Комментарии

Комментарии остутствуют