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

Последнее обновление:

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

Логика

\(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 = \{x: P(x)\}\) - Определение множества с помощью предикатов
Множество \(A\) из элементов \(x\), для которых предикат \(P(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\) - Универсальное множество
\(\mathbb{N} = \{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 \}\}\}\} \}\} \)
\(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, \leq)\)
Если отношение \(R\) на \(A\) является отношением частичного порядка.
Два элемента \(а\) и \(Ь\) частично упорядоченного множества \((S, \leq)\) сравнимы, если \(а < b\) или \(b < а\).
Линейный порядок: Если каждые два элемента частично упорядоченного множества \((S, \leq)\) сравнимы, то \((S, \leq)\) называется вполне упорядоченным множеством, или цепью.
Предшественник: если \(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)
Тезис Чёрча-Тьюринга
  • Любую вычислимую функцию, на реальном вычислительном устроистве, можно вычислить на машине Тьюринга.

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

Вычислимая функция.
  • \(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))\) вычислима.
  • Любая композиция вычислимых функций, будет вычислимой функцией.
  • Любая функция с конечной областью определения вычислима.
Разрешимые множества
  • Пусть \(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\) - разрешимо, тогда и только тогда, когда \(A\) и \(\overline{A}\) перечислимо

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

Правило сложения (Комбинаторный принцип сложения)
Кол-во вариантов выбора 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\)

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

Асимптотические обозначения
  • Время работы алгоритма - \(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))\)
    • \(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}$$
    • \(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}$$
    • \(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}$$