1 files changed, 325 insertions, 0 deletions
diff --git a/Теория автоматов/presentation2/presentation.tex b/Теория автоматов/presentation2/presentation.tex
new file mode 100644
index 0000000..cfc0137
--- /dev/null
+++ b/Теория автоматов/presentation2/presentation.tex
@@ -0,0 +1,325 @@
+\documentclass{beamer}
+
+\usepackage[T2A]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage[english,russian]{babel}
+\usepackage{wrapfig}
+\usepackage{graphicx}
+\usepackage{multirow}
+\usepackage{fancyvrb}
+\usepackage{underscore}
+\graphicspath{ {./images/} }
+
+\usetheme{Madrid}
+
+\usepackage{amsmath}
+\usepackage{amsthm}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{mathtools}
+\usepackage{braket}
+\usepackage{csquotes}
+
+\setbeamertemplate{caption}[numbered]
+\setbeamertemplate{theorems}[numbered]
+\let\theorem\relax
+\newtheorem{theorem}{Теорема}
+\let\definition\relax
+\newtheorem{definition}{Определение}
+
+\title{Теорема о функциональной полноте}
+\author[Гущин~А.~Ю.]{Гущин~Андрей~Юрьевич}
+\institute[СГУ]{Саратовский Государственный Университет}
+\date{\today}
+
+\newcommand{\ol}[1]{\overline{#1}}
+
+\begin{document}
+
+\maketitle
+
+\begin{frame}{Функциональная полнота}
+  Система логических элементов называется \textbf{функционально полной}, если
+  существует общий конструктивный прием, позволяющий строить из логических
+  элементов заданной системы корректные комбинационные схемы, имеющие любые
+  наперед заданные выходные функции.
+\end{frame}
+
+\begin{frame}{Функциональная полнота}
+  \begin{definition}
+    Система S булевых функций называется \textbf{функционально полной}, если
+    для любой булевой функции $f(x_1, \dots, x_m)$ можно построить равную ей
+    булеву функцию, представляющую собой результат суперпозиции (вообще говоря,
+    многократной) функций $x_1, \dots, x_m$ и функций системы $S$, взятых в
+    любом конечном числе экземпляров каждая ($m$ --- любое натуральное число).
+  \end{definition}
+
+  \begin{definition}
+    Система S булевых функций называется ослабленно функциональной полной,
+    если для любой булевой функции $f(x_1, \dots, x_m)$ можно построить равную
+    ей булеву функцию, представляющую собою результат суперпозиции (вообще
+    говоря, многократной) функций $x_1, \dots x_m$, констант 0 и 1 и функций
+    системы $S$, взятых в любом конечном числе экземпляров каждая.
+  \end{definition}
+\end{frame}
+
+\begin{frame}{Функции, сохраняющие константу 0}
+  Такие булевы функции $f(x_1, \dots, x_m)$, что $f(0, 0, \dots, 0) = 0$.
+
+  \begin{theorem}
+    Суперпозиция любого числа булевых функций, сохраняющих константу 0, является
+    также функцией, сохраняющей константу 0.
+  \end{theorem}
+  \begin{proof}
+    Пусть заданы $z = f(y_1, \dots, y_m)$ и $y_1 = g(x_1, \dots, x_n)$,
+    сохраняющие константу 0.
+
+    При подстановке нулевых значений аргументов в суперпозицию
+    \begin{equation*}
+      v = f(g(x_1, \dots, x_n), y_2, \dots, y_m)
+    \end{equation*}
+    обнаружим, что значение функции $v$ будет также равно нулю.
+  \end{proof}
+\end{frame}
+
+\begin{frame}{Функции, сохраняющие константу 1}
+  Такие булевы функции $f(x_1, \dots, x_m)$, что $f(1, 1, \dots, 1) = 1$.
+
+  \begin{theorem}
+    Суперпозиция любого числа булевых функций, сохраняющих константу 1, является
+    также функцией, сохраняющей константу 1.
+  \end{theorem}
+\end{frame}
+
+\begin{frame}{Самодвойственные функции}
+  Булевы функции $f(x_1, \dots, x_n)$ и $g(x_1, \dots, x_n)$
+  называются двойственными друг другу, если $g(x_1, \dots, x_n) =
+  \overline{f(\overline{x_1}, \dots, \overline{x_n})}$.
+
+  Булева функция $f(x_1, \dots, x_n)$ называется самодвойственной, если она
+  двойственна по отношению к себе самой, то есть если выполняется соотношение
+  $f(x_1, \dots, x_n) = \overline{f(\overline{x_1}, \dots, \overline{x_n})}$
+
+  Если условиться называть противоположными наборами набор $(\alpha_1, \dots,
+  \alpha_n)$ и набор $(\overline{\alpha_1}, \dots, \overline{\alpha_n})$, то
+  нетрудно следующим образом перефразировать определение самодвойственных
+  функций:
+  \begin{definition}
+    Булева функция называется самодвойственной, если на любых двух
+    противоположных наборах она принимает противоположные значения.
+  \end{definition}
+\end{frame}
+
+\begin{frame}{Самодвойственные функции}
+  \begin{theorem}
+    Суперпозиция любого числа самодвойственных функций является снова
+    самодвойственной функцией.
+  \end{theorem}
+  \begin{proof}
+    Пусть $z = f(y_1, \dots, y_m)$ и $y_1 = g(x_1, \dots, x_n)$ ---
+    самодвойственные функции. Двойственной функцией их суперпозиции
+    \begin{equation*}
+      v = f(g(x_1, \dots, x_n), y_2, \dots, y_m)
+    \end{equation*}
+    будет
+    \begin{equation*}
+      v^* = \ol{f(g(\ol{x_1}, \dots, \ol{x_n}), \ol{y_2}, \dots, \ol{y_m})}
+    \end{equation*}
+
+    Ввиду самодвойственности функции $g$ имеем $g(\ol{x_1}, \dots, \ol{x_n}) =
+    \ol{y_1}$. В виду самодвойственности $f$ имеем, что $v^* = v$.
+  \end{proof}
+\end{frame}
+
+\begin{frame}{Линейные функции}
+  Булева функция называется линейной, если, после представления её каноническим
+  полиномом в алгебре Жегалкина, в этом полиноме не окажется членов, имеющих
+  степени, выше чем первая, то есть представляющий эту функцию полином имеет вид
+  \begin{equation*}
+    a_0 + a_1 x_1 + \dots a_n x_n
+  \end{equation*}
+
+  Из определения линейных функций непосредственно следует справедливость
+  следующего предложения.
+  \begin{theorem}
+    Суперпозиция любого числа линейных булевых функций представляет собою снова
+    линейную функцию.
+  \end{theorem}
+\end{frame}
+
+\begin{frame}{Монотонные функции}
+  Для любых двух наборов $a = (\alpha_1, \dots, \alpha_n)$, $b = (\beta_1,
+  \dots, \beta_n)$, имеющих одинаковую размерность, отношение $a \leq b$
+  эквивалентно отношениям $a_i \leq b_i$ всех $i = 1, \dots, n$. При этом мы
+  считаем, что $0 \leq 0$, $0 \leq 1$, $1 \leq 1$.
+
+  \begin{definition}
+    Булева функция $f(x_1, \dots, x_n)$ называется монотонной, если для любых
+    наборов $a = (\alpha_1, \dots, \alpha_n)$ и $b = (\beta_1, \dots, \beta_n)$,
+    таких, что $a \leq b$, имеет место неравенство $f(\alpha_1, \dots, \alpha_n)
+    \leq f(\beta_1, \dots, \beta_n)$.
+  \end{definition}
+
+  \begin{theorem}
+    Суперпозиция любого числа монотонных булевых функций является в свою очередь
+    монотонной функцией.
+  \end{theorem}
+\end{frame}
+
+\begin{frame}{Монотонные функции}
+  \begin{proof}
+    Пусть заданы монотонные функции $z = f(y_1, \dots, y_m)$, $y_1 = g(x_1,
+    \dots, x_n)$. Возьмём два произвольных набора $a_1$ и $a_2$ ($a_1 \leq
+    a_2$). Каждый из этих наборов однозначно определяет соответствующие наборы
+    $b_1, c_1$ и $b_2, c_2$ значений переменных $x_i$ и $y_i$. При этом из $a_1
+    \leq a_2$ вытекает $b_1 \leq b_2$ и $c_1 \leq c_2$.
+
+    Обозначим через $v_1$ и $v_2$ значения суперпозиции $v = f(g(x_1, \dots,
+    x_n), y_2, \dots, y_m)$ на наборах $a_1$ и $a_2$. Через $g_1$ и $g_2$ ---
+    значения функции $g(x_1, \dots, x_n)$ на наборах $b_1$ и $b_2$. Если наборы
+    $c_1$ и $c_2$ имеют вид $c_1 = (\alpha_1, \dots, \alpha_m)$, $c_2 = (
+    \beta_1, \dots, \beta_m)$, то получаем
+    \begin{align*}
+      v_1 &= f(g_1, \alpha_2, \dots, \alpha_m), \\
+      v_2 &= f(g_2, \beta, \dots, \beta).
+    \end{align*}
+  \end{proof}
+\end{frame}
+
+\begin{frame}{Монотонные функции}
+  \begin{proof}
+    Так как $g$ монотонна $\implies g_1 \leq g_2$, $c_1 \leq c_2 \implies
+    \alpha_2 \leq \beta_2, \dots, \alpha_m \leq \beta_m$. Получаем
+    \begin{equation*}
+      (g_1, \alpha_2, \dots, \alpha_m) \leq (g_1, \beta_2, \dots, \beta_m)
+    \end{equation*}
+
+    Из этого неравенства в силу монотонности функции $f$ получаем неравенство
+    $v_1 \leq v_2$, то есть суперпозиция функций также монотонна.
+  \end{proof}
+
+  \begin{theorem}
+    В результате суперпозиции произвольной немонотонной функции $f(x_1, \dots,
+    x_n)$ с константами 0 и 1 может быть получена функция отрицания $\ol{x_i}$
+    одного из аргументов функции $f(x_1, \dots, x_n)$.
+    \label{thm:supneg}
+  \end{theorem}
+\end{frame}
+
+\begin{frame}{Монотонные функции}
+  \begin{proof}
+    Даны $a \leq b, f(a) = 1, f(b) = 0$.
+
+    Соседние друг другу наборы: $a_0 = a, a_1, a_2, \dots, a_n = b$.
+
+    Найдутся $f(a_k) = 1, f(a_{k + 1}) = 0$. Пусть они отличаются в $i$-й
+    компоненте. Она обязательно равна нулю в наборе $a_k$ и единице в наборе
+    $a_{k + 1}$. То есть
+    \begin{align*}
+      a_k &= (\alpha_1, \dots, \alpha_{i - 1}, 0, \alpha_{i + 1}, \dots, \alpha_n), \\
+      a_{k + 1} &= (\alpha_1, \dots, \alpha_{i - 1}, 1, \alpha_{i + 1}, \dots, \alpha_n). \\
+    \end{align*}
+
+    Пусть $g(x_i) = f(\alpha_1, \dots, \alpha_{i - 1}, x_i, \alpha_{i + 1},
+    \dots, \alpha_n)$. Получаем, что $g(0) = 1$ и $g(1) = 0$, то есть $g(x_i) =
+    \ol{x_i}$.
+  \end{proof}
+\end{frame}
+
+\begin{frame}{Теорема о функциональной полноте}
+  \begin{theorem}
+    Для того чтобы система $S$ булевых функций была функционально полной,
+    необходимо и достаточно, чтобы эта система содержала хотя бы одну функцию,
+    не сохраняющую константу 0, хотя бы одну функцию, не сохраняющую константу
+    1, хотя бы одну несамодвойственную функцию, хотя бы одну нелинейную функцию
+    и хотя бы одну немонотонную функцию.
+  \end{theorem}
+\end{frame}
+
+\begin{frame}{Теорема о функциональной полноте}
+  \begin{proof}
+    Зафиксируем функции $f_1, f_2, f_3, f_4, f_5$. Образуем суперпозицию
+    $g(x_1) = f_1(x_1, x_1, \dots, x_1)$. $g(0) = 1$. Если $g(1) = 1$, то
+    $g(x_1) \equiv 1$. Имея константу 1, подставляем её в $f_2$ и получаем
+    константу 0.
+
+    Если $g(1) = 0$ $\implies$ $g(x_1) = \ol{x1}$. $f_3$ --- несамодвойственная,
+    $\exists (\alpha_1, \dots, \alpha_k) : f_3(\alpha_1, \dots, \alpha_k) =
+    f_3(\ol{\alpha_1}, \dots, \ol{\alpha_k})$. Построим суперпозицию
+    \begin{equation*}
+      h(x_1) = f_3(\varphi_1(x_1), \dots, \varphi_k(x_1)),
+    \end{equation*}
+    $\varphi_i(x_1) = x_1$, если $\alpha_i = 0$ и $\varphi_i(x_1) = \ol{x_1}$
+    если $\alpha_i = 1$.
+
+    Получаем
+    \begin{align*}
+      h(0) &= f_3(\varphi_1(0), \dots, \varphi_k(0)) = f_3(\alpha_1, \dots, \alpha_k) = \\
+           &= f_3(\ol{\alpha_1}, \dots, \ol{\alpha_k}) =
+           f_3(\varphi_1(1), \dots, \varphi_k(1)) = h(1)
+    \end{align*}
+
+    То есть $h(x)$ тождественно равна 0 или 1. Образуя суперпозицию с $g(x_1)$
+    получаем вторую константу.
+  \end{proof}
+\end{frame}
+
+\begin{frame}{Теорема о функциональной полноте}
+  \begin{proof}
+    С помощью теоремы \ref{thm:supneg} получаем $\ol{x_i}$. Любая суперпозиция
+    может быть представлена в виде СКНФ, а СНКФ может быть представлена в виде
+    СДНФ в соответствии со вторым правилом де Моргана. Для завершения доказательства
+    необходимо получить функцию $x_1 x_2$.
+
+    Нелинейную функцию $f_4$ можем представить в виде полинома Жегалкина, в
+    котором обязательно будет произведение каких-либо двух переменных
+    $x_i$ и $x_j$.
+
+    Полином можно представить в виде
+    \begin{align*}
+      f_4(x_1, \dots, x_p) &= x_1 x_2 \psi_1(x_3, \dots, x_p) +
+      x_1 \psi_2(x_3, \dots, x_p) + \\
+       &+ x_2 \psi_3(x_3, \dots, x_p) + \psi_4(x_3, \dots, x_p)
+    \end{align*}
+  \end{proof}
+\end{frame}
+
+
+\begin{frame}{Теорема о функциональной полноте}
+  \begin{proof}
+    Перебирая значения переменных получим функцию
+    \begin{equation*}
+      \varepsilon(x_1, x_2) = x_1 x_2 + \alpha x_1 + \beta x_2 + \gamma
+    \end{equation*}
+
+    \begin{equation*}
+      \varepsilon(x_1 + \beta, x_2 + \alpha) = x_1 x_2 + \delta, \quad
+      \delta = \alpha \beta + \gamma
+    \end{equation*}
+
+    Если $\delta = 0$, то искомая функция построена. Если $\delta = 1$, то
+    мы построили функцию $x_1 x_2 + 1 = \ol{x_1 x_2}$. Суперпозицией с
+    имеющейся функцией $\ol{x_i}$ получаем искомую функцию.
+
+    Таким образом, теорема о функциональной полноте доказана.
+  \end{proof}
+\end{frame}
+
+\begin{frame}{Теорема о функциональной полноте}
+  Естественно называть функционально полную систему булевых функций
+  несократимой, если из нее нельзя исключить ни одной функции так, чтобы
+  оставшаяся после исключения система функций снова была бы функционально
+  полной.
+
+  В любой несократимой функционально полной системе булевых функций содержится
+  не более 5 функций. В действительности, их число всегда может быть сокращено
+  до 4, поскольку функция $f$, не сохраняющая 0, либо не сохраняет 1, либо
+  (если $f(1, 1, \dots, 1) = 1$) является несамодвойственной.
+
+  \begin{definition}
+    Максимальное возможное число функций в несократимой функционально полной
+    системе булевых функций равно четырем.
+  \end{definition}
+\end{frame}
+
+\end{document}