diff options
Diffstat (limited to 'Теория автоматов/presentation2')
| -rw-r--r-- | Теория автоматов/presentation2/images/DUW.png | bin | 0 -> 139783 bytes | |||
| -rw-r--r-- | Теория автоматов/presentation2/images/forbidden.jpg | bin | 0 -> 186501 bytes | |||
| -rwxr-xr-x | Теория автоматов/presentation2/maker.sh | 35 | ||||
| -rw-r--r-- | Теория автоматов/presentation2/presentation.pdf | bin | 0 -> 240612 bytes | |||
| -rw-r--r-- | Теория автоматов/presentation2/presentation.tex | 325 |
5 files changed, 360 insertions, 0 deletions
diff --git a/Теория автоматов/presentation2/images/DUW.png b/Теория автоматов/presentation2/images/DUW.png Binary files differnew file mode 100644 index 0000000..90c49c9 --- /dev/null +++ b/Теория автоматов/presentation2/images/DUW.png diff --git a/Теория автоматов/presentation2/images/forbidden.jpg b/Теория автоматов/presentation2/images/forbidden.jpg Binary files differnew file mode 100644 index 0000000..a94f53c --- /dev/null +++ b/Теория автоматов/presentation2/images/forbidden.jpg diff --git a/Теория автоматов/presentation2/maker.sh b/Теория автоматов/presentation2/maker.sh new file mode 100755 index 0000000..9b12212 --- /dev/null +++ b/Теория автоматов/presentation2/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -delete + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc *.bcf *.nav *.xml *.snm *.vrb *.bbl +} + +help() { + echo "Использование:" + echo "./maker.sh watch <main-doc>.tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc <main-doc>.tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/Теория автоматов/presentation2/presentation.pdf b/Теория автоматов/presentation2/presentation.pdf Binary files differnew file mode 100644 index 0000000..3c1de28 --- /dev/null +++ b/Теория автоматов/presentation2/presentation.pdf 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} |
