Добавление заданий в пятой лабе

1 files changed, 165 insertions, 5 deletions

diff --git a/lab5/report/lab5.tex b/lab5/report/lab5.tex
index 40995f3..c98a0c7 100644
--- a/lab5/report/lab5.tex
+++ b/lab5/report/lab5.tex
@@ -222,8 +222,8 @@ $R$ мощности $M$ определяющих соотношений.
     Если $is\_inserted = False$, то переход к шагу 4, иначе $M = \langle A | R
     \rangle$ и возврат к шагу 2.
   \item
-    По полугруппе $\langle A | R \rangle$ вычисляем матрицу $\mathfrak{D}$
-    отношения Грина с использованием алгоритма 3.4.
+    По таблице Кэли полугруппы $\langle A | R \rangle$ вычисляем матрицу
+    $\mathfrak{D}$ отношения Грина с использованием алгоритма 3.4.
 \end{enumerate}
 
 Трудоёмкость алгоритма "--- $O(N^M)$
@@ -249,15 +249,175 @@ $R$ мощности $M$ определяющих соотношений.
 
 \subsection*{Задание 1}
 
-решение
+Найдите подполугруппу $\langle x \rangle$, правый $[x)$, левый $(x]$ и
+двусторонний $(x)$ идеалы полугруппы $S$, порожденные элементом $x$, и
+определите порядок элемента $x$ для каждого элемента полугруппы, на которой
+бинарная операция задана следующей таблицей Кэли:
+
+\begin{table}[H]
+  \small
+  \centering
+  \begin{tabular}{|c|cccc|}
+    \hline
+    $\cdot$ & a & b & c & d \\ \hline
+    a       & a & b & c & d \\
+    b       & b & c & d & a \\
+    c       & c & d & a & b \\
+    d       & d & a & b & c \\ \hline
+  \end{tabular}
+\end{table}
+
+$[a) = \{a, b, c, d\}, \; (a] = \{a, b, c, d\}, \; (a) = \{a, b, c, d\}.$
+
+$[b) = \{b, c, d, a\}, \; (b] = \{b, c, d, a\}, \; (b) = \{b, c, d, a\}.$
+
+$[c) = \{c, d, a, b\}, \; (c] = \{c, d, a, b\}, \; (c) = \{c, d, a, b\}.$
+
+$[d) = \{d, a, b, c\}, \; (d] = \{d, a, b, c\}, \; (d) = \{d, a, b, c\}.$
 
 \subsection*{Задание 2}
 
-решение
+Для полугрупп из Задания 1 найдите отношения Грина и <<egg-box>>-картины.
+\begin{equation*}
+  \mathfrak{R} =
+    \begin{pmatrix}
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1
+    \end{pmatrix}
+\end{equation*}
+\begin{equation*}
+  \mathfrak{L} =
+    \begin{pmatrix}
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1
+    \end{pmatrix}
+\end{equation*}
+
+Тогда отношение Грина будет представлено матрицей $\mathfrak{D} = \mathfrak{R}
+\vee \mathfrak{L}$:
+\begin{equation*}
+  \mathfrak{D} =
+    \begin{pmatrix}
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1
+    \end{pmatrix}
+\end{equation*}
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.3\textwidth]{myegg2.png}
+  \caption{<<egg"=box>>"=диаграмма}
+\end{figure}
+
+По копредставлению полугруппу S найдите отношения Грина и <<egg-box>>-картины: 
+$S = \langle x, y : xy = yx, x^2 = y, y^3 = x \rangle$.
+
+Слова длины 1: $x, y$ "--- эти слова не эквивалентны относительно конгруэнции
+$\varepsilon$.
+
+Слова длины 2: $x^2 = y, xy, yx = xy, y^2$. Среди них только $xy$ и $y^2$ не
+эквивалентны относительно конгруэнции $\varepsilon$.
+
+Слова длины 3: $x^2 y = y^2, xy^2, y^3 = x$. Среди них только $x y^2$ не
+эквивалентно относительно конгруэнции $\varepsilon$.
+
+Слова длины 4: $x^2 y^2 = y^3 = x, x y^3 = x^2 = y$ "--- все эти слова
+эквивалентны относительно конгруэнции $\varepsilon$ ранее выделенным словам.
+
+Таким образом, $S = \{ x, y, xy, y^2, x y^2 \}$.
 
 \subsection*{Задание 3}
 
