\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) M(\rho)^T$ (значения элементов вне главной диагонали
        матрицы $M(\rho) M(\rho)^T$ равны нулю);
    \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{Основные системы замыкания на множестве бинарных отношений}

\textit{Замыканием} отношения $R$ относительно свойства $P$ называется такое
множество $R^*$, что:
\begin{enumerate}
    \item $R \subset R^*$.
    \item $R^*$ обладает свойством $P$.
    \item 
        $R^*$ является подмножеством любого другого отношения, содержащего $R$ и
        обладающего свойством $P$.
\end{enumerate}

Множество Z подмножеств множества A называется \textit{системой замыканий}, если
оно замкнуто относительно пересечений, т.е. выполняется
\begin{equation*}
    (\forall B \subset Z) ~ \bigcap B \in Z
\end{equation*}

\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)$ бинарного отношения $\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)$ бинарного отношения $\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)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является симметричным>> или <<Отношение не
является симметричным>>.

\begin{enumerate}
    \item Вычислить транспонированную матрицу $M^T$;
    \item Если $M = M^T$, то ответ <<Отношение является симметричным>>;
    \item Иначе ответ <<Отношение не является симметричным>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\subsection{Проверка бинарного отношения на антисимметричность}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является антисимметричным>> или <<Отношение не
является антисимметричным>>.

\begin{enumerate}
    \item Вычислить транспонированную матрицу $M^T$;
    \item Вычислить матрицу $A = M \times M^T$;
    \item 
        Если $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) : i
        \ne j$ выполняется $(A_{ij} = 0)$, то ответ <<Отношение
        является антисимметричным>>;
    \item Иначе ответ <<Отношение не является антисимметричным>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\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^2)$.

%%%
\subsection{Классификация отношения как квазипорядка}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является квазипорядком>> или <<Отношение не является
квазипорядком>>.

\begin{enumerate}
    \item Выяснить является ли отношение рефлексивным;
    \item Выяснить является ли отношение транзитивным;
    \item 
        Если на шагах 1 и 2 получены положительные ответы, то ответ <<Отношение
        является квазипорядком>>;
    \item Иначе ответ <<Отношение не является квазипорядком>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\subsection{Классификация отношения как эквивалентности}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является эквивалентностью>> или <<Отношение не
является эквивалентностью>>.

\begin{enumerate}
    \item Выяснить является ли отношение рефлексивным;
    \item Выяснить является ли отношение симметричным;
    \item Выяснить является ли отношение транзитивным;
    \item 
        Если на шагах 1, 2 и 3 получены положительные ответы, то ответ
        <<Отношение является эквивалентностью>>;
    \item Иначе ответ <<Отношение не является эквивалентностью>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\subsection{Классификация отношения как частичного порядка}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является частичным порядком>> или <<Отношение не
является частичным порядком>>.

\begin{enumerate}
    \item Выяснить является ли отношение антисимметричным;
    \item Выяснить является ли отношение транзитивным;
    \item 
        Если на шагах 1 и 2 получены положительные ответы, то ответ
        <<Отношение является частичным порядком>>;
    \item Иначе ответ <<Отношение не является частичным порядком>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\subsection{Классификация отношения как строгого порядка}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является строгим порядком>> или <<Отношение не
является строгим порядком>>.

\begin{enumerate}
    \item Выяснить является ли отношение антирефлексивным;
    \item Выяснить является ли отношение антисимметричным;
    \item Выяснить является ли отношение транзитивным;
    \item 
        Если на шагах 1, 2 и 3 получены положительные ответы, то ответ
        <<Отношение является строгим порядком>>;
    \item Иначе ответ <<Отношение не является строгим порядком>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

\section{Алгоритмы построения основных замыканий бинарных отношений}

%%%
\subsection{Алгоритм построения рефлексивного замыкания}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} Матрица $M'(M(\rho))$ рефлексивного замыкания.

\begin{enumerate}
    \item 
        $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ 
        M'_{ij} = \begin{cases}
            1, &i = j \\
            M_{ij}, &i \ne j
        \end{cases}$
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\subsection{Алгоритм построения симметричного замыкания}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} Матрица $M'(M(\rho))$ симметричного замыкания.

\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)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} Матрица $M'(M(\rho))$ транзитивного замыкания.

\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$ раз.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^4)$.

%%%
\subsection{Алгоритм построения эквивалентного замыкания}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} Матрица $M'(M(\rho))$ эквивалентного замыкания.

\begin{enumerate}
    \item 
        Вычислим матрицу $M_1 = \texttt{refl}(M)$, где \texttt{refl} ---
        алгоритм построения рефлексивного замыкания;
    \item
        Вычислим матрицу $M_2 = \texttt{symm}(M)$, где \texttt{symm} ---
        алгоритм построения симметричного замыкания;
    \item
        Вычислим матрицу $M' = \texttt{trans}(M)$, где \texttt{trans} ---
        алгоритм построения транзитивного замыкания;
\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{}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{mat4.png}
    \caption{}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.9\textwidth]{mat4_id.png}
    \caption{}
\end{figure}

\conclusion

В ходе выполнения данной лабораторной работы были изучены основные свойства
бинарных отношений, а также операций замыкания бинарных отношений. Были
разработаны алгоритмы классификации бинарных отношений, а также были произведена
оценка сложности вычисления данных алгоритмов. Также были разработаны алгоритмы
построения замыканий бинарных отношений на основе алгоритмов их классификации.
Программная реализация на языке Python с библиотекой numpy успешно прошла
тестирование.

\end{document}
