diff options
25 files changed, 822 insertions, 0 deletions
diff --git a/Теория автоматов/fsm-hw/fsm-hw.pdf b/Теория автоматов/fsm-hw/fsm-hw.pdf Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 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} diff --git a/Теория автоматов/presentation3/images/1.png b/Теория автоматов/presentation3/images/1.png Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 Binary files differnew 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} |