-решение
+Найдите полугруппу S по ее копредставлению $\langle x, y : xy = yx, x^3 = x, y^2
+= x \rangle$. Выделим полную систему представителей классов конгруэнции
+$\varepsilon$, которая определяется соотношениями данного копредставления. Для
+этого последовательно рассмотрим слова фиксированной длины и выделим те, которые
+не будут эквивалентны между собой относительно конгруэнции $\varepsilon$.
+
+Сначала рассматриваем слова длины $1$: $x, y$ - эти слова не эквивалентны между
+собой относительно конгруэнции $\varepsilon$.
+
+Затем рассматриваем слова длины $2$, которые получаются из слов длины $1$ путем
+последовательного умножения их справа на буквы $x$ и $y$. Из этих слов только
+слова $x^2$, $xy$ не эквивалентны относительно конгруэнции $\varepsilon$ другим
+ранее выделенным словам.
+
+Теперь рассматриваем слова длины $3$, которые получаются из выделенных слов
+длины $2$ путем последовательного умножения их справа на буквы $x$ и $y$. Из
+этих слов только слово $x^2y$ не эквивалентно относительно конгруэнции
+$\varepsilon$ другим ранее выделенным словам.
+
+Наконец рассматриваем слова длины $4$, которые получаются из выделенного слова
+длины $3$ путем последовательного умножения его справа на буквы $x$ и $y$. Все
+эти слова эквивалентны относительно конгруэнции $\varepsilon$ ранее выделенным
+словам.
+
+Значит, $S = \{x, y, x^2, xy, x^2y \}$ "--- полная система представителей
+классов конгруэнции $\varepsilon$. Операция умножения $\cdot$ таких слов
+определяется с точностью до конгруэнции $\varepsilon$ по следующей таблице Кэли:
+
+\begin{table}[H]
+  \centering
+  \begin{tabular}{|c|c|c|c|c|c|}
+  \hline
+  $\cdot $ & $x$ & $y$  & $x^2$  & $xy$ & $x^2y$ \\ \hline
+  $x$      & $x^2$ & $xy$ & $x$  & $x^2y$ & $xy$ \\ \hline
+  $y$      & $xy$ & $x$ & $x^2y$ & $x^2$ & $x$ \\ \hline
+  $x^2$     & $x$ & $x^2y$ & $x^2$ & $xy$ & $x^2y$ \\ \hline
+  $xy$    & $x^2y$ & $x^2$ & $xy$ & $x$ & $x^2$ \\ \hline
+  $x^2y$   & $xy$ &  $x$  &  $x^2y$ & $x^2$ & $x$ \\ \hline
+  \end{tabular}
+\end{table}
+
+Получим таким образом $\mathfrak{R}$ и $\mathfrak{L}$:
+\begin{equation*}
+  \mathfrak{R} =
+    \begin{pmatrix}
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1
+    \end{pmatrix}
+\end{equation*}
+\begin{equation*}
+  \mathfrak{L} =
+    \begin{pmatrix}
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1
+    \end{pmatrix}
+\end{equation*}
+
+Отношение Грина определяется матрицей $\mathfrak{D} = \mathfrak{R}
+\oplus \mathfrak{L}$:
+\begin{equation*}
+  \mathfrak{D} =
+    \begin{pmatrix}
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1 \\
+      1 & 1 & 1 & 1 & 1
+    \end{pmatrix}
+\end{equation*}
+
+Исходя из полученной матрицы отношений Грина, можно построить
+изображение <<egg"box>>"=диаграммы:
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.4\textwidth]{myegg2.png}
+  \caption{<<egg"=box>>"=диаграмма}
+\end{figure}
 
 
 \conclusion