Добавил лекции и домашку по автоматам

25 files changed, 822 insertions, 0 deletions

diff --git a/Теория автоматов/fsm-hw/fsm-hw.pdf b/Теория автоматов/fsm-hw/fsm-hw.pdf
new file mode 100644
index 0000000..2873b86
--- /dev/null
+++ b/Теория автоматов/fsm-hw/fsm-hw.pdf
diff --git a/Теория автоматов/fsm-hw/fsm-hw.tex b/Теория автоматов/fsm-hw/fsm-hw.tex
new file mode 100644
index 0000000..9ffaf83
--- /dev/null
+++ b/Теория автоматов/fsm-hw/fsm-hw.tex
@@ -0,0 +1,286 @@
+\documentclass[a4paper,oneside,12pt]{extarticle}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+\usepackage[
+  left=3cm, right=3cm,
+  top=2cm, bottom=2cm
+]{geometry}
+
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathtools}
+\usepackage{amsfonts}
+\usepackage{enumitem}
+\usepackage{amsthm}
+\usepackage{minted}
+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
+\usepackage{float}
+\usepackage{underscore}
+\usepackage{braket}
+
+\usepackage{enumitem}
+\makeatletter
+\AddEnumerateCounter{\asbuk}{\russian@alph}{щ}
+\makeatother
+
+\newtheorem{theorem}{Теорема}[subsection]
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}[subsection]
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\title{{Теория автоматов}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section*{Тема 2}
+
+\subsection*{Задача 2.30 (41)}
+
+Обязательно ли изоморфные автоматы эквивалентны? Доказать или привести
+контрпример. Тот же вопрос в обратную сторону.
+
+\subsection*{Решение}
+
+Два состояния $s_i$ и $s_j$ являются эквивалентными тогда и только тогда, когда,
+наблюдая внешние выходы, нельзя отличить автомат $M_1$ в начальном состоянии
+$s_i$ от автомата $M_2$ в начальном состоянии $s_j$.
+
+Автоматы $M_1$ и $M_2$ являются эквивалентными если каждому состоянию $s_i$ из
+$M_1$ соответствует, по крайней мере, одно эквивалентное состояние в автомате
+$M_2$ и каждому состоянию $s_j$ из $M_2$ соответствует, по крайней мере, одно
+эквивалентное состояние в автомате $M_1$.
+
+Определение эквивалентности автоматов означает, что два автомата, имеющих
+одинаковые таблицы переходов, графы или матрицы должны быть эквивалентны.
+Кроме того, поскольку эквивалентность пары состояний не зависит от обозначений
+состояний, то два изоморфных автомата также должны быть эквивалентными.
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{2_isomorph}
+  \caption{Изоморфные графы}
+\end{figure}
+
+Обратное в общем случае неверно. Например:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.8\textwidth]{2_equiv}
+  \caption{Эквивалентные, но не изоморфные графы}
+\end{figure}
+
+
+\newpage
+\section*{Тема 3}
+
+\subsection*{Задача 3.23 (32)}
+
+Постройте автомат, от которого никаким экспериментом длины 4 нельзя отличить
+автомат на рисунке, в предположении, что автоматы не эквивалентны.
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.5\textwidth]{3_23_problem}
+\end{figure}
+
+\subsection*{Решение}
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{3_23_solution}
+\end{figure}
+
+
+\newpage
+\section*{Тема 4}
+
+\subsection*{Задача 4.23 (а, б, в)}
+
+Постройте автомат с двумя состояниями, отвечающий следующим требованиям:
+\begin{enumerate}[label=(\asbuk*)]
+  \item чтобы он не был автоматом с конечной памятью;
+  \item чтобы он был автоматом с конечной памятью, но не зависящим от выхода;
+  \item чтобы он был не зависящим от выхода автоматом.
+\end{enumerate}
+
+\subsection*{Решение}
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{4_a}
+  \caption{Задача (а)}
+\end{figure}
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{4_b}
+  \caption{Задача (б)}
+\end{figure}
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.8\textwidth]{4_v}
+  \caption{Задача (в)}
+\end{figure}
+
+
+
+\newpage
+\section*{Тема 5}
+
+\subsection*{Задача 5.2}
+
+Преобразуйте следующий НКА в эквивалентный ДКА.
+
+\begin{table}[H]
+  \centering
+  \begin{tabular}{c||c|c}
+                    & 0             & 1            \\ \hline \hline
+    $\rightarrow p$ & $\set{q, s}$  & $\set{q}$    \\
+    $^*q$           & $\set{r}$     & $\set{q, r}$ \\
+    $r$             & $\set{s}$     & $\set{p}$    \\
+    $^*s$           & $\varnothing$ & $\set{p}$    \\
+  \end{tabular}
+\end{table}
+
+\subsection*{Решение}
+
+Изобразим данный НКА в виде графа:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.5\textwidth]{5_nondet}
+\end{figure}
+
+Построим ДКА, эквивалентный данному НКА следующим образом:
+состояниями в ДКА будут являться множества состояний, в которых может
+находиться НКА. Переходами между этими состояниями будут переходы в НКА,
+которые переводят одно множество состояний в другое множество состояний.
+
+Таким образом, получим следующий автомат:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.8\textwidth]{5_det}
+\end{figure}
+
+
+
+
+\newpage
+\section*{Тема 6}
+
+\subsection*{Задача 6.1}
+
+Вариант 6 --- $6_{10} = 0020_3$, $0020_3 + 2121_3 = 2111_3$
+
+Найти кратчайшую синхронизирующую последовательность для вашего варианта
+автомата или доказать, что ее не существует.
+
+Матрица автомата по варианту:
+\begin{table}[H]
+  \centering
+  \begin{tabular}{|c|c|c|}
+    \hline
+      & a & b \\ \hline
+    0 & 0 & 2 \\ \hline
+    1 & 0 & 1 \\ \hline
+    2 & 2 & 1 \\ \hline
+    3 & 0 & 1 \\ \hline
+  \end{tabular}
+\end{table}
+
+\subsection*{Решение}
+
+Изобразим данный автомат в виде графа:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.65\textwidth]{6_graph}
+\end{figure}
+
+Можно заметить, что все переходы с символом $b$ ведут в сторону состояния 1.
+
+\begin{itemize}
+  \item
+    Пусть автомат находится в состоянии 1 --- если ввести слово $bb$, то
+    автомат останется в состоянии 1;
+  \item
+    Пусть автомат находится в состоянии 0 --- если ввести слово $bb$, то
+    автомат перейдёт сначала в состояние 2, а потом в состояние 1;
+  \item
+    Пусть автомат находится в состоянии 2 --- если ввести слово $bb$, то
+    автомат перейдёт в состояние 1 и после этого останется в нём.
+\end{itemize}
+
+Таким образом, автомат синхронизируем последовательностью $bb$.
+
+
+\newpage
+\section*{Тема 7}
+
+\subsection*{Задача}
+
+Вариант 6 --- $6_{10} = 0110_2 \implies x_1 = 0, x_2 = 1, x_3 = 1, x_4 = 0$.
+
+Рассмотрим в качестве клеточного автомата (\textbf{бесконечную во все
+стороны}) плоскость, разбитую на квадраты равного размера (\textbf{клетки}).
+\textbf{Клетки} могут быть окрашены черным либо белым цветом, что составляет
+их состояние в моменты 0, 1, 2, \dots. Состояние автомата в момент $t$ --- это
+совокупность состояний всех клеток плоскости. \textbf{Невырожденным состоянием}
+назовем любое состояние автомата, при котором и черные, и белые клетки.
+
+Окрестностью клетки двумерного клеточного автомата назовем объединение этой
+клетки с окрестностью Мура (8 соседей, $6 \pmod{3} = 0$):
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.2\textwidth]{7_moore}
+\end{figure}
+
+\textbf{Зададим правило перехода}: в момент $t + 1$ клетка приобретает тот
+цвет, который имело четное ($x_2 = 1$) количество клеток из ее окрестности
+в момент $t$ (где 0 также считается четным числом). Требуется найти такое
+\textbf{невырожденное} начальное состояние, при котором черные клетки в какой-то
+момент исчезнут, но потом появятся ($x_3 x_4 = 10$).
+
+Если искомого невырожденного состояния не существует, доказать это. Исследуемый
+процесс изобразить графически.
+
+\subsection*{Решение}
+
+Чёрные клетки никогда не исчезнут.
+
+Допустим, мы установили в поле одну клетку чёрного цвета, оставив всю остальную
+бесконечную плоскость заполненную белыми клетками. В следующий момент
+времени все клетки, кроме окрестности чёрной клетки перекрасятся в чёрный,
+первоначальная точка станет белой, а её окрестность останется неизменной. То
+есть получится квадрат со стороной в 3 клетки полностью состоящий из белых клеток.
+
+В следующий шаг изначальная клетка снова перекрасится в чёрный, её окрестности
+станут белыми, а клетки на углах окрестности станут чёрными. Все остальные клетки
+снова станут белыми.
+
+В следующий шаг это снова повторится и первоначальная клетка будет чередовать
+свой цвет в каждый момент времени.
+
+Так как клетки с обоими цветами ведут себя симметрично, если закрасить всю
+плоскость чёрными клетками, кроме одной, получится симметричный вариант
+чередования цветов первоначальной клетки.
+
+При этом если предположить, что мы закрашиваем только некоторую конечную часть
+плоскости, то на бесконечной плоскости всегда найдётся клетка с противоположным
+цветом с одной и клеток внутри этой конечной части.
+
+То есть в любой момент времени на плоскости есть клетки с противоположными
+цветами, если начальное состояние плоскости было невырожденным.
+
+Видео с демонстрацией данного процесса приложено к письму.
+
+
+\end{document}
+
diff --git a/Теория автоматов/fsm-hw/images/2_equiv.jpeg b/Теория автоматов/fsm-hw/images/2_equiv.jpeg
new file mode 100644
index 0000000..ae1cd39
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/2_equiv.jpeg
diff --git a/Теория автоматов/fsm-hw/images/2_isomorph.jpeg b/Теория автоматов/fsm-hw/images/2_isomorph.jpeg
new file mode 100644
index 0000000..7d1f7ec
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/2_isomorph.jpeg
diff --git a/Теория автоматов/fsm-hw/images/3_23_problem.png b/Теория автоматов/fsm-hw/images/3_23_problem.png
new file mode 100644
index 0000000..c368554
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/3_23_problem.png
diff --git a/Теория автоматов/fsm-hw/images/3_23_solution.jpeg b/Теория автоматов/fsm-hw/images/3_23_solution.jpeg
new file mode 100644
index 0000000..8d2b4f5
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/3_23_solution.jpeg
diff --git a/Теория автоматов/fsm-hw/images/4_a.jpeg b/Теория автоматов/fsm-hw/images/4_a.jpeg
new file mode 100644
index 0000000..c1382da
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/4_a.jpeg
diff --git a/Теория автоматов/fsm-hw/images/4_b.jpeg b/Теория автоматов/fsm-hw/images/4_b.jpeg
new file mode 100644
index 0000000..997f44e
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/4_b.jpeg
diff --git a/Теория автоматов/fsm-hw/images/4_v.jpeg b/Теория автоматов/fsm-hw/images/4_v.jpeg
new file mode 100644
index 0000000..4d7e179
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/4_v.jpeg
diff --git a/Теория автоматов/fsm-hw/images/5_det.jpeg b/Теория автоматов/fsm-hw/images/5_det.jpeg
new file mode 100644
index 0000000..630d5a4
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/5_det.jpeg
diff --git a/Теория автоматов/fsm-hw/images/5_nondet.jpeg b/Теория автоматов/fsm-hw/images/5_nondet.jpeg
new file mode 100644
index 0000000..72cd309
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/5_nondet.jpeg
diff --git a/Теория автоматов/fsm-hw/images/6_graph.jpeg b/Теория автоматов/fsm-hw/images/6_graph.jpeg
new file mode 100644
index 0000000..4b21a58
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/6_graph.jpeg
diff --git a/Теория автоматов/fsm-hw/images/7_moore.png b/Теория автоматов/fsm-hw/images/7_moore.png
new file mode 100644
index 0000000..d1e6323
--- /dev/null
+++ b/Теория автоматов/fsm-hw/images/7_moore.png
diff --git a/Теория автоматов/fsm-hw/maker.sh b/Теория автоматов/fsm-hw/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/Теория автоматов/fsm-hw/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" -exec rm {} \;
+    rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc
+}
+
+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/images/DUW.png b/Теория автоматов/presentation2/images/DUW.png
new 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
new 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
new 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}
diff --git a/Теория автоматов/presentation3/images/1.png b/Теория автоматов/presentation3/images/1.png
new file mode 100644
index 0000000..c3756ee
--- /dev/null
+++ b/Теория автоматов/presentation3/images/1.png
diff --git a/Теория автоматов/presentation3/images/2.png b/Теория автоматов/presentation3/images/2.png
new file mode 100644
index 0000000..098e4e1
--- /dev/null
+++ b/Теория автоматов/presentation3/images/2.png
diff --git a/Теория автоматов/presentation3/images/3.png b/Теория автоматов/presentation3/images/3.png
new file mode 100644
index 0000000..c83e25c
--- /dev/null
+++ b/Теория автоматов/presentation3/images/3.png
diff --git a/Теория автоматов/presentation3/images/4.png b/Теория автоматов/presentation3/images/4.png
new file mode 100644
index 0000000..59fd3f5
--- /dev/null
+++ b/Теория автоматов/presentation3/images/4.png
diff --git a/Теория автоматов/presentation3/images/5.png b/Теория автоматов/presentation3/images/5.png
new file mode 100644
index 0000000..32b7928
--- /dev/null
+++ b/Теория автоматов/presentation3/images/5.png
diff --git a/Теория автоматов/presentation3/presentation.tex b/Теория автоматов/presentation3/presentation.tex
new file mode 100644
index 0000000..f92e0cc
--- /dev/null
+++ b/Теория автоматов/presentation3/presentation.tex
@@ -0,0 +1,141 @@
+\documentclass{beamer}
+
+\usepackage[T2A]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage[english,russian]{babel}
+\usepackage{wrapfig}
+\usepackage{graphicx}
+\usepackage{multirow}
+\graphicspath{ {./images/} }
+
+\usetheme{Madrid}
+
+\title{Формирование системы операторов $\phi$. Логическая схема комбинационного
+автомата}
+\author[Гущин А.Ю.]{Гущин Андрей Юрьевич}
+\institute[СГУ]{Саратовский Государственный Университет}
+\date{4 мая 2023 г.}
+
+\begin{document}
+
+\maketitle
+
+\begin{frame}
+  \begin{center}
+    \textbf{Формирование системы операторов $\phi$}
+  \end{center}
+\end{frame}
+
+
+\begin{frame}
+  Пусть необходимо разработать преобразователь четырехразрядного двоичного кода
+  в код Штибитца:
+  \begin{figure}[H]
+    \centering
+    \includegraphics[width=.6\textwidth]{1}
+    \caption{Преобразователь кода}
+    \label{fig:image1}
+  \end{figure}
+\end{frame}
+
+\begin{frame}
+  \begin{figure}[H]
+    \centering
+    \includegraphics[width=.5\textwidth]{2}
+    \label{fig:image1}
+  \end{figure}
+  \begin{center}
+    Таблица 1
+  \end{center}
+\end{frame}
+
+\begin{frame}
+  По данным таблицы 1 составлены четыре карты Карно.
+
+  \begin{figure}[H]
+    \centering
+    \includegraphics[width=.75\textwidth]{3}
+    \caption{Карты Карно четырехразрядного преобразователя кода}
+    \label{fig:image1}
+  \end{figure}
+
+  Сравнивая соответствующие клетки четырех карт, можно выделить одинаковую
+  смежность на двух, трех и/или четырех картах, что позволит унифицировать и
+  минимизировать описание булевых функций.
+\end{frame}
+
+\begin{frame}
+  Выбор минимальной булевой функции нужно проверить на ДНФ и КНФ.
+
+  Ниже приведены минимальные булевы функции ДНФ и КНФ.
+
+  \begin{equation*}
+     \begin{cases}
+       \phi_1 = 1 = \overline{x_1} \\
+       \phi_2 = 1 = (\overline{x_1} \cdot \overline{x_2}) \vee x_1 \cdot x_2 = x_1 \leftrightarrow x_2 = \overline{(x_1 \oplus x_2)} \\
+       \phi_3 = 1 = (\overline{x_1} \cdot \overline{x_2}) \cdot x_3 \vee x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_3} \\
+       \phi_4 = 1 = (\overline{x_1} \cdot \overline{x_2}) \cdot x_4 \vee \overline{x_3} \cdot x_4 \vee (x_1 \vee x_2) \cdot (x_3 \cdot \overline{x_4})
+     \end{cases}
+    \end{equation*}
+
+    \begin{equation*}
+      \begin{cases}
+        \phi_1 = 0 = \overline{x_1} \\
+        \phi_2 = 0 = (\overline{x_1} \vee x_2) \cdot (x_1 \vee \overline{x_2}) = x_1 \leftrightarrow x_2 = (x_1 \oplus x_2)\\
+        \phi_3 = 0 = (\overline{x_2} \cdot \overline{x_3}) \cdot (\overline{x_1} \vee \overline{x_3}) \cdot ((x_1 \vee x_2) \vee x_3) \\
+        \phi_4 = 0 = (x_3 \vee x_4) \cdot ((\overline{x_1} \vee \overline{x_3}) \vee \overline{x_4}) \cdot ((\overline{x_2} \vee \overline{x_3}) \vee \overline{x_4}) \cdot ((x_1 \vee x_2) \vee x_4)
+      \end{cases}
+     \end{equation*}
+\end{frame}
+
+\begin{frame}{Применение}
+  Система булевых функций используется при создании дешифраторов или
+  преобразователей кодов, при формировании нескольких команд на исполнение
+  одного задания и т.п.
+\end{frame}
+
+\begin{frame}
+  \begin{center}
+    \textbf{Логическая схема комбинационного автомата}
+  \end{center}
+\end{frame}
+
+\begin{frame}
+  Комбинационные автоматы реализуют логические функции с помощью логических
+  схем. Для проектирования комбинационных автоматов разработаны стандарты
+  обозначения различных логических схем.
+\end{frame}
+
+\begin{frame}{Обозначение и схемы логических функций}
+
+  \begin{figure}[H]
+    \centering
+    \includegraphics[width=.5\textwidth]{4}
+    \label{fig:image1}
+  \end{figure}
+
+\end{frame}
+
+\begin{frame}
+  На предыдущем рисунке приведены основные логические схемы для элементарных
+  булевых функций двух булевых переменных. Реальная аппаратура содержит в
+  одной микросхеме большое число элементарных логических схем, что существенно
+  упрощает формирование логической сети. Микросхемы (такова особенность
+  микроэлектроники) реализуют большинство логических функций в базисе <<И-НЕ>> и
+  <<ИЛИ-НЕ>>. В этом случае инверсия булевой переменной может быть реализована
+  также на логической схеме <<И-НЕ>> или <<ИЛИ-НЕ>>, объединив два входных
+  канала.
+\end{frame}
+
+\begin{frame}
+  На рисунке представлена логическая схема комбинационного автомата
+  преобразователя двоичного кода в код Штибитца, спроектированная по минимальным
+  булевым функциям для $f_i=1$.
+  \begin{figure}[H]
+    \centering
+    \includegraphics[width=.8\textwidth]{5}
+    \label{fig:image1}
+  \end{figure}
+\end{frame}
+
+\end{document}