path: root/Теория автоматов/presentation2/presentation.tex

\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}