\documentclass[spec, och, labwork2]{SCWorks} \usepackage{preamble} \begin{document} \include{titlepage.tex} \tableofcontents \section{Постановка задачи} Цель работы --- изучение основных свойств бинарных отношений и операций замыкания бинарных отношений. Порядок выполнения работы: \begin{enumerate} \item Разобрать основные определения видов бинарных отношений и разработать алгоритмы классификации бинарных отношений; \item Изучить свойства бинарных отношений и рассмотреть основные системы замыкания на множестве бинарных отношений; \item Разработать алгоритмы построения основных замыканий бинарных отношений. \end{enumerate} \section{Теоретические сведения} \subsection{Основные определения видов бинарных отношений} Подмножества декартова произведения $A_1 \times \dots \times A_n$ множеств $A_1, \dots, A_n$ называются $n$-ыми отношениями между элементами множеств $A_1, \dots, A_n$. Подмножества декартова произведения $A \times B$ множеств $A$ и $B$ называются бинарными отношениями между элементами множеств $A$ и $B$. Для бинарного отношения $\rho \subset A \times B$ область определения $D_\rho$ и множество значений $E_\rho$ определяется как подмножества соответствующих множеств $A$ и $B$ по следующим формулам: \begin{align*} D_\rho &= \left\{ a: (a, b) \in \rho \text{ для некоторого } b \in B \right\} \\ E_\rho &= \left\{ b: (a, b) \in \rho \text{ для некоторого } a \in A \right\} \end{align*} Бинарное отношение $\rho \subset A \times A$ называется: \begin{enumerate} \item \textit{рефлексивным}, если $(\forall a \in A) ~ (a, a) \in \rho$; \item \textit{антирефлексивным}, если $(\forall a \in A) ~ (a, a) \not\in \rho$; \item \textit{симметричным}, если $(\forall a, b \in A) ~ (a, b) \in \rho \implies (b,a) \in \rho$; \item \textit{антисимметричным}, если $(\forall a, b \in A) ~ (a, b) \in \rho \land (b, a) \in \rho \implies a = b$; \item \textit{транзитивным}, если $(\forall a, b, c \in A) ~ (a, b) \in \rho \land (b, c) \in \rho \implies (a, c) \in \rho$. \end{enumerate} Символом $\Delta_A$ обозначается тождественное отношение на множестве $A$, которое определяется по формуле: $\Delta_A = \{ (a, a) | a \in A \}$. Тогда бинарное отношение $\rho \subset A \times A$ является: \begin{itemize} \item \textit{рефлексивным} $\iff$ $\Delta_A \subset \rho$. Это означает, что бинарное отношение $\rho$ рефлексивно, если $M(\rho) \geq E$, где $E$ --- единичная матрица. Если же матрица $M(\rho)$ несравнима с единичной матрицей, то бинарное отношение $\rho$ не является рефлексивным; \item \textit{симметричным} $\iff$ $\rho^{-1} \subset \rho$. Это означает, что бинарное отношение $\rho$ симметрично, если $M(\rho) \geq M(\rho)^T$, где $M(\rho)^T$ – транспонированная матрица бинарного отношения $\rho$. Если же матрица $M(\rho)$ несравнима с $M(\rho)^T$, то бинарное отношение $\rho$ не является симметричным; \item \textit{антисимметричным} $\iff$ $\rho \cap \rho^{-1} \subset \Delta_A$. Это означает, что бинарное отношение $\rho$ антисимметрично, если $E \geq M(\rho) \otimes M(\rho)^T$ (значения элементов вне главной диагонали матрицы $M(\rho) \otimes M(\rho)^T$ равны нулю), где $\otimes$ --- операция поэлементного умножения матриц; \item \textit{транзитивным} $\iff$ $\rho \rho \subset \rho$. Это означает, что бинарное отношение $\rho$ транзитивно, если $M(\rho)M(\rho) \leq M(\rho)$. \end{itemize} Классификация бинарных отношений: \begin{enumerate} \item Рефлексивное и транзитивное отношение называется отношением \textit{квазипорядка}. \item Рефлексивное, симметричное и транзитивное отношение называется отношением \textit{эквивалентности}. \item Рефлексивное, антисимметричное и транзитивное отношение называется отношением \textit{частичного порядка}. \item Антирефлексивное, антисимметричное и транзитивное отношение называется отношением \textit{строгого порядка}. \end{enumerate} \subsection{Основные системы замыкания на множестве бинарных отношений} \begin{definition} Оператором замыкания на множестве A называется отображение $f$ множества всех подмножеств $P(A)$ в себя, удовлетворяющее условиям: \begin{enumerate} \item $X \subset Y \implies f(X) \subset f(Y)$; \item $X \subset f(X)$; \item $ff(X) = f(X)$. \end{enumerate} $\forall X, Y \in P(A)$. \end{definition} \begin{definition} Для подмножества $X \in A$ значение $f(X)$ называется замыканием подмножества $X$. \end{definition} \begin{definition} Множество Z подмножеств множества A называется \textit{системой замыканий}, если оно замкнуто относительно пересечений, т.е. выполняется \begin{equation*} (\forall B \subset Z) ~ \bigcap B \in Z \end{equation*} \end{definition} \begin{lemma}[О системах замыканий бинарных отношений] На множестве $P(A^2)$ всех бинарных отношений между элементами множества $A$ следующие множества являются системами замыканий: \begin{enumerate} \item $Z_r$ - множество всех рефлексивных бинарных отношений между элементами множества $A$; \item $Z_s$ – множество всех симметричных бинарных отношений между элементами множества $A$; \item $Z_t$ – множество всех транзитивных бинарных отношений между элементами множества $A$; \item $Z_{eq} = Eq(A)$ – множество всех отношений эквивалентности на множестве $A$. \end{enumerate} Множество $Z_{as}$ всех антисимметричных бинарных отношений между элементами множества $A$ не является системой замыкания. \end{lemma} \begin{lemma} На множестве $P(A^2)$ всех бинарных отношений между элементами множества A следующие отображения являются операторами замыканий: \begin{enumerate} \item $f_r(\rho) = \delta \cup \Delta_A$ --- наименьшее рефлексивное бинарное отношение, содержащее отношение $\rho \subset A^2$; \item $f_s(\rho) = \delta \cup \delta^{-1}$ --- наименьшее симметричное бинарное отношение, содержащее отношение $\rho \subset A^2$; \item $f_t(\rho) = \bigcup_{n = 1}^\infty \rho^n$ наименьшее транзитивное бинарное отношение, содержащее отношение $\rho \subset A^2$; \item $f_{eq} = f_t f_s f_r (\rho)$ наименьшее отношение эквивалентности, содержащее отношение $\rho \subset A^2$; \end{enumerate} \end{lemma} \section{Алгоритмы классификации бинарных отношений} %%% \subsection{Проверка бинарного отношения на рефлексивность} \textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является рефлексивным>> или <<Отношение не является рефлексивным>>. \begin{enumerate} \item Взять диагональ матрицы $d(M) = \{ m_{ii} | i = \overline{1, N} \}$; \item Если $\exists a = 0 \in d(M)$, то ответ <<Отношение не является рефлексивным>>; \item Иначе ответ <<Отношение является рефлексивным>>. \end{enumerate} Трудоёмкость алгоритма --- $O(N)$. %%% \subsection{Проверка бинарного отношения на антирефлексивность} \textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является антирефлексивным>> или <<Отношение не является антирефлексивным>>. \begin{enumerate} \item Взять диагональ матрицы $d(M) = \{ m_{ii} | i = \overline{1, N} \}$; \item Если $\exists a = 1 \in d(M)$, то ответ <<Отношение не является антирефлексивным>>; \item Иначе ответ <<Отношение является антирефлексивным>>. \end{enumerate} Трудоёмкость алгоритма --- $O(N)$. %%% \subsection{Проверка бинарного отношения на симметричность} \textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является симметричным>> или <<Отношение не является симметричным>>. \begin{enumerate} \item Вычислить транспонированную матрицу $M^T$; \item Если $M = M^T$, то ответ <<Отношение является симметричным>>; \item Иначе ответ <<Отношение не является симметричным>>. \end{enumerate} Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$, а сравнение двух матриц имеет трудоёмкость $O(N^2)$. Таким образом, трудоёмкость алгоритма --- $O(N^2) = O(N^2) + O(N^{3/2} \log N)$. %%% \subsection{Проверка бинарного отношения на антисимметричность} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является антисимметричным>> или <<Отношение не является антисимметричным>>. \begin{enumerate} \item Вычислить транспонированную матрицу $M^T$; \item Вычислить матрицу $(a_{ij}) = A = M \otimes M^T$; \item Если $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) : i \ne j$ выполняется $(a_{ij} = 0)$, то ответ <<Отношение является антисимметричным>>; \item Иначе ответ <<Отношение не является антисимметричным>>. \end{enumerate} Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$, а поэлементное умножение матриц --- $O(N^2)$. Таким образом, трудоёмкость алгоритма --- $O(N^2) = O(N^2) + O(N^2) + O(N^{3/2} \log N)$. %%% \subsection{Проверка бинарного отношения на транзитивность} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является транзитивным>> или <<Отношение не является транзитивным>>. \begin{enumerate} \item Вычислить матрицу $A = M \times M$; \item Если $A \leq M$, то ответ <<Отношение является транзитивным>>; \item Иначе ответ <<Отношение не является транзитивным>>. \end{enumerate} Перемножение матриц в худшем случае имеет трудоёмкость $O(N^3)$, а сравнение матриц имеет трудоёмкость $O(N^2)$. Таким образом, трудоёмкость алгоритма --- $O(N^3) = O(N^3) + O(N^2)$. %%% \subsection{Классификация отношения как квазипорядка} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является квазипорядком>> или <<Отношение не является квазипорядком>>. \begin{enumerate} \item Присвоить булевой переменной \texttt{refl} значение алгоритма 3.1; \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5; \item Если на шагах 1 и 2 получены положительные ответы, то ответ <<Отношение является квазипорядком>>; \item Иначе ответ <<Отношение не является квазипорядком>>. \end{enumerate} Трудоёмкость алгоритма --- $O(N^3)$. %%% \subsection{Классификация отношения как эквивалентности} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является эквивалентностью>> или <<Отношение не является эквивалентностью>>. \begin{enumerate} \item Присвоить булевой переменной \texttt{refl} значение алгоритма 3.1; \item Присвоить булевой переменной \texttt{symm} значение алгоритма 3.3; \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5; \item Если значение булевого выражения $\texttt{refl} \, \land \, \texttt{symm} \, \land \, \texttt{tran}$ --- истина, то ответ <<Отношение является эквивалентностью>>; \item Иначе ответ <<Отношение не является эквивалентностью>>. \end{enumerate} Трудоёмкость алгоритма --- $O(N^3)$. %%% \subsection{Классификация отношения как частичного порядка} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является частичным порядком>> или <<Отношение не является частичным порядком>>. \begin{enumerate} \item Присвоить булевой переменной \texttt{antisymm} значение алгоритма 3.4; \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5; \item Если значение булевого выражения $\texttt{antisymm} \, \land \, \texttt{tran}$ --- истина, то ответ <<Отношение является частичным порядком>>; \item Иначе ответ <<Отношение не является частичным порядком>>. \end{enumerate} Трудоёмкость алгоритма --- $O(N^3)$. %%% \subsection{Классификация отношения как строгого порядка} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} <<Отношение является строгим порядком>> или <<Отношение не является строгим порядком>>. \begin{enumerate} \item Присвоить булевой переменной \texttt{antirefl} значение алгоритма 3.2; \item Присвоить булевой переменной \texttt{antisymm} значение алгоритма 3.4; \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5; \item Если значение булевого выражения $\texttt{antirefl} \, \land \, \texttt{antisymm} \, \land \, \texttt{tran}$ --- истина, то ответ <<Отношение является строгим порядком>>; \item Иначе ответ <<Отношение не является строгим порядком>>. \end{enumerate} Трудоёмкость алгоритма --- $O(N^3)$. \section{Алгоритмы построения основных замыканий бинарных отношений} %%% \subsection{Алгоритм построения рефлексивного замыкания} \textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ рефлексивного замыкания. \begin{enumerate} \item Пусть $M' = M$ \item Установим $(\forall i = \overline{1, N}) ~ m'_{ii} = 1$ \end{enumerate} Трудоёмкость алгоритма --- $O(N)$. %%% \subsection{Алгоритм построения симметричного замыкания} \textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ симметричного замыкания. \begin{enumerate} \item $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ m'_{ij} = \begin{cases} 1, &m_{ij} = 1 \lor m_{ji} = 1\\ 0, &m_{ij} = 0 \land m_{ji} = 0 \end{cases}$ \end{enumerate} Трудоёмкость алгоритма --- $O(N^2)$. %%% \subsection{Алгоритм построения транзитивного замыкания} \textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ транзитивного замыкания. \begin{enumerate} \item $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ (\forall k = \overline{1, N}) ~ m'_{ij} = \begin{cases} 1, &m_{ik} = 1 \land m_{kj} = 1\\ 0, &\text{в иных случаях} \end{cases}$; \item Шаг 1 необходимо повторить $N$ раз (по пункту 3 Леммы 2). \end{enumerate} Трудоёмкость алгоритма --- $O(N^4)$. %%% \subsection{Алгоритм построения эквивалентного замыкания} \textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности $N \times N$. \textit{Выход.} Матрица $M'(M(\rho))$ эквивалентного замыкания. \begin{enumerate} \item Вычислим матрицу $M_1$ применив к матрице $M$ алгоритм 4.1; \item Вычислим матрицу $M_2$ применив к матрице $M_1$ алгоритм 4.2; \item Вычислим матрицу $M'$ применив к матрице $M_2$ алгоритм 4.3; \end{enumerate} Трудоёмкость алгоритма --- $O(N^4)$. \section{Программная реализация} \inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab1.py} \section{Результаты тестирования} Ниже представлены результаты запуска программы на некоторых бинарных отношениях. \begin{figure}[H] \centering \includegraphics[width=0.7\textwidth]{mat3.png} \caption{Ввод матрицы размерности $3 \times 3$} \end{figure} \begin{figure}[H] \centering \includegraphics[width=0.7\textwidth]{mat4.png} \caption{Ввод матрицы размерности $4 \times 4$} \end{figure} \begin{figure}[H] \centering \includegraphics[width=0.9\textwidth]{mat4_id.png} \caption{Ввод единичной матрицы размерности $4 \times 4$} \end{figure} \conclusion В ходе выполнения данной лабораторной работы были изучены основные свойства бинарных отношений, а также операций замыкания бинарных отношений. Были разработаны алгоритмы классификации бинарных отношений, а также были произведена оценка сложности вычисления данных алгоритмов. Также были разработаны алгоритмы построения замыканий бинарных отношений на основе алгоритмов их классификации. Программная реализация на языке Python с библиотекой numpy успешно прошла тестирование. \end{document}