% % Copyright (c) 2006 Aleksey Fedoseev % Permission is granted to copy, distribute and/or modify this document % under the terms of the GNU Free Documentation License, Version 1.2 % or any later version published by the Free Software Foundation; % with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. % \documentclass[12pt,a4paper]{article} \usepackage[T2A]{fontenc} \usepackage{ucs} \usepackage[utf8]{inputenc} \usepackage[english,russian]{babel} \usepackage{indentfirst} \usepackage{amsmath} \usepackage{amssymb} \usepackage{graphicx} \pagestyle{plain} \parindent=1.25cm \textheight=24cm \topmargin=-1cm \frenchspacing \begin{document} \title{\textbf{Семинары по Дискретной математике}} \author{Алексей Федосеев} \date{Версия 1.0, июнь 2006 г.} \maketitle Этот текст распространяется под лицензией GNU Free Documentation License (FDL) версии 1.2. Подробную информацию об этой лицензии Вы можете узнать по адресу: \emph{http://www.gnu.org/copyleft/fdl.html}. Обо всех неточностях и дополнениях Вы можете сообщать автору на электронную почту: \emph{aleksey@fedoseev.net}. Буду рад любым комментариям. \tableofcontents % семинар 1 \clearpage \section{Множества и отношения} \paragraph{Определение множества} Множество~--- это совокупность элементов, которые объединены \emph{отношением принадлежности}. Для любого элемента множества $A$ можно заключить: $a \in A$. Множества бывают конечными (из конечного числа элементов) и бесконечными. Конечные множества могут задаваться перечислением их элементов, например: $$ A = \{1, 2, 3, 4\}, B = \{\mbox{Иванов}, \mbox{Петров}, \mbox{Сидоров}\} $$ Бесконечные множества удобно задавать с помощью коллективизирующего условия: $A = \{ x | P(x) \}$, где $P(x)$ принимает значение ``истина'' или ``ложь''. Например, $A = \{ x | k \in \mathbb{N}, x = 2 k \}$. Множества считаются равными тогда и только тогда, когда они состоят из одних и тех же элементов: $$ A = B \Leftrightarrow (\forall x)(x \in A \Leftrightarrow x \in B) $$ \emph{Отношение включения}~--- множество $A$ включается в множество $B$, если все элементы $A$ принадлежат $B$: $A \subseteq B \Leftrightarrow (\forall x)(x \in A \Rightarrow x \in B)$. Тогда $A = B \Leftrightarrow (A \subseteq B) \And (B \subseteq A)$. Порядок элементов в множестве не играет роли, множество не содержит повторяющихся элементов: $\{1, 2, 3, 4\} = \{1, 2, 4, 3\} = \{1, 1, 2, 3, 4\}$. Не следует путать множества элементов и множества множеств: $\{1, 2, 3, 4\} \neq \{\{1, 2\}, \{3, 4\}\}$. \emph{Пустое множество} не содержит ни одного элемента $(\forall a) (a \notin A)$. При этом $\{ \varnothing \} \neq \varnothing $. \emph{Существует ли множество, содержащее само себя?} Да, рассмотрим пример: $Z = \{ X | \mbox{X~--- множество, содержащее не менее трёх элементов} \}$: $$ \left. \begin{array}{c} \{1, 2, 3\} \in Z \\ \{1, 2, 3, 4\} \in Z \\ \{1, 2, 3, 4, 5\} \in Z \\ \end{array} \right\} \Rightarrow Z \in Z $$ \emph{Существует ли множество, не содержащее само себя?} $Y = \{ X | X \notin X\}$. Это парадокс Рассела. \paragraph{Операции над множествами} Существуют операции над множествами (получение новых множеств на основе существующих): $$ \begin{array}{ll} \mbox{Объединение:} & A \cup B = \{x | x \in A \vee x \in B \}\\ \mbox{Пересечение:} & A \cap B = \{x | x \in A \And x \in B \}\\ \mbox{Разность:} & A \setminus B = \{x | x \in A \And x \notin B \}\\ \mbox{Симметрическая разность:} & A \bigtriangleup B = (A \cup B) \setminus (A \cap B) \end{array} $$ Если задано \emph{универсальное множество} $U$, то может быть введена операция \emph{дополнения}: $\overline{A} = U \setminus A$. Указанные операции обладают рядом интересных свойств (см. литературу). Свойства оформляются в виде тождеств (всегда истинных равенств). Существует несколько способов доказательства теоретико-множественных тождеств: \begin{enumerate} \item метод двух включений; \item метод характеристических функций; \item метод эквивалентных преобразований. \end{enumerate} Операции над множествами могут быть проиллюстрированы на \emph{диаграммах Венна}. Например, пересечение множеств может быть представлено как тёмная область на рисунке \ref{Pic:venn_and}. \begin{figure}[tbh] \begin{center} \includegraphics[width=4cm]{venn_and.eps} \caption{Диаграмма Венна для пересечения множеств} \label{Pic:venn_and} \end{center} \end{figure} \emph{Метод двух включений} основывается на укзанном выше определении равенства множеств ($A = B \Leftrightarrow (A \subseteq B) \And (B \subseteq A)$). Необходимо доказать две леммы: если $x \in A \Rightarrow x \in B$ и $x \in B \Rightarrow x \in A$. Рассмотрим пример: Доказать тождество $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$. Докажем методом двух включений: $$ \begin{array}{l} \triangleleft\quad \mbox{Необходимость:}\quad x \in (A \cup B) \setminus (A \cap B) \Rightarrow \\(x \in (A \cup B) \And x \notin (A \cap B)) \Rightarrow \left\{ \begin{array}{l} x \in A \Rightarrow x \neq B \\ x \in B \Rightarrow x \neq A \\ \end{array} \right\} \Rightarrow \\ (x \in A \setminus B) \vee (x \in B \setminus A) \Rightarrow x \in (A \setminus B) \cup (B \setminus A). \\ \mbox{Достаточность:}\quad x \in (x \in (A \cup B) \And x \notin (A \cap B)) \Rightarrow \\(x \in A \And x \notin B) \vee (x \in B \And x \notin A) \Rightarrow \\ (x \in A \cup B) \And (x \notin A \cap B) \Rightarrow x \in (A \cup B) \setminus (A \cap B) \quad\triangleright \end{array} $$ \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Доказать методом двух включений и проиллюстрировать результаты на диаграммах Венна: \begin{itemize} \item $(A \setminus B) \setminus C = A \setminus (B \setminus C)$; \item $(A \setminus B) \setminus C = (A \setminus C) \setminus (B \setminus C)$. \end{itemize}\\ \hline \end{tabular} \end{center} \emph{Метод характеристичских функций} состоит в сопоставлении каждому множеству $A$ функции $\chi_A(x) = \left\{ \begin{array}{l} 1, x \in A\\ 0, x \notin A \end{array} \right.$. Тогда функции, соответствующие операциям, будут равны: $$ \begin{array}{l} \chi_{A \cap B} = \chi_A \chi_B;\\ \chi_{A \cup B} = \chi_A + \chi_B - \chi_A \chi_B;\\ \chi_{A \setminus B} = \chi_A (1 - \chi_B). \end{array} $$ Рассмотрим пример доказательства приведённого выше тождества, $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$: Требуется показать, что $\chi_{(A \cup B) \setminus (A \cap B)} = \chi_{(A \setminus B) \cup (B \setminus A)}$. $$ \begin{array}{l} \triangleleft\quad \chi_{(A \cup B) \setminus (A \cap B)} = \chi_{A \cup B} (1 - \chi_{A \cap B}) = (\chi_A + \chi_B - \chi_A \chi_B)(1 - \chi_A \chi_B) = \\ = \chi_A - \chi_A \chi_B + \chi_B - \chi_A \chi_B - \chi_A \chi_B + \chi_A \chi_B = \underline{\chi_A + \chi_B - 2 \chi_A \chi_B}\\ \chi_{(A \setminus B) \cup (B \setminus A)} = \chi_A (1 - \chi_B) + \chi_B (1 - \chi_A) - \chi_A (1 - \chi_B) \chi_B (1 - \chi_A) = \\ = \chi_A + \chi_B - 2 \chi_A \chi_B - (\chi_A - \chi_A \chi_B) (\chi_B - \chi_A \chi_B) = \underline{\chi_A + \chi_B - 2 \chi_A \chi_B} \quad\triangleright \end{array} $$ \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Доказать методом характеристических функций и проиллюстрировать результаты на диаграммах Венна: \begin{itemize} \item $(A \bigtriangleup B) \bigtriangleup C = A \bigtriangleup (B \bigtriangleup C)$ \item $A \cup (B \bigtriangleup C) = (A \cup B) \bigtriangleup (A \cup C)$ \end{itemize}\\ \hline \end{tabular} \end{center} Метод эквивалентных преобразований заключается в последовательной подстановке известных тождеств в формулу для получения правой части доказываемого утверждения из левой или наоборот. \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Доказать методом эквивалентных преобразований и проиллюстрировать результаты на диаграммах Венна: $$A \bigtriangleup B = (A \cup B) \cap (\overline{A} \cup \overline{B}).$$\\ \hline \end{tabular} \end{center} \paragraph{Декартово произведение множеств} Определим множество \emph{упорядоченных пар} следующим образом: $$ A \times B = \{ z | z = (x, y), (x \in A) \And (y \in B) \} $$ В общем случае операция декартова произведения \emph{некоммутативна}: $A \times B \neq B \times A$. Также эта операция не обладает свойством \emph{ассоциативности} $ A \times (B \times C) \neq (A \times B) \times C \neq A \times B \times C$, действительно, если $a_i \in A, b_i \in B, c_i \in C$, то $(a_i, (b_i, c_i)) \neq ((a_i, b_i), c_i) \neq (a_i, b_i, c_i)$. Графически декартово произведение можно изобразить в виде квадрата на плоскости (рисунок \ref{Pic:set_product}). \begin{figure}[tbh] \begin{center} \includegraphics[width=4cm]{set_product.eps} \caption{Декартово произведение множеств} \label{Pic:set_product} \end{center} \end{figure} Умножение множества на себя называют декартовым квадратом (кубом и т.п.): $A^2 = A \times A$, $A^3 = A \times A \times A$, \dots. Декартов квадрат множества всех действительных чисел $\mathbb{R}^2$ образует декартову плоскость. \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Доказать методом двух включений и проиллюстрировать тождества графиком: \begin{itemize} \item $A \times (B \cup C) = (A \times B) \cup (A \times C)$; \item $A \times (B \setminus C) = (A \times B) \setminus (A \times C)$. \end{itemize}\\ Показать, что тождество $\overline{A \times B} = \overline{A} \times \overline{B}$ в общем случае неверно. Записать верное тождество и доказать его методом двух включений.\\ \hline \end{tabular} \end{center} \paragraph{Соответствия и операции над ними} Пусть заданы два множества $A$ и $B$, \emph{соответствием} называют некоторое подмножество их декартова произведения: $\rho \subseteq A \times B$ (рисунок \ref{Pic:correspondence}). Если для пары $(x, y) \in A \times B$ имеет место соответствие, то $(x, y) \in \rho$. Это также записывают в виде $x \rho y$. \begin{figure}[tbh] \begin{center} \includegraphics[width=4cm]{correspond.eps} \caption{Пример соответствия} \label{Pic:correspondence} \end{center} \end{figure} Существует несколько способов задания соответствия: перечислением элементов (возможно для конечных множеств $A$ и $B$), заданием предиката (например, $\rho = \{ (x, y) | x \in A, y \in B, x < y + 5\}$), и в виде графа, часто соответствие иллюстрируют графиком (рисунок \ref{Pic:corr_graph}). \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{corr_graph.eps} \caption{Пример задания соответствия графически} \label{Pic:corr_graph} \end{center} \end{figure} Для каждого соответствия рассматривают \emph{область определения} $\mbox{dom}\, \rho = \{ x | x \in A \And (\exists y) ((x, y) \in \rho)\}$ и \emph{область значений} $\mbox{rng}\, \rho = \{ x | y \in B \And (\exists x) ((x, y) \in \rho)\}$. Вводится понятие \emph{функциональности} соответствия. Соответствие функционально по первой компоненте тогда и только тогда, когда $\forall (x_1, y_1), (x_2, y_2) \in \rho: y_1 = y_2 \Rightarrow x_1 = x_2$, другими словами: для каждого $y$ существует единственный $x$. Аналогично, соответствие функционально по второй компоненте тогда и только тогда, когда $\forall (x_1, y_1), (x_2, y_2) \in \rho: x_1 = x_2 \Rightarrow y_1 = y_2$, или для каждого $x$ существует единственный $y$. \begin{figure}[tbh] \begin{center} \includegraphics[width=4cm]{nf2k.eps} \caption{Пример соответствия, не функционального по 2-ой компоненте} \label{Pic:corr_graph_2} \end{center} \end{figure} \emph{Отображение} из $A$ в $B$ (функция)~--- это соответствие из $A$ в $B$, которое всюду определено и функционально по второй компоненте. Соответствие~--- это множество упорядоченных пар, поэтому все операции над множествами к ним применимы. Для соответствий вводятся две новые операции: \emph{композиция} и \emph{обратное соответствие}. Композиция соответствий $\rho \subseteq A \times B$ и $\sigma \subseteq B \times C$~--- новое соответствие $\tau \subseteq A \times C$, равное $\tau = \rho \circ \sigma = \{ (x, y) | x \in A, y \in C, \exists z \in B: x \rho z \And z \sigma y \}$. Для конечных соответствий удобно пользоваться графовым представлений соответствий~--- тогда для получения композиции достаточно пройти по рёбрам графа. Пример композиции соответствий представлен на рисунке \ref{Pic:comp_corr} и иллюстрирует композицию соответствий оценок, полученных студентами, ($\rho$) и соответствия оценки получаемой стипендии. Результат композиции в этом случае~--- соответствие студентов и выплаты стипендии. \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{comp_corr.eps} \caption{Пример композиции соответствий} \label{Pic:comp_corr} \end{center} \end{figure} Под \emph{степенью отношения} понимают его композицию с самим собой: $ \rho^2 = \rho \circ \rho$. \emph{Обратное соответствие} образуется следующим образом: $\rho^{-1} \subseteq B \times A$, $\rho^{-1} = \{ (x, y) | (y, x) \in \rho \}$. При этом $\mbox{dom}\, \rho = \mbox{rng}\, \rho^{-1}$ и $\mbox{rng}\, \rho = \mbox{dom}\, \rho^{-1}$. Композиция и обратное соответствие обладают рядом свойств, которые могут быть доказаны методом двух включений. Рассмотрим свойство композиции $\rho \circ (\sigma \cup \tau) = \rho \circ \sigma \cup \rho \circ \tau$. $$ \begin{array}{l} \triangleleft\quad \mbox{Необходимость:}\quad (x, y) \in \rho \circ (\sigma \cup \tau) \Rightarrow\\ (\exists z)((x, z) \in \rho \And (z, y) \in \sigma \cup \tau) \Rightarrow\\ (\exists z)((x, z) \in \rho \And ((z, y) \in \sigma \vee (z, y) \in \tau)) \Rightarrow\\ (\exists z)((x, z) \in \rho \And (z, y) \in \sigma) \vee (\exists z)((x, z) \in \rho \And (z, y) \in \tau) \Rightarrow\\ (x, y) \in \rho \circ \sigma \vee (x, y) \in \rho \circ \tau \Rightarrow (x, y) \in \rho \circ \sigma \cup \rho \circ \tau\\ \mbox{Достаточность доказывается аналогично}\quad\triangleright \end{array} $$ \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Доказать тождества для соответствий. Во втором примере привести контр пример, показывающий, что равенство не может иметь место. \begin{itemize} \item $(\rho \circ \sigma)^{-1} = \sigma^{-1} \circ \rho^{-1}$; \item $\rho \circ (\sigma \cap \tau) \subseteq \rho \circ \sigma \cap \rho \circ \tau$. \end{itemize}\\ \hline \end{tabular} \end{center} \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Для соответствия $\rho \subseteq A \times B$: 1) построить график и граф; найти область определения и область значений; 2) найти $\rho^{-1}$, построить для него график и граф; 3) установить, является ли $\rho$ отображением из $A$ в $B$: \begin{itemize} \item $A = \{1, 2, 3, 4\}, B = \{p, q, r, s, t\}$, $\rho = \{ (1, s), (1, t), (2, r)$, $(2, s)$, $(3, p),(3, q), (4, q), (4, t)\}$; \item $A = B = \{a, b, c, d, e\}, \rho = \{(b,b), (d,c), (c,e), (a, e), (e, a)\}$. \end{itemize}\\ \hline \end{tabular} \end{center} \paragraph{Свойства отображений} Отображение называют \emph{инъективным}, если оно функционально по первой компоненте. На рисунке \ref{Pic:func_noninj} показано неинъективное отображение $ f(x) = x^2$ при $A = \mathbb{R}$, $B = \mathbb{R}^{+}$. Оно не является инъективным, так как значению $y = 1$ соответствуют два $x = 1$ и $x = -1$. \begin{figure}[tbh] \begin{center} \includegraphics[width=6cm]{func_noninj.eps} \caption{Пример неинъективного отображения} \label{Pic:func_noninj} \end{center} \end{figure} Отображение $f: A \rightarrow B$ называют \emph{сюръективным}, если область отображения совпадает с $B$. На рисунке \ref{Pic:func_nonsur} показано несюръетивное отображение $ f(x) = e^x$ при $A = \mathbb{R}$, $B = \mathbb{R}^{+}$. Оно не является сюръективным, так как область значений отображения равна $\mbox{rng}\, f = (0, +\infty)$. Однако, оно инъективно, так как функионально по первой компоненте. \begin{figure}[tbh] \begin{center} \includegraphics[width=6cm]{func_nonsur.eps} \caption{Пример инъективного и несюръективного отображения} \label{Pic:func_nonsur} \end{center} \end{figure} Если отображение инъективно и сюръективно, то оно называется \emph{биективным}. Такое отображение задаёт \emph{взаимно однозначное соответствие} между множествами $A$ и $B$. Пример биекции изображён на рисунке \ref{Pic:func_biject}: если рассмотреть угол, под которым расположен луч, то он соответствует точке на действительной прямой и наоборот. Таким образом, задано биективное отображение интервала $(0, \pi)$ на $\mathbb{R}$. \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{func_biject.eps} \caption{Пример биективного отображения} \label{Pic:func_biject} \end{center} \end{figure} \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Для данных функций $f: A \rightarrow B$ проверить свойства инъективности, сюръективности и биективности. \begin{itemize} \item $A = M_{n \times n}(\mathbb{R}) (\mbox{квадратные матрицы}), B = \mathbb{R}, f(x) = \det x$; \item $A = \mathbb{C} \setminus \{0\}, B = \mathbb{R}^{+} \times [0, 2 \pi), f(z) = (|x|, \arg z)$; \item $A = C[a, b]\, (\mbox{функции, непрерывные на отрезке $[a, b]$}), B = \mathbb{R}, f(x) = \int\limits_a^b x(t)\, dt$. \end{itemize}\\ \hline \end{tabular} \end{center} \paragraph{Бинарные отношения и их свойства} \emph{Бинарное отношение} (отношение)~--- соответствие множества самому себе: $\rho \subseteq A \times A$. Выделим специальное отношение, которое существует для любого множества $A$, называемое \emph{диагональю}: $id_A = \{ (x, x) | x \in A\}$. \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. На множестве $\mathbb{Z}$ задано отношение $<$. Найти квадрат этого отношения. Как изменится ответ, если задать это отношение на $\mathbb{R}$.\\ \hline \end{tabular} \end{center} Свойства бинарных отношений: \begin{enumerate} \item Отношение называют \emph{рефлексивным}, если $(\forall x \in A)((x, x) \in \rho)$. Отношение рефлексивно тогда и только тогда, когда диагональ полностью включается в него $id_A \subseteq \rho$. В качестве примера рефлексивного отношения можно привести $\rho = \{ (x, y) | x = y\}$. \item Отношение называют \emph{иррефлексивным}, если $(\forall x \in A)((x, x) \notin \rho$. Отношение иррефлексивно тогда и только тогда, когда диагональ полностью не принадлежит ему $id_A \cap \rho = \varnothing$. Если отношение не рефлексивно и не иррефлексивно, его называют \emph{нерефлексивным}. Иррефлексивным отношением является $\rho = \{ (x, y) | x \neq y\}$. \item Отношение называют \emph{симметричным}, если $(\forall x, y \in A)(x \rho y \Rightarrow y \rho x)$. При этом график отношения симметричен относительно диагонали, при этом отношение совпадает с обратным к нему $\rho = \rho^{-1}$. Примером такого отношения является равенство треугольников. \item Отношение называют \emph{антисимметричным}, если $(\forall x, y \in A)(x \rho y \And y \rho x \Rightarrow x = y)$. Если отношение не симметрично и не антисимметрично, его называют несимметричным. На графике отношения все симметричные относительно диагонали точки будут лежать на самой диагонали $\rho \cap \rho^{-1} \subseteq id_A$. Пример такого отношения~--- $ x \leqslant y$. \item Отношение называют \emph{транзитивным}, если $(\forall x, y, z \in A)(x \rho y \And y \rho z \Rightarrow x \rho z)$. При этом квадрат отношения включается в него самого $\rho^2 \subseteq \rho$. \end{enumerate} На рисунке \ref{Pic:rel_graphs} показаны примеры отношений с перечисленными свойствами. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{rel_graphs.eps} \caption{Графики, иллюстрирующие свойства отношений} \label{Pic:rel_graphs} \end{center} \end{figure} \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Для заданного бинарного отношения $\rho \subseteq A^2$ 1) построить график; 2) найти $\rho^{-1}$ и $\rho^2$ и построить их графики; 3) исследовать свойства Р, И, С, А, Т. \begin{itemize} \item $A = \{1, 2, 3, 4\}, \rho = \{(1,1), (1, 3)$, $(2, 1), (2, 4)$, $(3, 2), (3,3)$, $(3, 4), (4, 1) \}$; \item $ A = [0, 1], x \rho y \Leftrightarrow |x - y| \leqslant 1 / 3$; \item $ A = [0, 1], x \rho y \Leftrightarrow y \geqslant x + 1/4, x \leqslant 1 /2$. \end{itemize}\\ \hline \end{tabular} \end{center} \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Для заданного бинарного отношения $\rho \subseteq A^2$ 1) найти $\rho^{-1}$ и $\rho^2$; 2) исследовать свойства Р, И, С, А, Т. \begin{itemize} \item $ A = M_{n \times n}(\mathbb{R}), P \rho Q \Leftrightarrow p_{i j} \leqslant q_{i j}, i, j \in \{1, \dots n\}$; \item $ A = M_{n \times n}(\mathbb{R}), P \rho Q \Leftrightarrow \det P = \det Q$; \item $ A = M_{n \times n}(\mathbb{R}), P \rho Q \Leftrightarrow \det P \leqslant \det Q$. \end{itemize}\\ \hline \end{tabular} \end{center} % семинар 2 Рассмотрим пример бинарного отношения, которое изображено на рисунке \ref{Pic:rel_nontrans}. Исследуем свойства Р, И, С, А, Т для этого отношения. \begin{figure}[tbh] \begin{center} \includegraphics[width=14cm]{rel_nontrans.eps} \caption{Пример отношения} \label{Pic:rel_nontrans} \end{center} \end{figure} \begin{description} \item[рефлексивность] диагональ не включается полностью в это отношение, значит оно нерефлексивно; \item[симметричность] график отношения симметричен относительно диагонали, значит это симметричное отношение; \item[транзитивность] транзитивность будем проверять, учитывая тот факт, что для транзитивных отношений выполняется $\rho \circ \rho \subseteq \rho$. Рассмотрим, какие значения принимает отношения при различных $x$. Для этого воспользуемся специальным обозначением \emph{сечения}: $\rho(X) = \{ y | (x, y) \in \rho, x \in X \} = \bigcup\limits_{x \in X} \rho(x)$. На рисунке \ref{Pic:rel_nontrans} показаны значения, которые отношение принимает при различных $x$: $$ \rho\left(\frac{1}{2}\right) = [0, 1], \rho(0) = \rho(1) = \frac{1}{2}, \rho\left(\frac{1}{4}\right) = \left[\frac{1}{4}, \frac{3}{4}\right] $$ Отметим, что $\rho(x)$ для любого $x$ содержит $\frac{1}{2}$, а значит: $$ \begin{array}{l} \rho \circ \rho (0) = \rho \circ \rho (1) = \rho(\rho(0)) = \rho\left(\frac{1}{2}\right) = [0, 1],\\ \rho\left(\rho\left(\frac{1}{4}\right)\right) = \rho\left(\left[\frac{1}{4}, \frac{3}{4}\right]\right) = [0, 1],\\ \dots \end{array} $$ Получается, что $\rho \circ \rho = [0, 1]^2$, а значит $\rho \circ \rho \nsubseteq \rho$, т.е. это отношение не транзитивно. \end{description} Таким образом, это отношение имеет следующие свойства: \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline Р & И& С & А & Т\\ \hline - & - & + & - & -\\ \hline \end{tabular} \end{center} \paragraph{Отношения порядка} Отношения, обладающие свойствами \emph{рефлексивности}, \emph{антисимметричности} и \emph{транзитивности} называют \emph{отношениями порядка}. Исследуем свойства следующего отношения: $\rho \subseteq \mathbb{N}^2, x \rho y \Leftrightarrow x | y$ ($x$ делится нацело на $y$). \begin{description} \item[рефлексивность] $(\forall x)(x = x \Rightarrow x | x)$, рефлексивно; \item[симметричность] Симметричность в общем случае не выполняется (например, для чисел 3 и 1). $x | y \And y | x \Rightarrow x = y$, значит антисимметрично; \item[транзитивность] $$ \left.\begin{array}{r} x | y \Leftrightarrow x = k y, k \in \mathbb{N}\\ y | z \Leftrightarrow y = m z, m \in \mathbb{N} \end{array}\right\} \Rightarrow x = (k m) z, $$ т.е. выпоняется $x | z$, значит отношение транзитивно. \end{description} Обобщим свойства отношения в таблице: \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline Р & И& С & А & Т\\ \hline + & - & - & + & +\\ \hline \end{tabular} \end{center} В упорядоченных множествах два элемента называются \emph{сравнимыми}, если для них можно определить, какой больше, а какой~--- меньше. В случае обычного числового порядка ($\leqslant$) все элементы оказываются сравнимыми, а в рассмотренном выше отношении порядка, например, элементы 2 и 3 не могут быть сравнены. Отношения порядка, при которых все элементы множества сравнимы, называются \emph{линейными}. Для отношений порядка на конечных множествах удобно использовать диаграмме Хассе: элементы множества представляются точками на плоскости, два элемента соединяются линией в том случае, если элементы сравнимы и между ними не может быть помещён ещё один элемент. При этом, большие элементы рисуют выше, а меньшие~--- ниже. На рисунке \ref{Pic:hass_div} показана диаграмма Хассе для рассмотренного выше отношения порядка на различных множествах целых чисел. На диаграмме можно легко увидеть несравнимые элементы и линейный порядок (все элементы выстраиваются в линию). \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{hass_div.eps} \caption{Диаграммы Хассе для отношения порядка делимости} \label{Pic:hass_div} \end{center} \end{figure} Рассмотрим другое отношение порядка: отношения включения теории множеств $\subseteq$ на множестве $2^A$ всех подмножеств множества $A$. Внимательно рассмотрев его свойства, можно увидеть, что это отношение также рефлексивно, антисимметрично и транзитивно. На рисунке \ref{Pic:hass_set} показан пример такого отношения на множестве, образованном тремя множествами $A$, $B$ и $C$ и их объединениями. Диаграмма Хассе в данном случае имеет вид кубика, а отношение порядка не является линейным~--- например, $A$ и $B \cup C$ не могут быть сравнимы, так как нельзя сказать, чтобы одно из этих множеств включалось в другое. \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{hass_set.eps} \caption{Диаграмма Хассе для отношения порядка включения} \label{Pic:hass_set} \end{center} \end{figure} \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Рассмотрим множество слов русского алфавита. Каждое слово состоит из упорядоченного набора букв $x = x_1 x_2 \dots x_n $. Для букв будем использовать стандартный порядок их следования в алфавите. Рассмотрим следующие два отношения: \begin{itemize} \item $x \rho y \Leftrightarrow x_1 < y_1 \vee (x_1 = y_1 \And x_2 < y_2) \vee (x_1 = y_1 \And x_2 = y_2 \And x_3 < y_3) \vee \dots$; \item $x \rho y \Leftrightarrow x_1 \leqslant y_1 \And x_2 \leqslant y_2 \And x_3 \leqslant y_3 \And \dots$. \end{itemize} Докажите, что они являются отношениями порядка. Какое из них является линейным? Изобразите диаграммы Хесса для следующего набора слов: ``бутылка'', ``банан'', ``бисквит'', ``бивень'', ``банджо''.\\ \hline \end{tabular} \end{center} \paragraph{Отношения эквивалентности} Отношения, обладающие свойствами \emph{рефлексивности}, \emph{симметричности} и \emph{транзитивности} называют \emph{отношениями эквивалентности}. Примерами отношения эквивалентности является простое числовое равенство или отношение подобия для треугольников. Исследуем свойства отношения: $ A = M_{n \times n}(\mathbb{R}), \rho \subseteq A^2, P \rho Q \Leftrightarrow \det P = \det Q$, т.е. на множестве квадратных матриц из действительных чисел отношение выполняется, если определители двух матриц равны. Свойства этого отношения вытекают из свойств числового равенства: \begin{description} \item[рефлексивность] $(\forall X)(\det X = \det X)$, рефлексивно; \item[симметричность] $(\forall X, Y)(\det X = \det Y)$, симметрично; \item[транзитивность] $(\forall X, Y, Z)(\det X = \det Y \And \det Y = \det Z) \Rightarrow \det X = \det Z$, транзитивно. \end{description} Отличительным свойством отношений эквивалентности является существование \emph{классов эквивалентности}. Классом эквивалентности элемента $x$ по отношению $\rho \subseteq A^2$ называют множество всех элементов $A$, эквивалентных по данному отношению $x$: $$ [x]_\rho = \{ y | y \in A, x \rho y\} $$ Например, в рассмотренном выше отношении (ограничимся сейчас $n = 2$) можно выделить множество всех матриц, определитель которых равен 1: $$ \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) \rho \left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \\ \end{array} \right), \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) \rho \left( \begin{array}{cc} 0 & -1 \\ 1 & 1 \\ \end{array} \right), \dots $$ Таким образом, для каждого действительного числа $x$ можно построить класс эквивалентности матриц, определитель которых равен $x$: $$ \left[\left( \begin{array}{cc} x & 0 \\ 0 & 1 \\ \end{array} \right)\right]_\rho = \left\{\left( \begin{array}{cc} x & 0 \\ 0 & 1 \\ \end{array}\right), \left( \begin{array}{cc} 2x & 0 \\ 0 & 0.5 \\ \end{array}\right), \dots \right\} $$ Можно доказать, что классы эквивалентности образуют \emph{разбиение} начального множества $A$. Разбиением называется такой набор множеств $A_1$, $A_2$, $\dots$, который удовлетворяет условиям: $ A_1 \cup A_2 \cup \dots \cup A_n \cup \dots = A$ и $ A_1 \cap A_2 \cap \dots \cap A_n \cap \dots = \varnothing$, т.е. множества разбиения не пересекаются и при объединении дают начальное множество. Множество $A$ можно представить в виде объединения классов эквивалентности некоторых его элементов: $A = [x]_\rho \cup [y]_\rho \cup \dots$. В нашем примере множество всех матриц можно разбить на показанные выше классы эквивалентности, эти классы не будет пересекаться, так как в каждом из них определители матриц отличаются. Множество всех классов эквивалентности, задающих разбиение множества $A$, называют \emph{фактор-множеством}, а процесс его построения \emph{факторизацией}. Обозначается фактор-множество следующим образом: $$ \begin{array}{c} A /_\rho = \left\{ \left[\left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} \right)\right]_\rho, \left[\left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right)\right]_\rho, \left[\left( \begin{array}{cc} 2 & 0 \\ 0 & 1 \\ \end{array} \right)\right]_\rho, \dots \right\} = \\ = \left\{ \left.\left[\left( \begin{array}{cc} x & 0 \\ 0 & 1 \\ \end{array} \right)\right]_\rho \right| x \in \mathbb{R}\right\} \end{array} $$ Рассмотрим ещё одно отношение: на множестве целых чисел при заданном $k \in \mathbb{N}$, $\rho \subseteq \mathbb{Z}^2, x \rho y \Leftrightarrow x \equiv_k y$, что означает~--- $x$ и $y$ равны по модулю $k$ или имеют один остаток при делении на $k$. Выясним свойства отношения: \begin{description} \item[рефлексивность] $(\forall x)(x = x) \Rightarrow x \equiv_k x$, рефлексивно; \item[симметричность] $(\forall x, y)(x \equiv_k y \Rightarrow y \equiv_k k)$, симметрично; \item[транзитивность] $$ \left.\begin{array}{r} x \equiv_k y \Leftrightarrow x = n k + r,\, y = m k + r\\ y \equiv_k z \Leftrightarrow y = m k + r,\, z = l k + r \end{array}\right\} \Rightarrow x = n k + r,\, z = l k + r, $$ транзитивно \end{description} Обобщим свойства отношения в таблице. Видно, что это отношение эквивалентности. \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline Р & И& С & А & Т\\ \hline + & - & + & - & +\\ \hline \end{tabular} \end{center} Построим существующие классы эквивалентности: $$ \begin{array}{l} \left[ 0 \right]_{\equiv_k} = \{0, \pm k, \pm 2k, \pm 3k, \dots\},\\ \left[ 1 \right]_{\equiv_k} = \{1, \pm k + 1, \pm 2k + 1, \pm 3k + 1, \dots\},\\ \dots, \\ \left[ k - 1 \right]_{\equiv_k} = \{k - 1, \pm k + k - 1, \pm 2k + k - 1, \pm 3k + k - 1, \dots\} \end{array} $$ Всего $k$ классов эквивалентности, которые задают разбиение всего множества целых чисел. Для $k = 2$ имеем следующие два класса эквивалентности: $$ \begin{array}{l} \left[ 0 \right]_{\equiv_2} = \{0, \pm 2, \pm 4, \dots\},\\ \left[ 1 \right]_{\equiv_2} = \{\pm 1, \pm 3, \pm 5, \dots\}, \end{array} $$ а фактор-множество равно: $$ \mathbb{Z} /_{\equiv_2} = \{\left[ 0 \right]_{\equiv_2}, \left[ 1 \right]_{\equiv_2}\}. $$ \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Доказать, что отношение $\rho \subseteq A^2$ является эквивалентностью. Построить фактор-множество $A /_\rho$. Чем однозначно определяется каждый класс эквивалентности? \begin{itemize} \item $ A = V_3 $ (множество векторов в пространстве), $x \rho y \Leftrightarrow (x - y, \vec{n}) = 0$, где $\vec{n} \neq 0$~--- фиксированный вектор; \item $A = \mathbb{N}^2, (a, b) \rho (c, d) \Leftrightarrow ad = bc$. \end{itemize}\\ \hline \end{tabular} \end{center} \paragraph{Мощности множеств} В основе понятия \emph{мощности} лежит определение \emph{равномощности} множеств. Множество $A$ равномощно множеству $B$, если существует биекция $f: A \rightarrow B$. Биекция задаёт взаимо-однозначное соответствие между множествами, т.е. каждому элементу множества $A$ может быть поставлен один элемент множества $B$ и наоборот. То есть, эти множества как бы (в бесконечном случае так говорить не очень корректно) состоят из одного числа элементов. Равномощность множеств обычно обозначается так: $A \sim B$. Не трудно показать, что это отношение является \emph{эквивалентностью}. А значит, можно выделить классы эквивалентности равномощных множеств, которые совпадают для всех равномощных множеств: $|A| = |B|$, такой класс эквивалентности $|A|$ называют \emph{мощностью} множества $A$. В случае конечных множеств, под мощностью можно понимать натуральное число~--- число элементов множества (для мощностей с одинаковым числом элементов биекция строится тривиально). Однако, в бесконечном случае без построения биекции в доказательстве не обойтись. Любое множество, равномощное множеству натуральных чисел $\mathbb{N}$, называют \emph{счетным}. Мощность счетных множеств обозначается символом $\aleph_0$ (``алеф-ноль''). Любое множество, равномощное множеству натуральных чисел, можно ``пронумеровать'', записав в виде последовательности $a_1, a_2, \dots a_n \dots$. Весьма оригинально, что множество всех положительных чётных чисел $\mathbb{N}_2$, включающееся в множество натуральных чисел $\mathbb{N}$, также счётно (равномощно $\mathbb{N}$). Это доказывается построением элементарной биекции: $f(n) = 2 n, n \in \mathbb{N}$. Другой забавный пример~--- множество $\mathbb{N} \times \mathbb{N}$ (точки на плоскости с целыми положительными координатами) также счётно; биекция здесь чуть более сложна~--- она задаётся нумерацией всех точек плоскости из угла $(1,1)$ по расширяющимся диагоналям (см. рисунок \ref{Pic:set_power}). Очевидно, что $\mathbb{Z}$ и $\mathbb{Q}$ также счётны. \begin{figure}[tbh] \begin{center} \includegraphics[width=5cm]{set_power.eps} \caption{Нумерация множества $\mathbb{N} \times \mathbb{N}$} \label{Pic:set_power} \end{center} \end{figure} Для счетных множеств существует ряд интересных теорем: \begin{itemize} \item любое бесконечное множество содержит счётное подмножество; \item любое подмножество счётного множества конечно или счётно; \item объединение не более чем счётного семейства счётных множеств счётно; \item объединение конечного и счётного множества счётно. \end{itemize} Однако, множество всех действительных чисел не является счётным (это довольно элементарно доказал Кантор). Кроме того, равномощными являются следующие множества: всех двоичных последовательностей, всех подмножеств множества $\mathbb{N}$ и всех действительных чисел: $$ \{0, 1\}^\omega \sim 2^{\mathbb{N}} \sim (0, 1) \sim \mathbb{R}. $$ Мощность этих множеств называют \emph{мощностью континуума}. На самом деле, для любого множества $A$ мы можем легко получить множество с большей мощностью. Для этого достаточно рассмотреть множество $2^A$. \section{Алгебраические структуры} \emph{Алгебраическая структура} (алгебра)~--- множество с операциями на нём. Обозначается следующим образом: $\mathcal{A} (A, \Omega)$, где $\Omega$~--- набор операций, называемый \emph{сигнатурой}. \emph{Операция}~--- произвольное отображение $\omega: A^n \rightarrow A$. Выделяют унарные операции ($n = 1$), бинарные операции ($n = 2$), тернарные операции ($n = 3$). Также иногда представляют особый интерес некоторые элементы множества $A$, при этом они могу добавляться в сигнатуру, превращаясь в так называемые \emph{нулярные} операции. Чаще всего встречаются бинарные операции, они могу обладать следующими свойствами: \begin{description} \item[коммутативность] $(\forall x, y \in A)(x * y = y * x)$; \item[ассоциативность] $(\forall x, y, z \in A)(x * (y * z) = (x * y) * z)$; \item[идемпотентность] $(\forall x \in A)(x * x = x)$. \end{description} Примеры алгебр: \begin{itemize} \item $\mathcal{N} (\mathbb{N}, \{+, \cdot\})$~--- сложение и умножение на множестве натуральных чисел; \item $\mathcal{B}_A (2^A, \{\cup, \cap, \setminus, \neg, \varnothing, A\})$~--- операции над множеством всех подмножеств множества $A$, два элемента из $2^A$: $\varnothing$ и $A$ были специально выделены; \item $\mathcal{V} (V_3, \{+, \cdot \alpha (\alpha \in \mathbb{R})\})$~--- множество векторов в пространстве с операциями сложения и умножения на число~--- эта агебра интересна тем, что её сигнатура бесконечна. \end{itemize} Примеры не-алгебр: \begin{itemize} \item $\mathcal{R} (\mathbb{R}, \{ +, \cdot, / \})$~--- не алгебра, так как деление определено не для всех пар чисел из $\mathbb{R}$; \item $\mathcal{M} (M \rightarrow M, \{ \circ, {}^{-1}\})$~--- не алгебра, так как не для каждого отображения $M \rightarrow M$ существует обратное отображение. \end{itemize} \paragraph{Группы} Любая алгебра с одной бинарной операцией $\mathcal{A} (A, *)$ называется \emph{группоидом}. Примеры группоида: $(\mathbb{N}, +)$~--- сложение натуральных чисел или $(V_3, \times)$~--- множество векторов в пространстве с операцией векторного произведения. Группоид, операция которого обладает \emph{ассоциативностью}, называется \emph{полугруппой}. Примером полугруппы является алгебра бинарных отношений на множестве $M$ с операцией композиции $(2^{M \times M}, \circ)$ или та же алгебра $(\mathbb{N}, +)$. А вот алгебра векторов с векторным произведением полугруппой уже не является, так как векторное произведение неассоциативно. Если $\mathcal{A} (A, *)$~--- полугруппа и существует такое $\varepsilon \in A$, что $(\forall x \in A)(x * \varepsilon = \varepsilon * x = x)$, то такая полугруппа называется \emph{моноидом}, а элемент $\varepsilon$~--- нейтральным элементом. Обычно, нейтральный элемент записывается в сигнатуре. Можно доказать, что если полугруппа имеет нейтральный элемент, то он является единственным. Примером моноида является множество натуральных чисел с операцией умножения $(\mathbb{N}, \cdot, 1)$. А полугруппа натуральных чисел со сложением должна быть дополнена нулём, чтобы стать моноидом: $(\mathbb{N}_0, +, 0)$. Также моноид образуют теоретико-множественные операции объединения и пересечения: $(2^A, \cup, \varnothing)$ и $(2^A, \cap, A)$. Пусть $\mathcal{M} (M, *, \varepsilon)$~--- произвольный моноид, тогда $x' \in M$ называется обратным элементом к $x \in M$, если $ x * x' = x' * x = \varepsilon$. Моноид называется \emph{группой}, если каждый элемент в нём имеет обратный. Можно доказать, что в группе для любого элемента существует единственный обратный элемент, или $(x')' = x$. Примером группы является множество целых чисел с операцией сложения: $(\mathbb{Z}, +, 0)$, при этом обратным элементом к любому числу является его отрицание. Можно увидеть, откуда взялось название \emph{полугруппы}~--- если мы возьмём две полугруппы натуральных и отрицательных чисел $(\mathbb{N}, +)$ и $(\mathbb{N}^-, +)$ и объединим их с добавлением нейтрального элемента $0$, то получим полную группу. Также группой является множество всех невырожденных матриц $(\mathcal{M}^+, \cdot, E, {}^{-1})$ с операцией умножения. В этом случае обратная матрица является обратным элементом к любой матрице (она существует, так как матрицы невырождены). В группе можно решать уравнения вида $a * x = b$ или $x * a = b$, решением которых будет соответственно $x = a' * b$ и $x = b * a'$. Группа, операция которой коммутативна, называется \emph{абелева группа}. \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Задана алгебра $(X, *)$ с одной бинарной операцией. Проверить свойства этой операции и указать, к какому типу эта алгебра относится. \begin{itemize} \item $X = \mathbb{N}, x * y = x^y$; \item $X = \mathbb{N}, x * y = \mbox{НОК}(x, y)$; \item $X = \mathbb{R}, x * y = x$; \item $X$~--- множество диагональных матриц порядка $n$, $x * y$~--- произведение матриц; \item $X = 2^A, x * y = A \setminus B$. \end{itemize}\\ \hline \end{tabular} \end{center} \emph{Группа вычетов} Особый интерес представляют группа следующего вида: $\mathbb{Z}_K^+ (\{0, 1, 2, \dots, k - 1\}, \oplus_k, 0)$, где $\oplus_k$~--- операция сложения по модулю $k$ (остаток от деления $x + y$ на $k$). Такая группа называется \emph{аддитивной группой вычетов}. Аналогичная группа (при исключении нуля из множества алгебры) с операцией умножения по модулю $k$ $\mathbb{Z}_K^* (\{1, 2, \dots, k - 1\}, \odot_k, 1)$ называется \emph{мультипликативной группой вычетов}. В мультипликативной группе вычетов элемент образует \emph{замыкание} относительно операции умножения. Например, в $\mathbb{Z}_5^* (\{1, 2, 3, 4\}, \odot_5, 1)$: $$ \begin{array}{l} 3^1 = 3\\ 3^2 = 3 \odot_5 3 = 4\\ 3^3 = 3 \odot_5 3 \odot_5 3 = 4 \odot_5 3 = 2\\ 3^4 = 2 \odot_5 3 = 1\\ 3^5 = 1 \odot_5 3 = 3 = 3^1 \end{array} $$ Значит, $3^{2006}$ в этой группе вычисляется легко: $3^{2006} = 3^{2004} \odot_5 3^2 = (3^4)^{501} \odot_5 4 = 4$. \paragraph{Группа перестановок} Рассмотрим конечное множество $A = \{1, 2, \dots, n\}$, состоящее из $n$ элементов. Перестановкой называется биекция $A \rightarrow A$. Перестановка записывается в виде: $$ \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ i_1 & i_2 & \dots & i_n \end{array} \right), $$ где $i_1, \dots i_n \in A$. На множестве перестановок можно определить операцию \emph{композиции}: $$ \sigma = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ i_1 & i_2 & \dots & i_n \end{array} \right), \tau = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ j_1 & j_2 & \dots & j_n \end{array} \right), \tau \circ \sigma = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ k_1 & k_2 & \dots & k_n \end{array} \right), $$ где $k_s = \tau(\sigma(s)) = \tau(i_s) = j_{i_s}$. Для каждой перестановки можно получить \emph{обратную перестановку}: $$ \sigma = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ i_1 & i_2 & \dots & i_n \end{array} \right), \sigma^{-1} = \left( \begin{array}{cccc} i_1 & i_2 & \dots & i_n\\ 1 & 2 & \dots & n \end{array} \right) $$ Множество всех перестановок степени $n$ образуют группу по операции композиции, при этом нейтральным элементом является тождественная перестановка: $$ \left( A \rightarrow A, \circ, \varepsilon \right), \varepsilon = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ 1 & 2 & \dots & n \end{array} \right) $$ Такая группа называется \emph{группой перестановок}. Рассмотрим уравнение над этой группой: $$ \begin{array}{c} \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2 \end{array} \right) \circ X \circ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 4 & 2 & 1 & 3 \end{array} \right) = \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{array} \right)\\ X = \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2 \end{array} \right)^{-1} \circ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{array} \right) \circ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 4 & 2 & 1 & 3 \end{array} \right)^{-1} = \\ = \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2 \end{array} \right) \circ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{array} \right) \circ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 3 & 2 & 4 & 1 \end{array} \right) =\\ = \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 3 & 1 & 2 & 4 \end{array} \right) \circ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 3 & 2 & 4 & 1 \end{array} \right) = \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{array} \right) \end{array} $$ % семинар 3 \paragraph{Исследование группоидов} Рассмотрим ещё один пример группоида и исследуем свойства его бинарной операции. $\mathcal{A}(\mathbb{R}, \circ)$, где $(\forall x, y) (x \circ y = y)$. Очевидно, что эта операция \emph{некоммутативна}, так как $x \circ y = y \neq y \circ x = x$. С другой стороны, \emph{ассоциативность} может быть доказана следующим образом: $$ \begin{array}{l} x \circ (y \circ z) = x \circ z = z\\ (x \circ y) \circ z = y \circ z = z \end{array} $$ Значит, это полугруппа. При попытке найти нейтральный элемент, получим: $$ x \circ \varepsilon = x \Leftrightarrow \varepsilon = x, $$ это значит, что нейтральный элемент не существует, и данная алгебра - не моноид. \paragraph{Кольца, тела и поля} Алгебраическую структуру с двумя бинарными операциями $\mathcal{R}(R, +, \cdot, 0, 1)$ называется \emph{кольцом}, если выполняются следующие соотношения: \begin{itemize} \item $a + (b + c) = (a + b) + c$; \item $a + b = b + a$; \item $a + 0 = a$; \item $(\forall a)(\exists -a: a + (-a) = 0)$; \item $a \cdot (b \cdot c) = (a \cdot b) \cdot c$; \item $a \cdot 1 = 1 \cdot a = a$; \item $a \cdot (b + c) = a \cdot b + a \cdot c$ и $(a + b) \cdot c = a \cdot c + b \cdot c$. \end{itemize} Другими словами, алгебра $(R, +, 0)$ является \emph{абелевой группой}, алгебра $(R, \cdot, 1)$~--- \emph{моноидом}, а операция умножения дистрибутивна относительно сложения. Можно доказать, что в кольце имеет место аннулирующее свойство нуля: $a \cdot 0 = 0 \cdot a = 0$. В качестве примеров колец можно привести: \begin{itemize} \item кольцо действительных чисел с привычными операциями сложения и умножения~--- $(\mathbb{R}, +, \cdot, 0, 1)$. Действительно, по сложению имеем абелеву группу, тогда как по умножению~--- лишь моноид (обратный к нулю элемент не определён). \item кольцо квадратных матриц степени $n$~--- $(M_n, +, \cdot, 0, E)$, где $0$ и $E$~--- соответственно нулевая и единичная матрица. Также только моноид по умножению, потому что обратная матрица существует не для каждой квадратной матрицы. \end{itemize} В некоторых кольцах существуют \emph{делители нуля}, т.е. такие элементы $a, b \neq 0$, что $ a \cdot b = 0$. Для обычной арифметики это кажется удивительным и не выполняется, тогда как для приведённого выше примера кольца матриц можно найти делители нуля: $$ \left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{array} \right) \cdot \left( \begin{array}{cc} 0 & 0 \\ 0 & 1 \\ \end{array} \right) = \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \\ \end{array} \right) $$ Кольцо без делителей нуля называется \emph{областью целостности}. Пример такой алгебры~--- кольцо целых чисел с операциями сложения и умножения. Кольцо без делителей нуля, множество ненулевых элементов которого является группой по умножению, называется \emph{телом}. Тело с коммутативной операцией умножения называется \emph{полем}. Кольца рациональных, действительных и комплексных чисел с операциями арифметического сложения и умножения являются полями. \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Задана алгебра $(X, +, *)$ с двумя бинарными операциями. Проверить свойства этой операции и указать, к какому типу эта алгебра относится. \begin{itemize} \item $X = M_n^d$~--- множество диагональных матриц степени $n$; \item $X = 2^A$, $+$~--- $\bigtriangleup$, симметрическая разность множеств, а $*$~--- $\cap$, пересечение множеств; \item $X = \mathbb{R}[x]$~--- множество многочленов от переменной $x$ с действительными коэффициентами. \end{itemize}\\ \hline \end{tabular} \end{center} \paragraph{Кольцо вычетов} Важным примером кольца является \emph{кольцо вычетов} по модулю $k$: $\mathbb{Z}_k(\{0, 1, \dots, k - 1\}, \oplus_k, \odot_k, 0, 1)$. Для разных $k$ это кольцо может обладать разными свойствами. Рассмотрим два случая: $k = 4$ и $k = 5$. При $k = 4$ имеем следующие таблицы сложения и умножения по модулю 4: \begin{center} \begin{tabular}{cc} \begin{tabular}{|c|c|c|c|c|} \hline $\oplus_4$ & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 1 & 2 & 3\\ \hline 1 & 1 & 2 & 3 & 0\\ \hline 2 & 2 & 3 & 0 & 1\\ \hline 3 & 3 & 0 & 1 & 2\\ \hline \end{tabular} & \begin{tabular}{|c|c|c|c|c|} \hline $\odot_4$ & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 1 & 2 & 3\\ \hline 2 & 0 & 2 & 0 & 2\\ \hline 3 & 0 & 3 & 2 & 1\\ \hline \end{tabular} \\ \end{tabular} \end{center} Видно, что элемент 2 является делителем нуля: $2 \odot_4 2 = 0$. При $k = 5$ имеем следующие таблицы сложения и умножения по модулю 5: \begin{center} \begin{tabular}{cc} \begin{tabular}{|c|c|c|c|c|c|} \hline $\oplus_5$ & 0 & 1 & 2 & 3 & 4\\ \hline 0 & 0 & 1 & 2 & 3 & 4\\ \hline 1 & 1 & 2 & 3 & 4 & 0\\ \hline 2 & 2 & 3 & 4 & 0 & 1\\ \hline 3 & 3 & 4 & 0 & 1 & 2\\ \hline 4 & 4 & 0 & 1 & 2 & 3\\ \hline \end{tabular} & \begin{tabular}{|c|c|c|c|c|c|} \hline $\odot_5$ & 0 & 1 & 2 & 3 & 4\\ \hline 0 & 0 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 1 & 2 & 3 & 4\\ \hline 2 & 0 & 2 & 4 & 1 & 3\\ \hline 3 & 0 & 3 & 1 & 4 & 2\\ \hline 4 & 0 & 4 & 3 & 2 & 1\\ \hline \end{tabular} \end{tabular} \end{center} Здесь делителей нуля нет, а для каждого ненулевого элемента можно найти обратный по умножению: $1^{-1} = 1, 2^{-1} = 3, 3^{-1} = 2, 4^{-1} = 4$. Т.е. данное кольцо вычетов является полем. Можно доказать, что кольцо вычетов является полем тогда и только тогда, когда $k$~--- простое число. В кольцах вычетов можно решать уравнения и системы уравнений. Например решим данные уравнения в кольце $\mathbb{Z}_7$, для простоты умножение и сложение по модулю 7 будем обозначать стандартными знаками полюса и умножения: $$ \left\{\begin{array}{ll} 2 x + 3 y = 1,\\ 3 x - y = 2 \end{array}\right. \left\{\begin{array}{ll} y = 3 x - 2,\\ 2 x + 3 (3 x - 2) = 1 \end{array}\right. \left\{\begin{array}{ll} y = 3 x - 2,\\ 4 x = 0, x = 0 \end{array}\right. $$ $$ \left\{\begin{array}{ll} x = 0,\\ y = 5 \end{array}\right. $$ или в кольце вычетов $\mathbb{Z}_5$: $$ \begin{array}{c} x^3 + x^2 + 4 x - 1 = 0\\ x^3 + x^2 + 4 x + 4 = 0\\ x^2 (x + 1) + 4 (x + 1) = 0\\ (x + 1)(x^2 + 4) = 0\\ x_1 = 4,\\ x_2^2 = 1, x_2 = 1 \end{array} $$ \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Решить систему уравнений или алгебраическое уравнение в полях $\mathbb{Z}_5$ и $\mathbb{Z}_7$: \begin{itemize} \item $ \left\{\begin{array}{ll} -4 x + 3 y = 1,\\ x + 2 y = 3 \end{array}\right.$ \item $ \left\{\begin{array}{ll} -x + 3 y = 1,\\ 3 x + y = 2 \end{array}\right.$ \item $x^3 - x + 1 = 0$. \end{itemize}\\ \hline \end{tabular} \end{center} \paragraph{Подалгебры} Пусть дана алгебра $\mathcal{A}(A, \Omega)$ и множество $B \subset A$, такое, что $\mathcal{B}(B, \Omega)$~--- тоже алгебра с теми же операциями. Тогда $\mathcal{B}$~--- подалгебра $\mathcal{A}$. В качестве примеров подалгебр можно привести: \begin{itemize} \item группу $(\mathbb{Q}, +, 0)$ и её подгруппу $(\mathbb{Z}, +, 0)$; \item кольцо $(\mathbb{R}, +, \cdot, 0, 1)$ и его подкольцо $(\mathbb{Z}, +, \cdot, 0, 1)$. \end{itemize} А вот алгебра $(\mathbb{N}_0, +, 0)$ не является подгруппой $(\mathbb{Z}, +, 0)$, так как не обладает свойствами группы (является лишь моноидом и соответственно подмоноидом $(\mathbb{Z}, +, 0)$). \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задания для самоподготовки}. Для данной группы (кольца) $M$ поверить, является ли $H$ её подгруппой (подкольцом): \begin{itemize} \item $M = (\mathbb{C} \setminus \{ 0 \}, \cdot), H = \{ x \in \mathbb{R}, x > 0 \}$; \item $M = (C[a, b], +, \cdot)$, $C$~--- класс функций, непрерывных на отрезке, $H = \{ f \in C[a, b]: f(a) + f(b) = 0 \}$; \item $M = (V_3, +), H = \{ \vec{a} \in V_3; (\vec{a}, \vec{n}) = 0 \}$ ($\vec{n}$~--- заданный вектор). \end{itemize}\\ \hline \end{tabular} \end{center} \paragraph{Полукольца} Определение \emph{полукольца} аналогично определению \emph{полугруппы}~--- снимается требование существования обратного элемента по сложению (из двух полуколец можно получить кольцо, как и в случае группы): \begin{itemize} \item $a + (b + c) = (a + b) + c$; \item $a + b = b + a$; \item $a + 0 = a$; \item $a \cdot (b \cdot c) = (a \cdot b) \cdot c$; \item $a \cdot 1 = 1 \cdot a = a$; \item $a \cdot (b + c) = a \cdot b + a \cdot c$ и $(a + b) \cdot c = a \cdot c + b \cdot c$; \item $a \cdot 0 = 0 \cdot a = 0$; \end{itemize} Если операция сложения в полукольце \emph{идемпотентна}: $x + x = x$, то такое полукольцо называют \emph{идемпотентным полукольцом}, иногда их называют просто \emph{полукольцами}. Пример такого полукольца: $$ \mathcal{R}^+ = (\mathbb{R}^+ \cup \{ +\infty \}, \min, +, +\infty, 0) $$. Действительно, операция взятия минимума идемпотентна и $+\infty$ является по ней нейтральным элементом. Если операция умножения обладает также свойствами идемпотентности и коммутативности, то такое полукольцо называют \emph{симметричным}. Пример симметричного полукольца: алгебра подмножеств множества $mathcal{A} = (2^A, \cup, \cap, \varnothing, A)$. \paragraph{Булевы алгебры} Симметричное полукольцо, в котором для каждого элемента $x$ существует дополнение $\overline{x}$ такое, что $x + \overline{x} = 1$ и $x \cdot \overline{x} = 0$, называется \emph{булевой алгеброй}. Самый распространённым примером булевой алгебры является двухэлементная булева алгебра: $\mathcal{B} (\{0, 1\}, \vee, \wedge, 0, 1)$. Интересно, что приведённое выше симметричное полукольцо подмножеств множества $A$ также является булевой алгеброй, в которой дополнение определяется как $\overline{X} = A \setminus X$. Также представляет интерес $n$-компонентная булева алгебра: $$ \mathcal{B} (\{0, 1\}^n, \vee, \wedge, \mathbf{0}, \mathbf{1}), $$ где операции $\vee$ и $\wedge$ определены на булевых векторах из $n$ элементов, а $\mathbf{0}$ и $\mathbf{1}$~--- соответственно нулевой и единичный вектор. Нетрудно показать, что это также булева алгебра. В $n$-элементной булевой алгебре определяется стандартное отношение порядка (покомпонентное сравнение): $\overline{\alpha} \leqslant \overline{\beta} \Leftrightarrow \alpha_i \leqslant \beta_i, i = \overline{1, n}$. Диаграммы Хассе для этого отношения булевой алгебры первого, второго и третьего порядка показаны на рисунке \ref{Pic:hass_bool}. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{hass_bool.eps} \caption{Диаграмма Хассе для стандартного отношения порядка булевой алгебры} \label{Pic:hass_bool} \end{center} \end{figure} На базисе булевых алгебр (в первую очередь, двухэлементной булевой алгебры) строится теория \emph{булевых функций}. \section{Булевы функции} Булева функция~--- это отображение вида $f: \{0, 1\}^n \rightarrow {0, 1}$, где $n$~--- число булевых переменных. В общем случае это скалярная функция векторного переменного. Важное свойство булевых функции~--- их число конечно для заданного $n$ и равно $2^{2^n}$. То есть, каждая функция может быть задана своей \emph{таблицей истинности} или просто \emph{пронумерована}. При $n = 0$ существует только две функции-константы: 0 и 1. Рассмотрим все функции для $n = 1$: \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline $x$ & $f_1$ & $f_2$ & $f_3$ & $f_4$\\ \hline 0 & 0 & 0 & 1 & 1\\ \hline 1 & 0 & 1 & 0 & 1\\ \hline \end{tabular} \end{center} $f_1(x) = 0, f_4(x) = 1$~--- константы, $f_2(x) = x$~--- тождественная функция, $f_3(x) = \overline{x}$~--- дополнение. Рассмотрим все функции для $n = 2$: \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline $x_1$ & $x_2$ & $f_1$ & $f_2$ & $f_3$ & $f_4$ & $f_5$ & $f_6$ & $f_7$ & $f_8$ & $f_9$ & $f_{10}$ & $f_{11}$ & $f_{12}$ & $f_{13}$ & $f_{14}$ & $f_{15}$ & $f_{16}$\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ \hline \end{tabular} \end{center} $f_1(x_1, x_2) = 0, f_{16}(x_1, x_2) = 1$~--- константы, $f_2(x_1, x_2) = x_1~\wedge~x_2$~--- конъюнкция, $f_7(x_1, x_2) = x_1~\oplus~x_2$~--- исключающее или, $f_8(x_1, x_2) = x_1~\vee~x_2$~--- дизъюнкция, $f_9(x_1, x_2) = x_1~\downarrow~x_2$~--- стрелка Пирса, $f_{10}(x_1, x_2) = x_1~\sim~x_2$~--- эквивалентность, $f_{14}(x_1, x_2) = x_1~\rightarrow~x_2$~--- импликация, $f_{15}(x_1, x_2) = x_1~|~x_2$~--- штрих Шефера. Таким образом, каждая булева функция может быть представлена в виде таблицы истинности, так и в виде формулы. \paragraph{ДНФ} Элементарная конъюнкция~--- формула вида $x_i^{\alpha_i} \wedge x_j^{\alpha_j} \wedge \dots x_k^{\alpha_k}$, где при $\alpha_i = 0$ используется дополнение переменной, а при $\alpha_i = 1$~--- сама переменная. Пример элементарной конъюнкции: $ x_1 \overline{x_3} x_4 $. Дизъюнктивная нормальная форма~--- это формула вида $K_1 \vee K_2 \vee \dots K_m$, где $K_i$~--- элементарная конъюнкция. Можно доказать, что любая функция может быть представлена в виде ДНФ. \paragraph{Карта Карно} Для иллюстрации значения булевой функции, а также для получения её ДНФ используются \emph{карты Карно}~--- форма изображения булевой функции в виде таблицы, строки и столбцы которой обозначают отдельные переменные. Например, карта Карно для функции от трёх переменных $f = (0 0 1 0 1 1 1 0)$ будет иметь вид: \begin{center} \begin{tabular}{|lr|c|c|c|c|} \hline & $x_2$ $x_3$ & 0 0 & 0 1 & 1 1 & 1 0\\ $x_1$ & & & & &\\ \hline 0 & & 0 & 0 & 0 & 1\\ \hline 1 & & 1 & 1 & 0 & 1\\ \hline \end{tabular} \end{center} Отметим, что значение переменных в соседних столбцах и строках карты Карно должны быть сравнимы. Для каждой единицы в карте Карно можно выписать элементарную коньнкцию, с помощью которой она получается~--- например, единица при $x_1 = 0$ и $ x_2 x_3 = 1 0$ может быть представлена в виде конъюнкции $\overline{x_1} x_2 \overline{x_3}$. Дизъюнкция всех таких конъюнкций, соответствующих единицам, даст нам ДНФ данной функции. \paragraph{Минимизация ДНФ} Минимальной булевой функцией называется функция, ДНФ которой содержит минимальное число элементарных конъюнкций (а если число конъюнкций равно, то число переменных в конъюнкциях меньше). Алгоритм минимизации булевой функции состоит из следующих этапов: \begin{enumerate} \item Построение карты Карно для заданной функции. \item Выделение \emph{склеек}. Склейка~--- область, покрывающая только единицы на карте Карно, размер которой равен степени двух. Такая область может быть представлена в виде элементарной конъюнкции. При этом необходимо выделять склейки максимально большого размера. Дизъюнкция всех конъюнкций склеек даёт \emph{сокращённую ДНФ}. \item Определение \emph{ядра}. Ядро~--- набор склеек, каждая из которых покрывает единицы, не покрываемые ни одной другой склейкой. Такие склейки называют \emph{ядровыми}. Если в ядро входят все склейки, то минимальная ДНФ равна сокращённой, конец алгоритма. \item Если существуют склейки, целиком попадающие в ядро, их можно выбросить. В результате получится \emph{ДНФ Квайна}. \begin{enumerate} \item Если ядро покрывает все единицы, то минимизация закончена. \item Если есть единицы, не покрываемые ядерными склейками, то строится \emph{функция Патрика}: для каждой из таких единиц строится дизъюнкция вида $K_1 \vee K_2 \vee \dots K_m$, где $K_i$~--- конъюнкция склейки, покрывающецй данную единицу. Такие дизъюнкции объединяются в общую конъюнкцию, которая и носит название функции Патрика. После раскрытия скобок и сокращения получается дизъюнкция нескольких наборов конъюнкций, каждый из таких наборов представляет собой отдельную альтернативу, покрывающую все единицы, не попавшие в ядро. Каждая такая альтернатива, объединённая с ядром, даёт одну из возможных минимальных ДНФ, или одну из \emph{тупиковых} ДНФ. \end{enumerate} \end{enumerate} Рассмотрим пример минимизации булевой функции $f = (0 0 1 0 1 1 1 0)$. На рисунке \ref{Pic:karno_1} показана карта Карно для этой функции. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{karno_1.eps} \caption{Пример минимизации ДНФ с помощью карты Карно} \label{Pic:karno_1} \end{center} \end{figure} Всего можно выделить три склейки: $K_1$, $K_2$ и $K_3$. В ядро входят $K_1$ и $K_3$, тогда как $K_2$ может быть выброшена. В данном случае ДНФ Квайна и минимальная ДНФ совпадают: $ f = K_1 \vee K_3 = x_2 \overline{x_3} \vee x1 \overline{x_2}$. На рисунке \ref{Pic:karno_2} показана карта Карно похожей функции. В этом случае ядро $K_1$ и $K_4$ не покрывает все единицы функции. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{karno_2.eps} \caption{Пример минимизации ДНФ с помощью карты Карно} \label{Pic:karno_2} \end{center} \end{figure} Для единицы на пересечении $K_2$ и $K_3$ функция Патрика будет иметь вид: $K_2 \vee K_3$. Дальнейшее упрощение не возможно, имеем две альтернативы. Значит, тупиковые ДНФ можно записать в виде: $$ f = K_1 \vee K_4 \vee \left\{ \begin{array}{l} K_2\\ K_3 \end{array}\right. = \overline{x_2} x_3 \vee x_2 \overline{x_3} \vee \left\{ \begin{array}{l} x_1 x_3\\ x_1 x_2 \end{array}\right. $$ Бывают ситуации, когда в ядро не входит ни одна склейка. Например, для функции, показанной на рисунке \ref{Pic:karno_3}. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{karno_3.eps} \caption{Пример минимизации ДНФ с помощью карты Карно} \label{Pic:karno_3} \end{center} \end{figure} В этом случае функция Патрика будет иметь шесть сомножителей~--- по одному на единицу: Ф.П. = $(K_1 \vee K_2) (K_2 \vee K_3) (K_3 \vee K_4) (K_4 \vee K_5) (K_5 \vee K_6) (K_6 \vee K_1)$ = $(K_1 K_2 \vee K_2 \vee K_2 K_3 \vee K_1 K_3) (K_3 K_4 \vee K_4 \vee K_3 K_5 \vee K_4 K_5) (K_5 \vee K_6)$ = $(K_2 \vee K_1 K_3) (K_4 \vee K_3 K_5) (K_5 \vee K_6)$ = $(K_2 K_4 \vee K_1 K_3 K_4 \vee K_1 K_3 K_5 \vee K_2 K_3 K_5) (K_5 \vee K_6)$ = $K_2 K_4 K_6 \vee K_1 K_3 K_5 $. В результате имеем две альтернативы, две тупиковые ДНФ: $$ f = \left\{ \begin{array}{l} K_1 \vee K_3 \vee K_5\\ K_2 \vee K_4 \vee K_6 \end{array}\right. = \left\{ \begin{array}{l} \overline{x_1} \overline{x_2} \vee x_1 x_3 \vee x_2 \overline{x_3}\\ \overline{x_2} x_3 \vee x_1 x_2 \vee \overline{x_1} \overline{x_3} \end{array}\right. $$ % семинар 4 \paragraph{Системы булевых функций. Базис Жегалкина} Конечное множество булевых функций $\mathcal{F} = \{ f_1, f_2, \dots f_n \}$ называют \emph{системой булевых функций}. Систему булевых функций называют \emph{полной}, если \emph{любая} булева функция может быть выражена в виде формулы над этой системой (другими словами, если она представима через функции данной системы). Примером полной системы является так называемый \emph{стандартный базис}, содержащий дизъюнкцию, конъюнкцию и отрицание: $\mathcal{F}_0 = \{ \vee, \wedge, \overline{\phantom{x}} \}$. Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде ДНФ или КНФ. А учитывая, что $x \vee y = \overline{\overline{x} \wedge \overline{y}}$ и $x \wedge y = \overline{\overline{x} \vee \overline{y}}$, полными являются даже системы $\{ \vee, \overline{\phantom{x}}\}$ и $\{ \wedge, \overline{\phantom{x}}\}$. Другой распространённой полной системой булевых функций является \emph{базис Жегалкина}: $\mathcal{F}_{\mbox{Ж}} = \{ \oplus, \cdot, 1 \}$, включающий исключающее или, конъюнкцию и константу 1. Можно доказать, что любая булева функция представима в виде так называемого \emph{полинома Жегалкина}: $$ f(x_1, \dots x_n) = \sum\limits_{\begin{array}{c} i_1, i_2, \dots i_k \in \{1, \dots n\}\\ k \in \overline{1, n}\end{array} } a_{i_1, i_2, \dots i_k} x_{i_1} x_{i_2} \dots x_{i_k} \oplus a_0, $$ где $a_j \in \{0, 1\}$. В частном случае, полином Жегалкина имеет линейный вид: $$ f(x_1, \dots x_n) = \sum\limits_{i \in \overline{1, n}} a_i x_i \oplus a_0. $$ Булева функция, представимая в виде линейного полинома Жегалкина, называется \emph{линейной}. Существует простой способ выражения любой булевой функции над базисом Жегалкина. Этот способ носит название \emph{метода неопределённых коэффициентов}. Рассмотрим этот метод на примере: Рассмотрим функцию $ f(x_1, x_2, x_3) = (0 0 1 1 1 0 0 1) $. В общем виде полином Жегалкина для этой функции имеет вид: $$ f(x_1, x_2, x_3) = a_{1 2 3} x_1 x_2 x_3 \oplus a_{1 2} x_1 x_2 \oplus a_{2 3} x_2 x_3 \oplus a_{1 3} x_1 x_3 \oplus a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3 \oplus a_0 $$ Вычислим все коэффициенты начиная с $a_0$, последовательно подставляя в полином известные значения функции $f$: $$ \begin{array}{l} f (0, 0, 0) = a_0 = 0,\\ f (0, 0, 1) = a_3 \oplus a_0 = a_3 = 0,\\ f (0, 1, 0) = a_2 \oplus a_0 = a_2 = 1,\\ f (1, 0, 0) = a_1 \oplus a_0 = a_1 = 1,\\ f (0, 1, 1) = a_{2 3} \oplus a_2 \oplus a_3 \oplus a_0 = a_{2 3} \oplus 1 = 1 \Rightarrow a_{2 3} = 0,\\ f (1, 0, 1) = a_{1 3} \oplus a_1 \oplus a_3 \oplus a_0 = a_{1 3} \oplus 1 = 0 \Rightarrow a_{1 3} = 1,\\ f (1, 1, 0) = a_{1 2} \oplus a_1 \oplus a_2 \oplus a_0 = a_{1 2} = 0,\\ f (1, 1, 1) = a_{1 2 3} \oplus a_{1 2} \oplus a_{2 3} \oplus a_{1 3} \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_0 = a_{1 2 3} \oplus 1 = 1 \Rightarrow a_{1 2 3} = 0 \end{array} $$ Таким образом, функция имеет вид: $$ f(x_1, x_2, x_3) = x_1 x_3 \oplus x_1 \oplus x_2 $$ и не является линейной. \paragraph{Теорема Поста} Существует метод проверки полноты системы, называемый теоремой Поста. Она основывается на выделении пяти классов Поста булевых функций: \begin{description} \item[класс функций сохраняющих 0] $f \in T_0 \Leftrightarrow f(0, 0, \dots 0) = 0$, \item[класс функций сохраняющих 1] $f \in T_1 \Leftrightarrow f(1, 1, \dots 1) = 1$, \item[класс самодвойственных функций] $f \in S \Leftrightarrow (\forall \alpha)(f(\overline{\alpha}) = \overline{f(\alpha)})$, \item[класс монотонных функций] $f \in M \Leftrightarrow (\forall \alpha, \beta)(\alpha \leqslant \beta \Rightarrow f(\alpha) \leqslant f(\beta))$, где подразумевается стандартный порядок булевой алгебры (при котором существуют и несравнимые элементы!), \item[класс линейных функций] $ f = \sum\limits_{i \in \overline{1, n}} a_i x_i \oplus a_0 $, т.е. функция представима в виде полинома Жегалкина первой степени. \end{description} Можно доказать, что все эти классы являются \emph{замкнутыми}, т.е. любая комбинация функций из одного класса остаётся в том же классе. \begin{quote} {\bf Теорема (Поста):} система булевых функций полна тогда и только тогда, когда она целиком не лежит ни в одном из классов Поста. \end{quote} Рассмотрим пример: $f(x_1, x_2, x_3) = x_1 (\overline{x_1} | x_3) (\overline{x_1} \oplus \overline{x_3}) \rightarrow (x_2 \sim x_3), w = (1 1 1 0 0 1 1 0)$. Необходимо проверить полноту системы $\{f, w\}$. Функция $f$ принимает следующие значения: $f = (1 1 1 1 1 1 0 1)$. Проверка принадлежности первых четырёх классов поста может быть проведена очень быстро. Для проверки линейности построим представление данных функций в виде полинома Жегалкина: $$ \begin{array}{l} f (0, 0, 0) = a_0 = 1,\\ f (0, 0, 1) = a_3 \oplus 1 = 1 \Rightarrow a_3 = 0,\\ f (0, 1, 0) = a_2 \oplus 1 = 1 \Rightarrow a_2 = 0,\\ f (1, 0, 0) = a_1 \oplus 1 = 1 \Rightarrow a_1 = 0,\\ f (0, 1, 1) = a_{2 3} \oplus 0 \oplus 0 \oplus 1 = 1 \Rightarrow a_{2 3} = 0,\\ f (1, 0, 1) = a_{1 3} \oplus 0 \oplus 0 \oplus 1 = 1 \Rightarrow a_{1 3} = 0,\\ f (1, 1, 0) = a_{1 2} \oplus 0 \oplus 0 \oplus 1 = 0 \Rightarrow a_{1 2} = 1,\\ f (1, 1, 1) = a_{1 2 3} \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 1 \Rightarrow a_{1 2 3} = 1. \end{array} $$ Поучается, что $f = x_1 x_2 x_3 \oplus x_1 x_2 \oplus 1$ нелинейна. $$ \begin{array}{l} w (0, 0, 0) = a_0 = 1,\\ w (0, 0, 1) = a_3 \oplus 1 = 1 \Rightarrow a_3 = 0,\\ w (0, 1, 0) = a_2 \oplus 1 = 1 \Rightarrow a_2 = 0,\\ w (1, 0, 0) = a_1 \oplus 1 = 0 \Rightarrow a_1 = 1,\\ w (0, 1, 1) = a_{2 3} \oplus 0 \oplus 0 \oplus 1 = 0 \Rightarrow a_{2 3} = 1,\\ w (1, 0, 1) = a_{1 3} \oplus 1 \oplus 0 \oplus 1 = 1 \Rightarrow a_{1 3} = 1,\\ w (1, 1, 0) = a_{1 2} \oplus 1 \oplus 0 \oplus 1 = 1 \Rightarrow a_{1 2} = 1,\\ w (1, 1, 1) = a_{1 2 3} \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \oplus 1 = 0 \Rightarrow a_{1 2 3} = 1. \end{array} $$ Поучается, что $w = x_1 x_2 x_3 \oplus x_1 x_2 \oplus x_2 x_3 \oplus x_1 x_3 \oplus x_1 \oplus 1$ нелинейна. Принадлежность классам Поста обобщим в таблице: \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline & $T_0$ & $T_1$ & $S$ & $M$ & $L$ \\ \hline $f$ & - & + & - & - & -\\ $w$ & - & - & - & - & -\\ \hline \end{tabular} \end{center} Система функций $\{f, w\}$ является полной, более того, полной является уже система $\{ w\}$. Выразим стандартный базис $\{\wedge, \overline{\phantom{x}}\}$ через функцию $w$. Воспользуемся тем, что $w$ не сохраняет ни 0, ни 1, значит: $$ w(x, x, x) = \overline{x}. $$ Так как $w$~--- несамодвойственна, выразим константы через отрицание. Для этого найдём такой вектор $\alpha$, что $w(\alpha) = w(\overline{\alpha})$. Видно, что это выполняется при $\alpha = (0 1 0)$. Значит, $w(\overline{x}, x, \overline{x}) = w(x, \overline{x}, x) = 1$. Тогда 0 можно получить с помощью отрицания. $w$~--- нелинейна, выразим конъюнкцию из полинома Жегалкина этой функции. Можно получить, что $w(x_1, x_2, 0) = x_1 x_2 \oplus x_1 \oplus 1$. Тогда $$ w(x_1, x_2 \oplus 1, 0) \oplus 1 = x_1 (x_2 \oplus 1) \oplus x_1 \oplus 1 \oplus 1 = x_1 x_2, $$ откуда $x y = \overline{w(x, \overline{y}, 0)}$. \paragraph{Схемы из функциональных элементов} Часто для формального задания булевых функций используется \emph{схемы из функциональных элементов} (СФЭ)~--- графы специального вида, основу которых составляют собственно функциональные элементы, т.е. булевы функции, принимающие на вход переменные и выдающие результат. На рисунке \ref{Pic:schema_std} изображены функциональные элементы для стандартных булевых функций. С их помощью, к примеру, функция исключающего или может быть реализована следующим образом (рисунок \ref{Pic:schema_xor}): \begin{figure}[tbh] \begin{center} \includegraphics[width=5cm]{schema_std.eps} \caption{Функциональные элементы для стандартных функций} \label{Pic:schema_std} \end{center} \end{figure} \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{schema_xor.eps} \caption{СФЭ для функции исключающего или} \label{Pic:schema_xor} \end{center} \end{figure} Аналогичным образом могут быть построены схемы для булевых функций любой сложности. В электронике часто используются схемы, выполняющие сложение битовых переменных. Такие схемы называются \emph{сумматорами}. Таблица истинности для булевых функций сложения двух $x_1 + x_2 = y_1 y_2$ и трёх $x_1 + x_2 + x_3 = y_1 y_2$ однобитовых (булевых) переменных содержит два столбца результата (результат имеет большее число разрядов, чем аргументы), т.е. мы имеем две булевых функции для каждой из операций сложения: \begin{center} \begin{tabular}{cc} \begin{tabular}{|c|c|c|c|} \hline $x_1$ & $x_2$ & $y_1$ & $y_2$\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 1 & 0 & 1\\ \hline 1 & 0 & 0 & 1\\ \hline 1 & 1 & 1 & 0\\ \hline \end{tabular} & \begin{tabular}{|c|c|c|c|c|} \hline $x_1$ & $x_2$ & $x_3$ & $y_1$ & $y_2$\\ \hline 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 0 & 1\\ \hline 0 & 1 & 0 & 0 & 1\\ \hline 0 & 1 & 1 & 1 & 0\\ \hline 1 & 0 & 0 & 0 & 1\\ \hline 1 & 0 & 1 & 1 & 0\\ \hline 1 & 1 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 1\\ \hline \end{tabular} \end{tabular} \end{center} СФЭ для сумматора сложения трёх переменных представлен на рисунке \ref{Pic:schema_sum3}. Удобство использования этого сумматора таково, что на его основе можно стоить сумматоры для сложения сколь угодно больших чисел. Например, на рисунке \ref{Pic:schema_sum_many} показан сумматор для сложения двух трёхразрядных переменных $x_1 x_2 x_3 + y_1 y_2 y_3 = z_1 z_2 z_3 z_4$: \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{schema_sum3.eps} \caption{СФЭ сумматора} \label{Pic:schema_sum3} \end{center} \end{figure} \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{schema_sum_many.eps} \caption{СФЭ для сумматора трёхразрядных переменных} \label{Pic:schema_sum_many} \end{center} \end{figure} \section{Графы} В теории графов выделяют два вида графов: \emph{неориентированные} и \emph{ориентированные}. \paragraph{Неориентированные графы} Неориентированным графом называют пару $(V, E)$, где $V$~--- конечное множество \emph{вершин}, а $E$~--- множество \emph{рёбер} такое, что $E \subseteq \{ \{v, w\} | v, w \in V \And v \neq w \}$. Важно, что рёбра могут соединять какие-то \emph{две} вершины. Вершины можно представить в виде точек на плоскости, а дуги~--- линиями, их соединяющими. При этом для нас представляют интерес не координаты точек или длина и форма линий, а \emph{связь} между дугами и вершинами. На рисунке \ref{Pic:graph_examples} показаны примеры неориентированных графов. Граф {\bf (а)} определяется как: $$ \begin{array}{l} V = \{\mbox{``Киев''}, \mbox{``Лондон''}, \mbox{``Москва''}, \mbox{``Рио''}\},\\ E = \{\{\mbox{``Киев''},\mbox{``Москва''}\}, \{\mbox{``Лондон''},\mbox{``Москва''}\}\}. \end{array} $$ А вот в графе {\bf (в)} все вершины соедины с каким-либо ребром: $$ \begin{array}{l} V = \{1, 2, 3, 4, 5, 6, 7\},\\ E = \{\{1,2\},\{1,3\},\{1,7\},\{2,4\},\{2,5\},\{3,6\},\{4,5\},\{6,7\}\} \end{array} $$ \begin{figure}[tbh] \begin{center} \includegraphics[width=13cm]{graph_examples.eps} \caption{Примеры неориентированных графов} \label{Pic:graph_examples} \end{center} \end{figure} Можно легко получить число возможных графов для заданного числа вершин $|V| = n$. Максимальное число рёбер в таком графе~--- число неупорядоченных пар из $n$, т.е. $C_n^2 = \frac{n (n - 1)}{2}$. Тогда общее число неориентированных графов равно мощности множества подмножеств всех рёбер, т.е. $2^{\frac{n (n - 1)}{2}}$. Для каждой вершины вводится понятие \emph{степени}: $$ dg(v) = |\{ u | \{u, v\} \in E\}|, $$ т.е. число рёбер, соединённых с вершиной. \emph{Цепью} в графе называют произвольную конечную или бесконечную последовательность вершин, в которой каждая последующая соединена ребром с предыдущей. Для конечной цепи число рёбер в ней называют \emph{длиной}. Цепь называется \emph{простой}, если все её вершины, кроме, быть может, первой и последней, попарно различны и все её рёбра попарно различны. Простая цепь ненулевой длины, начало и конец которой совпадают, называется \emph{циклом}. Неориентированный граф, не имеющий циклов называют \emph{ацикличным}. На рисунке \ref{Pic:graph_chain} показаны цепь, простая цепь и цикл. \begin{figure}[tbh] \begin{center} \includegraphics[width=13cm]{graph_chain.eps} \caption{Цепь, простая цепь и цикл} \label{Pic:graph_chain} \end{center} \end{figure} \emph{Подграфом} $\mathcal{G}' = (V', E')$ графа $\mathcal{G} = (V, E)$ называют такой \emph{граф}, что: $ V' \subseteq V \And E' \subseteq E$. Так как $\mathcal{G}'$~--- граф, в нём не могут быть только вершины, соединённые с рёбрами. Подграф называется \emph{остовным}, если $V = V'$. Неориентированный граф называется \emph{связным}, если в нём любые две вершины соединены цепью. Максимальный связный подграф~--- \emph{компонента связности} этого графа (или просто \emph{компонента}). Компоненты не имеют ни общих вершин, ни общих рёбер. Для двух вершин можно ввести бинарное отношение \emph{достижимости}: $u v$ выполняется, когда вершины $u$ и $v$ можно соединить цепью. Можно доказать, что это отношение является отношением эквивалентности. Тогда граф может быть факторизован, и элементами фактор-множества будут являться компоненты данного графа. На рисунке \ref{Pic:graph_com} показан пример графа из нескольких компонент связности. \begin{figure}[tbh] \begin{center} \includegraphics[width=7cm]{graph_com.eps} \caption{Компоненты неориентированного графа} \label{Pic:graph_com} \end{center} \end{figure} Особый интерес представляют особые виды графов. Ациклический связный граф называется \emph{деревом}. Обычно в дереве одна из вершин выделяется в качестве \emph{корня}. Более общим случаем дерева является \emph{лес}: граф, состоящий из двух и более деревьев (ациклический граф). Вершины, степень которых равна 1 и не являющиеся корнем, называют \emph{листьями}. Граф, состоящий только из корня и листьев, называют \emph{кустом}. На рисунке \ref{Pic:graph_tree} показаны дерево, куст и лес. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{graph_tree.eps} \caption{Дерево, куст и лес} \label{Pic:graph_tree} \end{center} \end{figure} Помимо перечисления множеств $V$ и $E$, неориентированные графы можно представлять в виде матрицы \emph{смежности}: матрица имеет квадратный и симметрический вид, размером $n \times n$, где $n$~--- число вершин. Элементы матрицы равны: $$ a_{i,j} = \left\{ \begin{array}{l} 1, \mbox{если}\, \{v_i, v_j\} \in E,\\ 0, \mbox{если}\, \{v_i, v_j\} \notin E. \end{array}\right. $$ Для графа на рисунке \ref{Pic:graph_examples}, {\bf (а)} матрица смежности будет иметь вид: $$ A = \left( \begin{array}{cccc} 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 \end{array} \right) $$ Другой матрицей, представляющей для нас интерес, является матрица \emph{достижимости}, размер которой также $n \times n$. Элементы матрицы равны: $$ a_{i,j} = \left\{ \begin{array}{l} 1, \mbox{если}\, v_i \Rightarrow^* v_j\\ 0, \mbox{иначе}. \end{array}\right. $$ В том же примере матрица достижимости отличается от матрицы смежности: $$ C = \left( \begin{array}{cccc} 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 \end{array} \right) $$ \paragraph{Оринтированные графы} Ориентированный граф отличается наличием направления на дугах, соединяющих вершины. \emph{Ориентированный граф} определяется как пара $(V, E)$, где $V$~--- множество вершин, как в неориентированном графе, а $E \subseteq V \times V$~--- множество дуг. Каждая дуга~--- упорядоченная пара вершин, стрелка на которой направлена от первой вершины ко второй. Отметим также, что в случае неориентированного графа возможны \emph{петли}, т.е. дуги вида $(v, v)$. На рисунке \ref{Pic:ograph_example} показан пример ориентированного графа. Для него множество вершин и дуг равно: $$ \begin{array}{l} V = \{\mbox{``Вася''}, \mbox{``Гога''}, \mbox{``Гриша''}, \mbox{``Маша''}, \mbox{``Миша''}, \mbox{``Оля''}\},\\ E = \{(\mbox{``Вася''}, \mbox{``Маша''}), (\mbox{``Гога''}, \mbox{``Гриша''}), (\mbox{``Гога''}, \mbox{``Миша''}),\\ (\mbox{``Гриша''}, \mbox{``Оля''}), (\mbox{``Маша''}, \mbox{``Вася''}), (\mbox{``Миша''}, \mbox{``Оля''}), \\ (\mbox{``Оля''}, \mbox{``Оля''})\} \end{array} $$ \begin{figure}[tbh] \begin{center} \includegraphics[width=7cm]{ograph_example.eps} \caption{Пример ориентированного графа} \label{Pic:ograph_example} \end{center} \end{figure} Число ориентированных графов для заданного числа вершин больше, чем неориентированных. Всего между $n$ вершинами можно провести $n^2$ дуг (число упорядоченных пар). Значит число графов будет равно мощности множества подмножеств всех дуг: $2^{n^2}$. Для ориентированных графов степень вершины состоит из двух частей: \begin{description} \item[полустепень захода] $dg^{-}(v) = |\{ v | (w, v) \in E\}|$~--- число дуг, входящих в вершину; \item[полустепень исхода] $dg^{+}(v) = |\{ v | (v, w) \in E\}|$~--- число дуг, исходящих из вершины. \end{description} Например, для вершины ``Оля'' на рисунке \ref{Pic:ograph_example} полустепень захода равна 3, а полустепень исхода~--- 1. Аналогом цепи в ориентированных графах является \emph{путь}~--- при этом движение возможно только в направлении стрелок. Также определяется и \emph{простой путь}, а аналог цикла называется \emph{контуром}. В ориентированных графах определяется три вида связности: \begin{description} \item[связность] Ориентированный граф называется \emph{связным} (просто связным, связным односторонне), если $(\forall v, u \in V)(v \Rightarrow^* u \vee u \Rightarrow^* v)$, т.е. существует путь нулевой или большей длины из $u$ в $v$ или из $v$ в $u$. \item[сильная связность] Ориентированный граф называется \emph{сильно связным} (связным двусторонне), если $(\forall v, u \in V)(v \Rightarrow^* u \And u \Rightarrow^* v)$, т.е. существуют пути нулевой или большей длины из $u$ в $v$ и из $v$ в $u$. \item[слабая связность] Ориентированный граф называется \emph{слабо связным}, если соответствующий ему неориентированный граф (стереть все стрелочки и удалить петли) связен. \end{description} На рисунке \ref{Pic:ograph_conn} показаны связный, сильно и слабо связные подграфы исходных графов. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{ograph_conn.eps} \caption{Связность в ориентированных графах} \label{Pic:ograph_conn} \end{center} \end{figure} \emph{Ориентированное дерево} определяется следующим образом: \begin{enumerate} \item $dg^-(v) \leqslant 1$ для всех вершин; \item $dg^-(v) = 0$ для единственной вершины, называемой корнем; \item в графе нет контуров. \end{enumerate} Куст и лес определяются аналогично. Граф более общего вида, не имеющий контуров, называется \emph{сетью}. Ориентированные графы также могут задаваться матрицей смежности. В этом случае элементы матрицы равны: $$ a_{i,j} = \left\{ \begin{array}{l} 1, \mbox{если}\, (v_i, v_j) \in E,\\ 0, \mbox{если}\, (v_i, v_j) \notin E. \end{array}\right. $$ Такая матрица уже не является в общем случае симметричной. Для графа на рисунке \ref{Pic:ograph_example} матрица будет равна: $$ A = \left(\begin{array}{ccccccc} 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) $$ Аналогично определяется и матрица достижимости. Для нашего примера такая матрица будет равна: $$ C = \left(\begin{array}{ccccccc} 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) $$ % семинар 5 \paragraph{Идемпотентные полукольца} Идемпотентным называется полукольцо, $(A, \oplus, \odot, \mathbf{0}, \mathbf{1})$, в котором операция сложения идемпотентна: $(\forall a \in A)(a \oplus a = a)$. Примером таких полуколец являются: \begin{itemize} \item \emph{булево полукольцо} $\mathcal{B}_2 = (\{0, 1\}, \vee, \wedge, 0, 1)$; \item $\mathcal{R}^+ = ([0, +\infty], min, +, +\infty, 0)$. \end{itemize} В указанных полукольцах для каждого элемента можно ввести операцию \emph{итерации}: $a^* = a^0 \oplus a^1 \oplus a^2 \oplus \dots$~--- бесконечная сумма степеней элементов. Под степенью $n$ элемента понимается умножение его на себя $n$ раз, а нулевая степень равна единице полукольца по определению: $a^0 = \mathbf{1}$. Для приведённых выше полуколец итерация для любых элементов находится очень просто: \begin{itemize} \item $\mathcal{B}_2$: $$ \begin{array}{l} 0^* = 0^0 \oplus 0^1 \oplus 0^2 \oplus \dots = 1 + 0 + 0 + \dots = 1\\ 1^* = 1^0 \oplus 1^1 \oplus 0^2 \oplus \dots = 1 + 1 + 1 + \dots = 1 \end{array} $$ \item $\mathcal{R}^+$: для любого $a$ $$ a^* = a^0 \oplus a^1 \oplus \dots = \mathbf{1} \oplus a^1 \oplus a^2 = min\{0, a^1, a^2, \dots\} = 0 $$ \end{itemize} Идемпотентные полукольца интересны тем, что в них можно решать уравнения вида: $$ \begin{array}{l} x = a \odot x \oplus b \Leftrightarrow x = a^* \odot b;\\ x = x \odot a \oplus b \Leftrightarrow x = b \odot a^*. \end{array} $$ Интересно, что такие необычные для арифметики уравнения как $x = x$ или $x = x + \mathbf{1}$ имеют здесь единственные решения: $$ \begin{array}{l} x = x \oplus \mathbf{1} \Leftrightarrow x = \mathbf{1}^* \odot \mathbf{1} = \mathbf{1};\\ x = x \Leftrightarrow x = \mathbf{1} \odot x \oplus \mathbf{0} \Leftrightarrow x = \mathbf{1}^* \odot \mathbf{0} = \mathbf{0}. \end{array} $$ \paragraph{Нахождение матрицы достижимости} Важной задачей в теории графов является нахождение матрицы достижимости по матрице смежности. Можно доказать, что матрица достижимости может быть получена как итерация матрицы смежности: $$ C = A^*, $$ где элементами матриц являются нули и единицы, о операции соответствуют операциям идемпотентного полукольца $\mathcal{B}_2$. В этом случае матрица $C$ может быть получена при решении уравнения $X = A \odot X$, так как оно эквивалентно уравнению $X = A \odot X \oplus E $, где $E$~--- единичная матрица. Таким образом, для получения матрицы $C$ необходимо решить $n$ систем уравнений следующего вида для $k = \overline{1, n}$: $$ \left\{ \begin{array}{l} x_1 = a_{1 1} \odot x_1 \oplus a_{1 2} \odot x_2 \oplus \dots \oplus a_{1 n} \odot x_n \oplus \varepsilon_{1 k}\\ x_2 = a_{2 1} \odot x_1 \oplus a_{2 2} \odot x_2 \oplus \dots \oplus a_{2 n} \odot x_n \oplus \varepsilon_{2 k}\\ \dots \\ x_n = a_{n 1} \odot x_1 \oplus a_{n 2} \odot x_2 \oplus \dots \oplus a_{n n} \odot x_n \oplus \varepsilon_{n k} \end{array}\right., $$ где $a_{i j}$~--- элементы матрицы смежности, а $\varepsilon_{i j}$~--- элементы единичной матрицы. Решением каждой из систем будет $k$-й столбец матрицы $C$. \begin{figure}[tbh] \begin{center} \includegraphics[width=6cm]{graph_att.eps} \caption{Ориентированный граф} \label{Pic:graph_att} \end{center} \end{figure} Рассмотрим пример. На рисунке \ref{Pic:graph_att} показан ориентированный граф из шести вершин, матрица смежности которого равна: $$ A = \left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 \end{array}\right) $$ \begin{description} \item[1-й столбец] $$ \begin{array}{c} \left\{ \begin{array}{l} x_1 = 1 \odot x_2 \oplus 1\\ x_2 = 1 \odot x_3 \oplus 1 \odot x_5\\ x_3 = 1 \odot x_6\\ x_4 = 0\\ x_5 = 1 \odot x_2 \oplus 1 \odot x_4\\ x_6 = 1 \odot x_3 \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 1 \odot x_3 \oplus 1 \odot (1 \odot x_2)\\ x_3 = 1 \odot x_6\\ x_4 = 0\\ x_5 = 1 \odot x_2\\ x_6 = 1 \odot (1 \odot x_6) \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow\\ \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 1^* \odot (1 \odot x_3) = 1 \odot x_3\\ x_3 = 1 \odot x_6\\ x_4 = 0\\ x_5 = 1 \odot x_2\\ x_6 = 1^*\odot (1 \odot x_5) = 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 1 \odot (1 \odot (1 \odot (1 \odot x_2))) = x_2\\ x_3 = 1 \odot (1 \odot (1 \odot x_2))\\ x_4 = 0\\ x_5 = 1 \odot x_2\\ x_6 = 1 \odot (1 \odot x_2) \end{array}\right. \Leftrightarrow\\ \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 0\\ x_3 = 0\\ x_4 = 0\\ x_5 = 0\\ x_6 = 0 \end{array}\right. \end{array} $$ \item[2-й столбец] $$ \left\{ \begin{array}{l} x_1 = 1 \odot x_2\\ x_2 = 1 \odot x_3 \oplus 1 \odot x_5 \oplus 1\\ x_3 = 1 \odot x_6\\ x_4 = 0\\ x_5 = 1 \odot x_2 \oplus 1 \odot x_4\\ x_6 = 1 \odot x_3 \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1 \odot x_2\\ x_2 = 1\\ x_3 = 1 \odot x_6\\ x_4 = 0\\ x_5 = 1 \odot x_2 = 1\\ x_6 = 1^* \odot 1 \odot x_5 = 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 1\\ x_3 = 1\\ x_4 = 0\\ x_5 = 1\\ x_6 = 1 \end{array}\right. $$ \item[3-6 столбцы] Вычисляются аналогично. \end{description} Полученная матрица достижимости примет вид: $$ C = \left(\begin{array}{cccccc} 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 1 \end{array}\right) $$ \paragraph{Нахождение кратчайших путей} Теория графов широко применяется при решении транспортных задач~--- нахождения кратчайших маршрутов в графах дорог, сетей и т.п. Для этого используются \emph{размеченные} графы: $\mathcal{G} = (V, E, \varphi)$, где $\varphi: E \mapsto S \setminus \{0\}$~--- весовая функция над некоторым полукольцом $(S, \oplus, \odot, 0, 1)$. Т.е. каждому ребру (или дуге) сопоставляется число, символизирующее длину пути, сложность задачи или любую другую стоимость перемещения между вершинами. Рассмотрим граф, размеченный над полукольцом $\mathcal{R}^+$ (см. рисунок \ref{Pic:graph_cost}). \begin{figure}[tbh] \begin{center} \includegraphics[width=6cm]{graph_cost.eps} \caption{Граф с размеченными дугами} \label{Pic:graph_cost} \end{center} \end{figure} Для такого графа можно записать матрицу $A$ \emph{метог дуг} (эта матрица аналогична матрице смежностей), где $$ a_{i j} = \left\{ \begin{array}{l} \varphi((v_i, v_j)), \mbox{если}\, (v_i, v_j) \in E\\ +\infty, \mbox{иначе} \end{array}\right. $$ В нашем случае матрица меток дуг равна: $$ A = \left(\begin{array}{cccccc} +\infty & 1 & +\infty & +\infty & +\infty & +\infty\\ +\infty & +\infty & 2 & +\infty & 20 & +\infty\\ +\infty & +\infty & +\infty & +\infty & +\infty & 3\\ +\infty & +\infty & +\infty & +\infty & +\infty & +\infty\\ +\infty & 2 & +\infty & 4 & +\infty & +\infty\\ +\infty & +\infty & 4 & +\infty & 1 & +\infty \end{array}\right) $$ Можно доказать, что на основе этой матрицы по аналогии можно получить \emph{матрицу стоимостей} путей $C = A^*$, где $c_{i j}$~--- стоимость кратчайшего пути между вершинами $i$ и $j$, т.е. сумма меток всех дуг для данного пути. Если же пути между вершинами $i$ и $j$ не существует, то соответствующий элемент матрицы $C$ равен $+\infty$. Матрица стоимостей $C$ находится аналогично, с помощью решения $n$ систем уравнений. Важно отметить, что в данном случае вся работа ведётся в полукольце $\mathcal{R}^+$, в котором нулём полукольца является $+\infty$, а единицей~--- 0! \begin{description} \item[1-й столбец] $$ \begin{array}{c} \left\{ \begin{array}{l} x_1 = 1 \odot x_2 \oplus 0\\ x_2 = 2 \odot x_3 \oplus 20 \odot x_5\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2 \odot x_2 \oplus 4 \odot x_4\\ x_6 = 4 \odot x_3 \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 0\\ x_2 = 2 \odot x_3 \oplus 20 \odot (2 \odot x_2)\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2 \odot x_2\\ x_6 = 4 \odot (3 \odot x_6) \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow\\ \Leftrightarrow \left\{ \begin{array}{l} x_1 = 0\\ x_2 = 2 \odot x_3 \oplus 22 \odot x_2\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2 \odot x_2\\ x_6 = 7 \odot x_6 \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 0\\ x_2 = 22^* \odot 2 \odot x_3 = 2 \odot x_3\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2 \odot x_2\\ x_6 = 7^* \odot 1 \odot x_5 = 1 \odot x_5 \end{array}\right. \Leftrightarrow\\ \Leftrightarrow \left\{ \begin{array}{l} x_1 = 0\\ x_2 = 2 \odot (3 \odot (2 \odot (2 \odot x_2))) = 10 \odot x_2\\ x_3 = 3 \odot (2 \odot (2 \odot x_2))\\ x_4 = +\infty\\ x_5 = 2 \odot x_2\\ x_6 = 1 \odot (2 \odot x_2) \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 0\\ x_2 = +\infty\\ x_3 = +\infty\\ x_4 = +\infty\\ x_5 = +\infty\\ x_6 = +\infty \end{array}\right. \end{array} $$ \item[2-й столбец] $$ \begin{array}{c} \left\{ \begin{array}{l} x_1 = 1 \odot x_2\\ x_2 = 2 \odot x_3 \oplus 20 \odot x_5 \oplus 0\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2 \odot x_2 \oplus 4 \odot x_4\\ x_6 = 4 \odot x_3 \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1 \odot x_2\\ x_2 = 0\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2 \odot x_2 \oplus 4 \odot x_4\\ x_6 = 4 \odot (3 \odot x_6) \oplus 1 \odot x_5 \end{array}\right. \Leftrightarrow\\ \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 0\\ x_3 = 3 \odot x_6\\ x_4 = +\infty\\ x_5 = 2\\ x_6 = 7^* \odot 1 \odot x_5 = 1 \odot x_5 = 3 \end{array}\right. \Leftrightarrow \left\{ \begin{array}{l} x_1 = 1\\ x_2 = 0\\ x_3 = 6\\ x_4 = +\infty\\ x_5 = 2\\ x_6 = 3 \end{array}\right. \end{array} $$ \item[3-6 столбцы] Вычисляются аналогично. \end{description} Полученная матрица стоимостей будет иметь вид: $$ C = \left(\begin{array}{cccccc} 0 & 1 & 3 & 11 & 7 & 6\\ +\infty & 0 & 2 & 10 & 6 & 5\\ +\infty & 6 & 0 & 8 & 4 & 3\\ +\infty & +\infty & +\infty & 0 & +\infty & +\infty\\ +\infty & 2 & 4 & 4 & 0 & 7\\ +\infty & 3 & 4 & 5 & 1 & 0 \end{array}\right) $$ \paragraph{Гомоморфизм и автоморфизм графов} Пусть заданы два графа $\mathcal{G}_1 = (V_1, E_1)$ и $\mathcal{G}_2 = (V_2, E_2)$, отображение множества вершин первого графа во второе $h: V_1 \mapsto V_2$~--- \emph{гомоморфизм} графа $\mathcal{G}_1$ в $\mathcal{G}_2$, если $(\forall v, w \in V_1)(\{v, w\} \in E_1 \Rightarrow \{h(v), h(w)\} \in E_2)$. Если отображение $h$ биективно, то графы называются \emph{изоморфными}. Примеры гомоморфизма и не гомоморфизма представлены на рисунке \ref{Pic:graph_homo}. \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{graph_homo.eps} \caption{Пример гомоморфизма и не гомоморфизма} \label{Pic:graph_homo} \end{center} \end{figure} Аналогичным образом гомоморфизм определяется для ориентированных графов. Рассмотрим соответствующий пример: для заданного графа (см. рисунок \ref{Pic:ograph_homo}) необходимо найти все друхвершинные гомоморфные образы. \begin{figure}[tbh] \begin{center} \includegraphics[width=9cm]{ograph_homo.eps} \caption{Гомоморфизм в ориентированном графе} \label{Pic:ograph_homo} \end{center} \end{figure} Изоморфизм графа на себя (перестановка вершин) называется \emph{автоморфизмом}. Для анализа возможных существующих автоморфизмов в неориентированных графах удобно использовать дополнения к графам: граф с тем же набором вершин и набором дуг, не принадлежащих исходному графу. На рисунке \ref{Pic:graph_auto} показан исходный граф и его дополнение. \begin{figure}[tbh] \begin{center} \includegraphics[width=7cm]{graph_auto.eps} \caption{Автоморфизм в неориентированном графе} \label{Pic:graph_auto} \end{center} \end{figure} Можно увидеть, что любая перестановка из множества дополнении к графу оставит граф неизменным: $$ \left\{ \varepsilon, \left(\begin{array}{cc}1 & 3\\3 & 1\end{array}\right), \left(\begin{array}{cc}2 & 4\\4 & 2\end{array}\right), \left(\begin{array}{cccc}1 & 2 & 3& 4\\2 & 1 & 4 & 3\end{array}\right)\right\}. $$ Такие \emph{циклические перестановки} можно записать в сокращённом виде: $$ \{ \varepsilon, (1 3), (2 4), (1 3) (2 4)\}. $$ Видно, что все эти перестановки и их комбинации задают всевозможные автоморфизмы оригинального графа. \paragraph{Алгоритмы обхода графов. Поиск в глубину, поиск в ширину} Часто возникает задача \emph{обхода} вершин и рёбер графа, т.е. посещение всех вершин или рёбер, причём только по одному разу. Такой обход может использоваться, например, в поиске информации на графе. Существуют два широко известных алгоритма обхода вершин графа: поиск в глубину и поиск в ширину. В обоих из них поиск ведётся от какой-то вершины, избранной в качестве начальной. Поиск в глубину использует в своей работе рекурсию (или стэк в явном виде). Основная идея алгоритма состоит в ``погружении'' в граф от начальной вершины на максимально возможную глубину, а затем постепенный возврат из рекурсивных вызовов. С помощью рекурсии алгоритм поиска в глубину можно представить следующим образом: \begin{verbatim} bool visited[N] = {false, ... }; // массив флагов посещённых вершин edge edges[M]; // массив рёбер // рекурсивная процедура поиска void deep_search(vertex_t v) { visited[v] = true; // отметить вершину как посещённую ... // сделать с вершиной то, ради чего обход затевался for(size_t i = 0; i < M; i++) { edge e = edges[i]; if(e.from == v && !visited[e.to]) { deep_search(e.to); } } } \end{verbatim} Если стэк использовать явным образом, можно избавиться от рекурсивного вызова: \begin{verbatim} bool visited[N] = {false, ... }; // массив флагов посещённых вершин edge edges[M]; // массив рёбер stack s; // стэк // нерекурсивная процедура поиска void deep_search(vertex_t v0) { s.push(v0); while(!s.empty()) { vertex_t v = s.pop(); if(visited[v]) continue; // пропустить посещённую вершину visited[v] = true; // отметить вершину как посещённую ... // сделать с вершиной что-то for(size_t i = 0; i < M; i++) { edge e = edges[i]; if(e.from == v && !visited[e.to]) { s.push(e.to); } } } } \end{verbatim} В обоих случаях поиск запускается вызовом процедуры с параметром начальной вершины. Рассмотрим пример поиска в глубину на неориентированном графе, изображённый не рисунке \ref{Pic:graph_deep}. Остовный подграф, получившийся при обходе вершин обозначен пунктиром. Очевидно, что этот подграф является деревом с корнем в начальной вершине, а его вид будет зависеть от порядка обхода вершин во внутреннем цикле рекурсивной процедуры. \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{graph_deep.eps} \caption{Поиск в глубину в неориентированном графе} \label{Pic:graph_deep} \end{center} \end{figure} Порядок следования вершин и состояние стэка на каждом шаге: \begin{center} \begin{tabular}{|c|c|c|} \hline {\bf Шаг} & {\bf Текущая вершина} & {\bf Стэк в конце шага}\\ \hline 0 & $\varnothing$ & A\\ \hline 1 & A & B A\\ \hline 2 & B & C D B A\\ \hline 3 & C & D B A\\ \hline 4 & D & E D B A\\ \hline 5 & E & F H E B A\\ \hline 6 & F & G F H E B A\\ \hline 7 & G & I J G F H E B A\\ \hline 8 & I & J J I G F H E B A\\ \hline 9 & J & I G F H E B A\\ \hline 10 & H & E B A\\ \hline конец & A & $\varnothing$\\ \hline \end{tabular} \end{center} Аналогично производится поиск в глубину на ориентированном графе (см. рисунок \ref{Pic:ograph_deep}). \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{ograph_deep.eps} \caption{Поиск в глубину в ориентированном графе} \label{Pic:ograph_deep} \end{center} \end{figure} С помощью алгоритма поиска в глубину можно классифицировать дуги ориентированного графа следующим образом: \begin{description} \item[остовные дуги] получаются непосредственно при поиске в глубину, образуют дерево (или в общем случае лес), на рисунке обозначены пунктиром; \item[прямые дуги] соединяют предка и потомка в остовном пути, на рисунке обозначены буквой \textbf{F}; \item[обратные дуги] соединяют потомка и предка в остовном пути, на рисунке обозначены буквой \textbf{B}, интересно то, что каждая из таких дуг задаёт элементарный контур в графе; \item[перекрёстные дуги] все остальные дуги, на рисунке обозначены буквой \textbf{C}. \end{description} Вторым широко распространённым алгоритмом является \emph{поиск в ширину}. Это алгоритм использует \emph{очередь} для хранения списка обрабатываемых вершин. В результате работы алгоритма также получается остовное дерево, которое в общем случае отличается от дерева поика в глубину. Можно предложить следующий алгоритм поиска в ширину: \begin{verbatim} bool visited[N] = {false, ... }; // массив флагов посещённых вершин edge edges[M]; // массив рёбер queue q; // очередь // процедура поиска void wide_search(vertex_t v0) { q.push(v0); while(!q.empty()) { vertex_t v = q.pop(); if(visited[v]) continue; // пропустить посещённую вершину visited[v] = true; // отметить вершину как посещённую ... // сделать с вершиной что-то for(size_t i = 0; i < M; i++) { edge e = edges[i]; if(e.from == v && !visited[e.to]) q.push(e.to); } } } \end{verbatim} \begin{figure}[tbh] \begin{center} \includegraphics[width=13cm]{graph_wide.eps} \caption{Поиск в ширину в неориентированном графе} \label{Pic:graph_wide} \end{center} \end{figure} Рассмотрим пример поиска в ширину на неориентированном графе, изображённый не рисунке \ref{Pic:graph_wide}. Остовный подграф, получившийся при обходе вершин обозначен пунктиром. Порядок следования вершин и состояние очереди на каждом шаге представлены в таблице: \begin{center} \begin{tabular}{|c|c|c|} \hline {\bf Шаг} & {\bf Текущая вершина} & {\bf Очередь в конце шага}\\ \hline 0 & $\varnothing$ & Баум.\\ \hline 1 & Бауманская & Курск. Семён.\\ \hline 2 & Курская & Семён. Комсом. Пл.Рев. Таган.\\ \hline 3 & Семёновская & Комсом. Пл.Рев. Таган.\\ \hline 4 & Комсомольская & Пл.Рев. Таган.\\ \hline 5 & Пл. Революции & Таган. Арбат.\\ \hline 6 & Таганская & Арбат. Павел.\\ \hline 7 & Арбатская & Павел. Полян.\\ \hline 8 & Павелецкая & Полян. Серпух.\\ \hline 9 & Полянка & Серпух. Серпух.\\ \hline 10 & Серпуховская & Серпух. Октяб. Тульск.\\ \hline 11 & Октябрьская & Тульская\\ \hline 12 & Тульская & $\varnothing$\\ \hline \end{tabular} \end{center} % семинар 6 \section{Регулярные языки и конечные автоматы} \paragraph{Языки} Искусственные языки (например, языки программирования) рассматриваются в особом разделе дискретной математики~--- \emph{Теории формальных языков}. В рамках этих семинаров языки будут изучаться с \emph{синтаксической} точки зрения (проверка корректности фраз на рассматриваемом языке). В основе определения языка лежит понятие \emph{алфавита}. Произвольное конечное непустое множество $V = \{a, b, \dots \}$ называется алфавитом, его элементы~--- \emph{буквами}. Упорядоченный набор букв $a_1 a_2 \dots a_n, a_i \in V$ в данном алфавите называют \emph{словом} (или \emph{цепочка}). \emph{Длина} слова~--- число букв в нём. По сути, все слова длины $n$~--- декартова $n$-ная степень $V^n$ алфавита. Также по определению вводится понятие пустого слова $\lambda$: $V^0 = \{\lambda\}$. Все слова в алфавите $V$ можно обозначить как $V^* = V^0 \cup V^1 \cup V^2 \cup \dots$. \emph{Языком} $\mathcal{L}$ в алфавите $V$ называется некоторое подмножество всех слов этого алфавита: $\mathcal{L} \subseteq V^*$. Рассмотрим пример. Возьмем алфавит $V = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ всех десятичных цифр. В этом случае всего существует одно слово длины 0 (пустое слово $\lambda$), 10 слов длины 1 (``0'', ``1'', ``2'' и т.п.), 100 слов длины 2 (``00'', ``01'', $\dots$, ``99'') и т.п.. Множество всех слов в этом алфавите~--- множество всех строк, состоящих из десятичных цифр. Это множество, естественно, бесконечно. Рассмотрим язык всех двоичных слов: $\mathcal{L}_2 = \{0000, 011, 101111010, \dots\}$. Очевидно, что это множество образует язык в алфавите $V$, так как $\mathcal{L}_2 \subset V^*$. Кстати говоря, язык всех двоичных \emph{чисел} $\mathcal{L}_B = \{0, 1, 10, \dots 101111010, \dots\}$ является подмножеством языка двоичных слов: $\mathcal{L}_B \subset \mathcal{L}_2 \subset V^*$. Возьмём на множестве всех слов бинарную операцию \emph{конкатенации} (склеивания) строк: $$ a_1 a_2 \dots a_n \cdot b_1 b_2 \dots b_m = a_1 a_2 \dots a_n b_1 b_2 \dots b_m. $$ Очевидно, что эта операция ассоциативна, но в общем случае некоммутативна. Кроме того, пустое слово $\lambda$ является нейтральным элементом по этой операции: $a \cdot \lambda = \lambda \cdot a = a$. Можно заключить, что алгебра $(V^*, \cdot, \lambda)$~--- моноид. Операция конкатенации может быть расширена и на два языка: $$ \mathcal{L}_1 \cdot \mathcal{L}_2 = \{ c | c = a \cdot b, a \in \mathcal{L}_1, b \in \mathcal{L}_2\} $$ Например, для двух языков в алфавите $V = \{a, b\}$ конкатенация будет равна: $$ \begin{array}{l} \mathcal{L}_1 = \{ a b, a a b, a\}\\ \mathcal{L}_2 = \{ b, b b\}\\ \mathcal{L}_1 \cdot \mathcal{L}_2 = \{ a b b, a a b b, a b, a b b b, a a b b b\} \end{array} $$ Все свойства конкатенации сохраняются, а нейтральным элементом будет язык $\{ \lambda \}$. Также к языкам можно применять и стандартные теоретико-множественные операции, например, \emph{объединение}. Можно заметить, что множество всех языков в алфавите $V$ с операциями объединения и конкатенации образуют идемпотентное полукольцо: $$ \mathcal{L} (2^{V^*}, \cup, \cdot, \varnothing, \{\lambda\}). $$ Не трудно убедиться, что все аксиомы идемпотентного полукольца при этом выполняются. В этом полукольце также существует операция \emph{итерации}~--- босконечного объединения степеней языков: $$ \mathcal{L}^* = \mathcal{L}^0 \cup \mathcal{L}^1 \cup \mathcal{L}^2 \cup \mathcal{L}^3 \dots, $$ где степень $n$ языка определяется как $n$-кратная конкатенация этого языка с самим собой, а 0-ая степень по определению язык $\{\lambda\}$. Например, для языка $\mathcal{L} = \{ a b, b\}$ в алфавите $V = \{a, b\}$ итерация будет равна языку: $$ \begin{array}{c} \mathcal{L}^* = \mathcal{L}^0 \cup \mathcal{L}^1 \cup \mathcal{L}^2 \cup \mathcal{L}^3 \dots =\\ = \{\lambda\} \cup \{ a b, b\} \cup \{ a b, b\} \cdot \{ a b, b\} \cup \{ a b, b\} \cdot \{ a b, b\} \cdot \{ a b, b\} \dots=\\ = \{\lambda, a b, b\} \cup \{a b a b, a b b, b a b, b b\} \cup \{a b a b, a b b, b a b, b b\} \cdot \{ a b, b\} \cup \dots =\\ \{\lambda, b, a b, b b, a b b, b a b, b b b, a b a b, a b b b, b a b b, a b a b a b, \dots\} \end{array} $$ Обычно итерация языка обозначают кратко: $\{a b, b\}^*$. Также введем понятие \emph{позитивной итерации}: $$ \mathcal{L}^+ = \mathcal{L}^1 \cup \mathcal{L}^2 \cup \mathcal{L}^3 \dots, $$ \paragraph{Регулярные языки и выражения} \emph{Регулярным языком} в алфавите $V = \{a, b, c, \dots\}$ называется \emph{замыкание} элементарных языков $[\{a\}, \{b\}, \{c\}, \dots]_{\{\cup, \cdot, \phantom{x}^*\}}$ по операциям объединения, конкатенации и итерации. Другими словами, регулярные языки~--- это языки, которые могут быть получены из букв алфавита с помощью последовательных применений операций объединения, конкатенации или итерации, и никакие другие. Существует множество регулярных языков. Например, язык двоичных слов, приведённый выше или язык всех адресов электронной почты в алфавите $\{a, b, \dots, z, -, _, @\}$. Примером нерегулярного языка является $\mathcal{L} = \{ a^n b^n | n \in \mathbb{N}\} = \{ a b, a a b b, a a a b b b, \dots\}$ в алфавите $V = \{a, b\}$. Очень важное условие~--- равенство числа букв $a$ и $b$ нарушает регулярность языка. Тогда как язык $\{ a^n b^m | n, m \in \mathbb{N}\}$ конечно является регулярным, так как может быть получен как $\{a\}^+ \cdot \{b\}^+$. Для более удобного представления регулярных языков можно использовать \emph{регулярные выражения}. В регулярных выражениях могут фигурировать буквы алфавита, пустое слово $\lambda$, бинарные операции объединения и конкатенации и унарная операция итерации, так что регулярному выражению может быть однозначно поставлен в соответствие регулярный язык (обратное неверно). При этом достаточно заменить следующие элементы регулярного выражения: $$ \begin{array}{c} \varnothing \rightarrow \varnothing\\ \forall a \in V: a \rightarrow \{ a \}\\ \lambda \rightarrow \{ \lambda \}\\ \alpha \rightarrow P, \beta \rightarrow Q \Rightarrow \left\{ \begin{array}{l} (\alpha + \beta) \rightarrow P \cup Q\\ (\alpha \cdot \beta) \rightarrow P \cdot Q\\ \alpha^* \rightarrow P^*, \alpha^+ \rightarrow P^+ \end{array}\right. \end{array} $$ В регулярных выражениях по определению используется следующие приоритеты операций (по убыванию приоритета): $\phantom{x}^*$ и $\phantom{x}^+$, $\cdot$, +. Рассмотрим примеры на связь между регулярными языками и регулярными выражениями: \begin{itemize} \item $(a + bc)^* \rightarrow \{ a, bc\}^* = \{ \{a, bc\}^n | n \in \mathbb{N}_0 \}$, примерами слов этого языка являются $ a b c a a a$ или $b c a$, тогда как слово $ b a c b c$ не принадлежит данному языку. \item $a b^* + b^+ (a a)^* \rightarrow \{a\} \{b\}^* \cup \{b\}^+ \{ a a \}^* = \{ a b^n, b^m (a a)^k | n, k \geqslant 0, m > 0\}$, примерами слов этого языка являются $ a b b b$ или $ b b $, тогда как слово $a b a$ не принадлежит данному языку. \item рассмотрим алфавит $V = \{ a, b, \dots, z, @, ., -\}$ символов латиницы и некоторых служебных символов. Регулярное выражение $(a + b + \dots + z)^+@(a + b + \dots + z)^+.(a + b + \dots + z)^+$ задаёт в общем виде язык возможных адресов электронной почты, например: $hkhfskdjfh@qewq.ert$ или $aleksey@fedoseev.net$. \item в алфавите десятичных цифр $V = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ регулярное выражение $(0 + 1)^*$ задаёт язык двоичных слов, рассмотренный выше. \end{itemize} Один язык может задаваться множеством регулярных выражений, например, язык $\{\{a, b\}^n c a^m| n \geqslant 0, m > 0\}$~--- выражением $(a + b)^* c a^+$ или $(a^*b^*)^* c a a^*$. На практике регулярные выражения часто используются для поиска известных последовательностей символов в тексте и разбиении строк регулярного языка на составные части. См. команду grep в Unix или regular expressions в современных библиотеках и языках программирования. \paragraph{Конечные автоматы} Отдельный раздел математики рассматривает \emph{автоматы}~--- абстрактные машины, выполняющие определённые действия на основании входных данных. В этом курсе рассматриваются \emph{конечные автоматы}. Другими известными автоматами являются \emph{автоматы с магазинной памятью}, используемые в теории компиляторов, а также универсальная \emph{машина Тьюринга}. Конечный автомат представляет собой абстрактное устройство (см. рисунок \ref{Pic:fa_scheme}), состоящее из: \begin{itemize} \item входной ленты с символами из алфавита $V$; \item считывающего устройства; \item блока управления, который может находиться в одном из состояний. \end{itemize} \begin{figure}[tbh] \begin{center} \includegraphics[width=6cm]{fa_scheme.eps} \caption{Схема конечного автомата} \label{Pic:fa_scheme} \end{center} \end{figure} Считывающее устройство может двигаться вдоль ленты в одном направлении, тем самым проходя всю цепочку символов на ленте. Работа автомата состоит из дискретных \emph{шагов}, на каждом шаге устройство управления находится в определённом состоянии. При переходе на следующий шаг считывающее устройство может продвинуться на один символ, а также может измениться состояние блока управления (или, другими словами, состояние самого автомата). Блок управления содержит список правил переходов, согласно которому его состояние изменяется с учётом входных символов. Формально, конечный автомат~--- это пятёрка вида $$ \mathcal{F} (V, Q, q_0, Q_F, \delta), $$ где $V$~--- алфавит входных символов, $Q$~--- конечное множество состояний, $q_0 \in Q$~--- начальное состояние автомата, $Q_F \subseteq Q$~--- множество конечных состояний автомата, $\delta$~---множество правил переходов. Каждое правило переходов имеет вид $p a \rightarrow q$, где $p, q \in Q$~--- некоторые состояния, которые могут совпадать, $a \in V \cup \{\lambda\}$~--- входной символ или пустое слово. Правило имеет следующий смысл: \begin{itemize} \item если $a \neq \lambda$, то это правило применимо, только если на данном шаге блок управления находится в состоянии $p$, а считывающее устройство наблюдает символ $a$ на входной цепочке. Результатом действия этого правила является изменение состояния автомата на $q$ и сдвиг считывающего устройства на один символ; \item если $a = \lambda$, то это правило применимо, только если на данном шаге блок управления находится в состоянии $p$, символ на ленте при этом не анализируется (это возможно также, если считывающее устройство дошло до конца ленты). Результатом действия этого правила является изменение состояния автомата на $q$. \end{itemize} Таким образом, автомат меняет своё состояние от начального к одному из конечных, последовательно читая символы на ленте. Говорят, что цепочка входных символов \emph{допускается} конечным автоматом, если в результате работы автомата она прочитывается целиком, а автомат после этого находится в одном из конечных состояний. В противном случае, говорят, что цепочка \emph{не допускается} данным автоматом. Для отображения конечного автомата часто используют ориентированный граф, вершины которого соответствуют состояниям автомата, а дуги~--- правилам переходов. При этом дуга из вершины $q_1$ в вершину $q_2$ имеет метку $a$ тогда и только тогда, когда автомат содержит правило перехода $q_1 a \rightarrow q_2$, т.е. метками дуг могут быть символы входного алфавита или символ $\lambda$. На рисунке \ref{Pic:fa_example1} показан автомат $\mathcal{F}_1$, который формально определяется как пятёрка $(\{a, b\}, \{q_1, q_2, q_3, q_4\}, q_1, \{q_4\}, \delta)$ со следующими правилами переходов $\delta$: $$ \begin{array}{lc} q_1 a \rightarrow q_2 & (1)\\ q_1 b \rightarrow q_2 & (2)\\ q_2 b \rightarrow q_3 & (3)\\ q_2 b \rightarrow q_4 & (4)\\ q_4 \lambda \rightarrow q_2 & (5)\\ q_4 a \rightarrow q_3 & (6)\\ q_4 a \rightarrow q_4 & (7) \end{array} $$ Начальные и конечные вершины отображаются специальным образом (с входящими и выходящими стрелками)~--- это всего лишь способ обозначения вершин, а не нарушение определения графа, согласно которому не бывает дуг, не связывающих вершины. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{fa_example1.eps} \caption{Конечный автомат, в виде ориентированного графа} \label{Pic:fa_example1} \end{center} \end{figure} Рассмотрим пример работы этого автомата. Пусть на вход подаётся цепочка $a b b a a$, последовательность шагов представлена в таблице: \begin{center} \begin{tabular}{|c|c|c|c|} \hline \textbf{Шаг} & \textbf{Состояние} & \textbf{Входная цепочка} & \textbf{Правило}\\ \hline 1 & $q_1$ & $ a b b a a$ & 1\\ \hline 2 & $q_2$ & $ b b a a$ & 4\\ \hline 3 & $q_4$ & $ b a a$ & 5\\ \hline 4 & $q_2$ & $ b a a$ & 4\\ \hline 5 & $q_4$ & $ a a$ & 7\\ \hline 6 & $q_4$ & $ a$ & 6\\ \hline 7 & $q_3$ & $\lambda$ & конец\\ \hline \end{tabular} \end{center} Входная цепочка \emph{допускается} конечным автоматом, но это видно лишь при такой последовательности шагов. Однако, в ходе работы встретилось несколько альтернатив, связанных с наличием $\lambda$-переходов и правил с одинаковыми левыми частями. Т.е. блок управления должен быть снабжён дополнительным устройством выбора в таких спорных ситуациях (назовём его ``чёртиком''), чтобы работа автомата не зашла в тупик. Рассмотрим пример другой цепочки~--- $a a b$: \begin{center} \begin{tabular}{|c|c|c|c|} \hline \textbf{Шаг} & \textbf{Состояние} & \textbf{Входная цепочка} & \textbf{Правило}\\ \hline 1 & $q_1$ & $a a b$ & 1\\ \hline 2 & $q_2$ & $a b$ & ошибка\\ \hline \end{tabular} \end{center} Эта цепочка не допускается данным конечным автоматом. \begin{center} \begin{tabular}{|p{12cm}|} \hline \emph{Задание для самоподготовки}. Для заданного конечного автомата $\mathcal{F}(\{a, b\}, \{q_1, q_2, q_3, q_4, q_5\}, q_1, \{q_5\}, \delta)$, где $\delta$: $$ \begin{array}{c} q_1 a \rightarrow q_2\\ q_2 b \rightarrow q_3\\ q_3 a \rightarrow q_3\\ q_3 b \rightarrow q_3\\ q_3 b \rightarrow q_4\\ q_4 a \rightarrow q_5\\ q_5 \lambda \rightarrow q_1, \end{array} $$ проверить допустимость цепочек $a b b a$, $ a b b b a a b a a b a $ и $ a b b b a b$. Можно ли выписать регулярное выражение, задающее все допускаемые данным автоматом цепочки? \\ \hline \end{tabular} \end{center} \paragraph{Теорема Клини} На самом деле, между регулярными языками и конечными автоматами существует непосредственная связь. В теореме Клини доказывается, что язык допускается некоторым конечным автоматом тогда и только тогда, когда он регулярный. Таким образом, мы можем для каждого регулярного языка построить конечный автомат, который будет проверять принадлежность цепочек данному языку, и, обратно, для любого конечного автомата можно получить язык допускаемых слов, и этот язык будет регулярным. Рассмотрим первую задачу~--- получение конечного автомата по известному регулярному языку (или выражению). Мы можем выписать \emph{элементарные} автоматы, которые допускают цепочки из одинарных букв алфавита и расширить их автоматами для операций (см. рисунок \ref{Pic:fa_from_lang}). \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{fa_from_lang.eps} \caption{Получение конечного автомата по регулярному языку} \label{Pic:fa_from_lang} \end{center} \end{figure} Рассмотрим пример: регулярный язык $\mathcal{L}'$ задан регулярным выражением $ a b (a + b)^* b^+$. Соответствующий автомат представлен на рисунке \ref{Pic:fa_example2}. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{fa_example2.eps} \caption{Конечный автомат, соответствующий языку $\mathcal{L}'$} \label{Pic:fa_example2} \end{center} \end{figure} % семинар 7 Для получения регулярного языка, допускаемого конечным автоматом, в общем случае необходимо решить систему уравнений в полукольце языков (аналогично решалась задача поиска кратчайших расстояний в графе): $\mathcal{L} (2^{V^*}, \cup, \cdot, \varnothing, \{\lambda\})$. Не трудно убедиться, что это идемпотентное полукольцо с итерацией, в котором мы можем решать уравнение вида $x = a x + b$ (см. выше). Чтобы получить систему уравнений, необходимо построить матрицу переходов для графа конечного автомата. Рассмотрим пример, в котором получить регулярное выражение без составления конечного автомата и системы уравнений достаточно сложно. Рассмотрим алфавит $\{0, 1\}$, необходимо получить регулярное выражения для языка, содержащего только чётное число единиц и чётное число нулей. Попытки придумать регулярное выражение ``в лоб'' (например, $((00)^* + (11)^*)^*$) дадут только частные случаи. Построим конечный автомат, допускающий цепочки такого языка: очевидно, что возможно только четыре состояния: ``чётное число нулей и единиц'', ``чётное число нулей, нечётное~--- единиц'', ``нечётное число нулей и единиц'' и ``нечётное число нулей и чётное число единиц'', автомат со всеми возможными переходами показан на рисунке \ref{Pic:fa_example3}. \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{fa_example3.eps} \caption{Конечный автомат, допускающий цепочки с чётным числом нулей и единиц} \label{Pic:fa_example3} \end{center} \end{figure} $$ A = \left(\begin{array}{cccc} \varnothing & 1 & \varnothing & 0\\ 1 & \varnothing & 0 & \varnothing\\ \varnothing & 0 & \varnothing & 1\\ 0 & \varnothing & 1 & \varnothing \end{array}\right) $$ Каждому состоянию $q_i$ конечного автомата ставится в соответствие переменная $x_i$. Значение этой переменной суть есть регулярное выражение, задающее все слова, которые допускаются конечным автоматом, стартующем из данного состояния. Очевидно, что язык, допускаемый конечным автоматом получается сложением переменных всех стартовых состояний. Каждой строке матрицы соответствует одно уравнение, при этом всем уравнениям, соответствующим конечным состояниям автомата, необходимо прибавить $\lambda$. В нашем примере получается следующая система уравнений, которая имеет решение: $$ \begin{array}{c} \begin{array}{cc} \left\{\begin{array}{l} x_1 = 1 \cdot x_2 + 0 \cdot x_4 + \lambda\\ x_2 = 1 \cdot x_1 + 0 \cdot x_3\\ x_3 = 0 \cdot x_2 + 1 \cdot x_4\\ x_4 = 0 \cdot x_1 + 1 \cdot x_3 \end{array}\right. & \left\{\begin{array}{l} x_1 = 1 \cdot x_2 + 0 \cdot (0 \cdot x_1 + 1 \cdot x_3) + \lambda\\ x_2 = 1 \cdot x_1 + 0 \cdot x_3\\ x_3 = 0 \cdot x_2 + 1 \cdot (0 \cdot x_1 + 1 \cdot x_3) \end{array}\right. \\ \left\{\begin{array}{l} x_1 = 0 0 \cdot x_1 + 1 \cdot x_2 + 0 1 \cdot x_3 + \lambda\\ x_2 = 1 \cdot x_1 + 0 \cdot x_3\\ x_3 = 1 1 \cdot x_3 + 0 \cdot x_2 + 1 0 \cdot x_1 \end{array}\right. & \left\{\begin{array}{l} x_3 = (1 1)^*(0 \cdot x_2 + 1 0 \cdot x_1)\\ x_1 = 0 0 \cdot x_1 + 1 \cdot x_2 + 0 1 \cdot x_3 + \lambda\\ x_2 = 1 \cdot x_1 + 0 \cdot x_3 \end{array}\right. \end{array}\\ \left\{\begin{array}{l} x_1 = 0 0 \cdot x_1 + 1 \cdot x_2 + 0 1 (1 1)^*(0 \cdot x_2 + 1 0 \cdot x_1) + \lambda\\ x_2 = 1 \cdot x_1 + 0 (1 1)^*(0 \cdot x_2 + 1 0 \cdot x_1) \end{array}\right.\\ \left\{\begin{array}{l} x_1 = 0 0 \cdot x_1 + 1 \cdot x_2 + 0 1 (1 1)^* 0 \cdot x_2 + 0 1 (1 1)^* 1 0 \cdot x_1 + \lambda\\ x_2 = 0 (1 1)^* 0 \cdot x_2 + (1 + 0 (1 1)^* 1 0) \cdot x_1 \end{array}\right.\\ \left\{\begin{array}{l} x_2 = (0 (1 1)^* 0)^* (1 + 0 (1 1)^* 1 0) \cdot x_1\\ x_1 = (0 0 + 0 1 (1 1)^* 1 0) \cdot x_1 + (1 + 0 1 (1 1)^* 0) \cdot x_2 + \lambda \end{array}\right.\\ x_1 = (0 0 + 0 1 (1 1)^* 1 0) \cdot x_1 + (1 + 0 1 (1 1)^* 0) (0 (1 1)^* 0)^* (1 + 0 (1 1)^* 1 0) \cdot x_1 + \lambda\\ x_1 = (0 0 + 0 1 (1 1)^* 1 0 + (1 + 0 1 (1 1)^* 0) (0 (1 1)^* 0)^* (1 + 0 (1 1)^* 1 0)) \cdot x_1 + \lambda\\ x_1 = (0 0 + 0 1 (1 1)^* 1 0 + (1 + 0 1 (1 1)^* 0) (0 (1 1)^* 0)^* (1 + 0 (1 1)^* 1 0)) \end{array} $$ Таким образом, регулярное выражение для языка, допускаемого автоматом, равно: $$ 0 0 + 0 1 (1 1)^* 1 0 + (1 + 0 1 (1 1)^* 0) (0 (1 1)^* 0)^* (1 + 0 (1 1)^* 1 0), $$ а сам язык: $$ L = \{00, 01(11)^k10, \{1, 01(11)^l\}(0 (1 1)^m 0)^n\{1, 0 (1 1)^o 10\} | k, l, m, n, o \in \mathbb{N}_0\}. $$ \paragraph{Детерминизация конечных автоматов} Выше уже было сказано о том, что при работе конечного автомата возможны ``конфликтные ситуации'', когда существует два правила с одинаковой левой частью или $\lambda$-переходы~--- в этом случае необходимо ``знать заранее'', какой путь следует выбрать, чтобы цепочка всё же была прочитана. Такой подход очень неудобен в реализации, поэтому возникает задача \emph{детерминизации} конечного автомата, т.е. приведение его к такому виду, что ``конфликтные ситуации не возможны'', а язык, допускаемый автоматом, не изменяется. Существует формальный алгоритм детерминизации автомата, который состоит из двух шагов: \begin{itemize} \item удаление $\lambda$-переходов; \item собственно детерминизация. \end{itemize} Для данного автомата $M = (V, Q, q_0, F, \delta)$, автомат без $\lambda$-переходов будет иметь вид: $$ M' = (V, Q', q_0, F', \delta'), $$ где множество вершин $Q' = \{ q_0 \} \cup \{ q | \exists r)(r \rightarrow q \And \mu(r, q) \neq \lambda \}$, т.е. начальная вершина плюс все вершины, в которые входит хотя бы одна не-$\lambda$-дуга; множество конечных вершин $F' = (F \cap Q') \cup \{ q | q \in Q' \And q \Rightarrow_\lambda^+ q_f \in F\}$, т.е. множество оставшихся конечных вершин плюс все вершины, достижимые из конечных по $\lambda$-путям (одна или набор $\lambda$-дуг); множество правил перехода $\delta'$~--- оставляются только не-$\lambda$-переходы, к ним добавляются переходы, следующими за $\lambda$-путями из данной вершины (т.е. для $\forall p, q, r: p \Rightarrow_\lambda^+ q \rightarrow_a r, a \in V$ в $\delta'$ добавляется правило $ p a \rightarrow r$). Рассмотрим пример: на рисунке \ref{Pic:fa_example4} показаны автоматы с $\lambda$-переходами и без~--- при этом они допускают один и тот же язык. \begin{figure}[tbh] \begin{center} \includegraphics[width=12cm]{fa_example4.eps} \caption{Удаление $\lambda$-переходов} \label{Pic:fa_example4} \end{center} \end{figure} Детерминизация производится построением новых вершин и переходов. При этом в качестве вершин графа автомата могут теперь выступать не отдельные состояния изначального автомата, а\emph{наборы} состояний, например $\{ q_0, q_2, q_3\}$. В качестве нового исходного состояния принимается состояние $\{q_0\}$. Далее для всех букв алфавита строятся новые вершины, в которые можно попасть из данной вершины. Для нашего примера все новые состояния и переходы будут выглядеть так: $$ \begin{array}{l} \delta'(\{q_1\}, a) = \{q_4\}\\ \delta'(\{q_1\}, b) = \{q_3\}\\ \delta'(\{q_3\}, a) = \{q_1, q_4\}\\ \delta'(\{q_3\}, b) = \{q_2, q_4\}\\ \delta'(\{q_4\}, a) = \{q_1, q_4\}\\ \delta'(\{q_4\}, b) = \{q_2, q_4\}\\ \delta'(\{q_1, q_4\}, a) = \{q_1, q_4\}\\ \delta'(\{q_1, q_4\}, b) = \{q_2, q_3, q_4\}\\ \delta'(\{q_2, q_4\}, a) = \{q_1, q_4\}\\ \delta'(\{q_2, q_4\}, b) = \{q_2, q_3, q_4\}\\ \delta'(\{q_2, q_3, q_4\}, a) = \{q_1, q_4\}\\ \delta'(\{q_2, q_3, q_4\}, b) = \{q_2, q_3, q_4\} \end{array} $$ Новыми конечными вершинами являются все вершины, содержащие в себе хоть одну из конечных вершин исходного автомата: $\{q_4\}$, $\{q_1, q_4\}$, $\{q_2, q_4\}$, $\{q_2, q_3, q_4\}$. Новые вершины можно переименовать. Граф детерминизированного автомата показан на рисунке \ref{Pic:fa_example4d}. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{fa_example4d.eps} \caption{Детерминизированный автомат} \label{Pic:fa_example4d} \end{center} \end{figure} Существует теорема, согласно которой для каждого автомата может быть построен эквивалентный (допускающий тот же язык) автомат. Это позволяет для любого регулярного языка построить детерминизированный автомат. Из этой теоремы есть интересное следствие~--- с помощью детерминизированного автомата можно получать автоматы \emph{не допускающие} заданную цепочку. Для этого необходимо в детерминизированном автомате, допускающем данную цепочку, взять в качестве конечных вершин дополнение относительно всех вершин: $F' = Q \setminus F$. Рассмотрим пример~--- необходимо получить автомат (в алфавите $\{a, b\}$), не допускающий идущих подряд букв $a b$. На рисунке \ref{Pic:fa_example5} показан исходный автомат, допускающий все слова, содержащие подряд $a b$, затем тот же автомат, но детерминизированный. Третьим показан автомат, не досускающий цепочки, содержащие подряд $a b$. В данном случае две правые вершины в последнем автомате можно объединить как \emph{неверные состояния}, в том смысле, что попав туда, автомат заведомо не прочитает заданную цепочку. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{fa_example5.eps} \caption{Детерминизация и дополнение конечного автомата} \label{Pic:fa_example5} \end{center} \end{figure} % семинар 8 Помимо отрицания языка (язык~--- множество слов, а значит и все множественные операции к нему применимы), благодаря теореме о детерминизации, можно заключить следующее про регулярные языки: $\overline{L} = V^* \setminus L$~--- дополнение к языку является регулярным, $L_{or} = L_1 \cup L_2$~--- объединение двух регулярных языков по определению регулярно. А значит, $L_{and} = L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$ пересечение двух регулярных языков является регулярным языком. \paragraph{Лемма о разрастании} Для регулярных языков существует интересная \emph{лемма}: \begin{quote} Если $L \subseteq V^*$~--- регулярный язык, то $\exists k_L \in \mathbb{N}: \forall x \in L \And |x| \geqslant k_L x = u v w, \mbox{где}\, |v| > 0 \And |v| \leqslant k_L \And (\forall n \geqslant 0) (u v^n w \in L)$. \end{quote} Другими словами, в любом регулярном языке можно найти такую непустую последовательность символов, что её исключение или повторение любое число раз оставит новое слово в данном языке. Мы можем ``накачивать'' часть слова, и оставаться в рамках языка. Рассмотрим пример. В регулярном языке, задаваемом выражением $a^*(a + b)^+$ можно найти такое разбиение цепочки $x = a^n (a^m b^k)^l: u = \lambda, v = a, w = (a^m b^k)^l$. ``Накачивая'' цепочку $v$ мы остаёмся в рамках языка. Однако, эта лемма часто применяется для доказательства нерегулярности языков. Если удаётся показать, что она не выполняется для любой цепочки $x$ в языке $L$, то можно заключить, что этот язык не регулярный. Например, язык $L = \{ a^n b^n | n \in \mathbb{N}\}$. Слова в этом языке имеют вид $ a a a \dots a a b b b \dots b b$, с одинаковым числом символов $a$ и $b$. Мы можем разбить слово следующим образом: \begin{itemize} \item $u = \lambda, v = a^n b^n, w = \lambda$, но в этом случае, накачивая $v$, слово $ (a^n b^n) (a^n b^n) \dots (a^n b^n)$ уже не будет принадлежать нашему языку. По аналогии, можно отвергнуть все разбиения, в которых $v$ содержит как символы $a$, так и символы $b$; \item $u = \lambda, v = a^n, w = b^n$, но тогда слова вида $a^{2 n} b^n$, $a^{3 n} b^n$ и т.п. уже не будут принадлежать языку, так как число символов $a$ и $b$. \end{itemize} Аналогично можно рассмотреть все остальные случаи. Очевидно, что лемма не выполняется, а это значит, что язык этот нерегулярный. Для доказательства нерегулярности других языков иногда требуется использовать свойства регулярных языков. Например, требуется доказать нерегулярность языка всех двойных слов $L_d = \{ y y | y \in V^*\}$. Формулировка языка не позволяет напрямую применить лемму о разрастании (в $y$ может попадать что угодно). В данном случае можно воспользоваться тем, что пересечение регулярных языков регулярно. Допустим, язык $L_d$ регулярен, тогда его пересечение с языком, задаваемым выражением: $a^* b a^* b$, равное $L_d \cup \{a^n b a^m b | n, m \in \mathbb{N}_0\} = \{a^k b a^k b | k \in \mathbb{N}_0\}$ должно быть регулярным, а уже регулярность последнего можно легко опровергнуть леммой о разрастании~--- также как и в предыдущем примере. \paragraph{О грамматиках} Мы рассматривали языки как множество слов (собственно определение языка), как способ простого описания этого множества (регулярные выражения) и как средство по их распознаванию (конечные автоматы). Все эти описания в определенном смысле эквивалентны. Существует еще один способ задания языков~--- с точки зрения генерации всех слов языка (т.е. способ, обратный распознаванию и автоматам). При этом вводится понятие \emph{грамматики}: $$ \mathcal{G} = (V, N, S, P), $$ где $V$~--- алфавит символов языка (называемый также \emph{терминальным алфавитом}), $N$~--- алфавит служебных символов (\emph{нетерминальный алфавит})~--- он не пересекается с терминальным алфавитом $V \cap N = \varnothing$, $S \in N$~--- аксиома и $P$~--- конечное множество правил вывода вида $$ P: \alpha \rightarrow \beta, $$ где $\alpha \in (V \cup N)^* N (V \cup N)^*$, т.е. множество слов из символов обоих алфавитов, но содержащее по крайней мере один нетерминальный символ, $\beta \in (V \cup N)^*$. Набор правил вида $\alpha \rightarrow \beta_1, \alpha \rightarrow \beta_2, \dots$ обычно сокращают как $\alpha \rightarrow \beta_1 | beta_2 | \dots$. Каждое слово языка получается из последовательного применения правил, начиная от аксиомы. В этом случае говорят, что язык \emph{порождается} грамматикой. Рассмотрим пример грамматики арифметических выражений с одной переменной: $$ \mathcal{G}_0 = (\{x, (, ), +, *\}, \{E, T, F\}, E, P), P: $$ $$ \begin{array}{l} E \rightarrow E + T\, |\, T\\ T \rightarrow T * F\, |\, F\\ F \rightarrow ( E )\, |\, x\\ \end{array} $$ Используя данную грамматику мы можем построить например такое выражение, применяя правило к самому левому нетерминалу: $$ \begin{array}{c} E \vdash E + T \vdash E + T + T \vdash T + T \vdash T * F + T \vdash F * F + T \vdash (E) * F + T \vdash \\ \vdash (E + T) * F + T \vdash (T + T) * F + T \vdash (F + T) * F + T \vdash (x + T) * F + T \vdash\\ \vdash (x + F) * F + T \vdash (x + x) * F + T \vdash (x + x) * x + T \vdash (x + x) * x + F \vdash \\ \vdash (x + x) * x + x \end{array} $$ Видно, что в нетерминальные символы вкладывается определённый синтаксический смысл. Например, в грамматике языка программирования нетерминальными символами являются понятия ``выражение'', ``оператор'', ``условие'' и т.п. Существует классификация грамматик~--- в зависимости от того, какой вид имет правила вывода, языки принадлежат к разным классам. Например, если во всех правилах вывода $\alpha \rightarrow \beta$ цепочки $\alpha \in N$, а $\beta \in (V \cup N)^*$, то такие грамматики называются \emph{контекстно-свободными} (это большинство искусственных языков). Нас больше всего интересует случай, когда правила имеют вид: $$ \begin{array}{l} A \rightarrow a B,\\ A \rightarrow a,\\ A \rightarrow B,\\ A \rightarrow \lambda, \end{array} $$ где $A, B \in N$, a $a \in V$. Такие грамматики называют \emph{регулярными}. Существует теорема о том, что для любого регулярного языка можно построить не только конечный автомат, который допускает данный язык, но и регулярную грамматику, которая порождает данный язык. Чтобы получить регулярную грамматику по конечному автомату необходимо: \begin{itemize} \item в качестве терминального алфавита взять входной алфавит $V$; \item множество нетерминальных символов будет содержать состояния конечного автомата $N = \{q_1, q_2, \dots, q_n\}$; \item аксиома совпадает с начальным состоянием автомата; \item правила вывода могут быть получены из правил переходов следующим образом: \begin{itemize} \item если $q a \rightarrow r \in \delta$, т.е. существует переход по символу $a$, то необходимо добавить правило вывода $q \rightarrow a r$; \item если и только если $q a \rightarrow q_f \in \delta$, где $q_f \in F$~--- оно из завершающих состояний, то добавляется правило вывода $q \rightarrow a$. \end{itemize} \end{itemize} Обратный процесс аналогичен. \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{fa_example6.eps} \caption{Пример конечного автомата} \label{Pic:fa_example6} \end{center} \end{figure} Например, для конечного автомата, изображённого на рисунке, грамматика будет иметь вид: $$ \mathcal{G} = (\{a, b\}, \{q_1, q_2, q_3\}, q_1, P), P: $$ $$ \begin{array}{l} q_1 \rightarrow a q_1 | b q_1 | a q_2\\ q_2 \rightarrow b q_3 | b\\ q_3 \rightarrow a q_3 | b q_3 | a | b \end{array} $$ \paragraph{Минимизация автоматов с выходом} Помимо конечных автоматов, что мы рассматривали ранее, существуют \emph{автоматы с выходом}, т.е. автоматы, преобразующие слово входного языка в слово выходного языка. Такие автоматы обычно применяются при кодировании/декодировании информации. Будем задавать конечный автомат с выходом следующей пятёркой: $$ \mathcal{F}_o (A, B, Q, q_0, f, g), $$ где $A$~--- входной алфавит, $B$~--- выходной алфавит (может в частном случае совпадать со входным), $Q$~--- множество состояний автомата, $q_0 \in Q$~--- начальное состояние, $f: Q \times A \rightarrow Q$~--- функция переходов, аналогичная $\delta$ в определении конечного автомата, $g: Q \times A \rightarrow B$~--- функция выходов~--- какой символ будет получен на выход на каждом шаге работы автомата. Конечным состоянием в этом случае мы полагаем любое из состояний автомата. Также, мы будем рассматривать только детерминированные автоматы с выходом. Рассмотрим пример. Пусть необходимо построить автомат, заменяющий каждую третью единицу в двоичном слове на ноль. В виде графа он может быть представлен следующим образом: \begin{figure}[tbh] \begin{center} \includegraphics[width=8cm]{fao_example1.eps} \caption{Конечный автомат с выходом, заменяющий каждую третью единицу} \label{Pic:fao_example1} \end{center} \end{figure} Работа автомата на примере цепочки ``10100110'' показана в таблице: \begin{center} \begin{tabular}{|c|c|c|c|} \hline \textbf{Шаг} & \textbf{Состояние} & \textbf{Входная цепочка} & \textbf{Выходная цепочка}\\ \hline 1 & $q_1$ & 10100110 & $\lambda$\\ \hline 2 & $q_2$ & 0100110 & 1\\ \hline 3 & $q_2$ & 100110 & 10\\ \hline 4 & $q_3$ & 00110 & 101\\ \hline 5 & $q_3$ & 0110 & 1010\\ \hline 6 & $q_3$ & 110 & 10100\\ \hline 7 & $q_1$ & 10 & 101000\\ \hline 8 & $q_2$ & 0 & 1010001\\ \hline 9 & $q_2$ & $ \lambda $ & 10100010\\ \hline \end{tabular} \end{center} Для таких автоматов существует задача \emph{минимизации}~--- получения эквивалентного (дающего тот же выход по заданному входу) автомата с меньшим числом состояний. Существует алгоритм минимизации автомата с выходом. В основе этого алгоритма лежит понятие \emph{эквивалентных состояний}. Два состояния считаются эквивалентными, если они генерируют один и тот же выход по заданному входу. Таким образом, можно разбить всё множество состояний на классы эквивалентности. Алгоритм минимизации состоит из следующих шагов: \begin{enumerate} \item удаление недостижимых вершин, т.е. всех таких вершин, в которые нельзя попасть из начальной при любой входной цепочке; \item разбиение множества всех вершин на начальные классы эквивалентности $I_1$, $I_2$, $I_3$, $I_4$ (очевидно, что их может быть не более четырёх); \item для каждого состояния и входного символа получить класс эквивалентности, в одно из состояний которого мы попадаем по данному переходу. Эти результаты можно объединить в таблице: \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline & $q_1$ & $q_2$ & $\dots$ & $q_n$\\ \hline $a_1$ & $I_k$ & $I_j$ & $\dots$ & $\dots$\\ \hline $\dots$ & $\dots$ & $\dots$ & $\dots$ & $\dots$\\ \hline $a_m$ & $I_l$ & $I_p$ & $\dots$ & $\dots$\\ \hline \end{tabular} \end{center} \item на основании полученных переходов разбиваем существующие классы эквивалентности $I_j$, так, чтобы все состояния, входящие в один класс, переходили в одни и те же классы эквивалентности по заданному входу. Другими словами, выделяем в полученной таблице одинаковые столбцы и группируем согласно ним состояния автомата~--- если эти группы пересекаются с классами эквивалентности, то их необходимо разбить; \item повторить два предыдущих этапа пока на очередной итерации не получится набор классов эквивалентности, аналогичный предыдущему шагу; \item заменить каждый из классов эквивалентности новым состоянием. \end{enumerate} Рассмотрим пример. На рисунке \ref{Pic:fao_example2} показан автомат с выходом. \begin{figure}[tbh] \begin{center} \includegraphics[width=10cm]{fao_example2.eps} \caption{Пример конечного автомата с выходом} \label{Pic:fao_example2} \end{center} \end{figure} Недостижимых вершин в этом автомате нет, так что переходим ко второму этапу. Можно выделить два класса эквивалентности: $I_1 = \{q_1, q_4, q_5, q_6\}$ и $I_2 = \{q_2, q_3\}$. Далее строим таблицу переходов: \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline & $q_1$ & $q_2$ & $q_3$ & $q_4$ & $q_5$ & $q_6$\\ \hline 0 & $I_1$ & $I_1$ & $I_1$ & $I_2$ & $I_1$ & $I_1$\\ \hline 1 & $I_1$ & $I_1$ & $I_1$ & $I_2$ & $I_1$ & $I_1$\\ \hline \end{tabular} \end{center} Видно, что $q_4$ должно быть отделено в свой собственный класс эквивалентности. Класс эквивалентности $I_2$ не меняется: $I_1 = \{q_1, q_5, q_6\}$, $I_2 = \{q_2, q_3\}$ и $I_3 = \{ q_4\}$. Снова строим таблицу: \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline & $q_1$ & $q_2$ & $q_3$ & $q_4$ & $q_5$ & $q_6$\\ \hline 0 & $I_3$ & $I_1$ & $I_1$ & $I_2$ & $I_3$ & $I_3$\\ \hline 1 & $I_3$ & $I_1$ & $I_1$ & $I_2$ & $I_3$ & $I_3$\\ \hline \end{tabular} \end{center} Все классы остаются неизменными, значит мы дошли до конца алгоритма. Результат минимизации показан на рисунке \ref{Pic:fao_example2_min}. \begin{figure}[tbh] \begin{center} \includegraphics[width=6cm]{fao_example2_min.eps} \caption{Пример конечного автомата с выходом} \label{Pic:fao_example2_min} \end{center} \end{figure} \end{document}