4 files changed, 240 insertions, 0 deletions
diff --git a/sem5/universal-algebra/lectures/lecture1.tex b/sem5/universal-algebra/lectures/lecture1.tex
new file mode 100644
index 0000000..98db9dc
--- /dev/null
+++ b/sem5/universal-algebra/lectures/lecture1.tex
@@ -0,0 +1,50 @@
+% Лекция 1 (03.09.21)
+\section{Алгебра отношений}
+Обозначение множеств:
+\begin{itemize}
+  \item $A = \{ a : P(A) \}$
+  \item $[0, 1] = \{ x : x \in R \land 0 \leq x \leq 1 \}$
+  \item $A = \{ 0, 1, \dots, 10 \}$
+\end{itemize}
+
+Основные действия над множествами:
+\begin{itemize}
+  \item Сравнение множеств: $A = B$ означает, что $|A|=|B| \land \forall x \in A \iff x \in B$
+  \item Объединение: $A \cup B$ --- множество, состоящее из элементов $A$ или $B$. $A \cup B = \{ x : x \in A \lor x \in B \}$
+  \item Разность множеств: $A - B = \{ x : x \in A \land x \not\in B \}$
+\end{itemize}
+
+\begin{definition}
+  $\{ x, y \}$ называется неупорядоченной парой элементов $x$, $y$.
+\end{definition}
+
+\begin{definition}
+  Множество $(a, b) = \{ a, \{a, b\} \}$ называют упорядоченной парой.
+\end{definition}
+
+$A_1 \cdot \ldots \cdot A_n = \{ (a_1, a_2, \dots, a_n) : \dots \}$
+
+\dots
+
+\begin{definition}
+  Всюду определённое и однозначеное бинарное отношение $\phi \subset A \times B$ обозначается $\phi: A \to B$ и
+  называется отображением $A$ в $B$, или \textit{функцией} на множестве $A$ со значениями в множестве $B$.
+\end{definition}
+
+Для отображения $\phi: A \to B$:
+\begin{itemize}
+  \item Область определения $D_p = A$ 
+  \item Область значений $E_p = B$
+\end{itemize}
+
+\begin{definition}
+  Отображение $\phi: A \to B$ называется:
+  \begin{itemize}
+    \item \textit{Преобразованием} множества $A$, если $A = B$;
+    \item \textit{Отображением} множества $A$ на множество $B$, если $E_\phi = B$;
+    \item \textit{Взаимно однозначным отображением} множества $A$ в множество $B$, если оно является взаимно однозначным бинарным отношением;
+    \item \textit{Взаимно однозначным отображением} $A$ на $B$ если оно взаимно однозначно и $E_\phi = B$;
+    \item \textit{Перестановкой} множества $A$, если оно является взаимно однозначным отображением множества $A$ на себя.
+  \end{itemize}
+\end{definition}
+
diff --git a/sem5/universal-algebra/lectures/lecture3.tex b/sem5/universal-algebra/lectures/lecture3.tex
new file mode 100644
index 0000000..4707dd5
--- /dev/null
+++ b/sem5/universal-algebra/lectures/lecture3.tex
@@ -0,0 +1,92 @@
+% Лекция 3 (17.09.21)
+\begin{example}
+  На $Z$ рассматривается бинарное отношение $(x, y) \in \varepsilon \iff |x| = |y|$. 
+  Очевидно, что $\varepsilon$ рефлексивно, симметрично и транзитивно. 
+  $\varepsilon$ является эквивалентным на $Z$ с классами $\varepsilon(x) \{ x, -x \}$  
+\end{example}
+
+\begin{example}
+  На $Z$ для фиксированного $m \in N$ $(x, y) \in \varepsilon \iff$ $x - y$ делится
+  на $m$ то есть $x - y = k \cdot m$ для некоторого $k \in Z$.
+  \begin{itemize}
+    \item 
+      \textit{Рефлексивность}. $(x, x) \in \varepsilon$ равносильна 
+      $x - x = m \cdot k$, ($\exists k \in R$) --- выполняется 
+      $x - x = m \cdot O$ для $O \in Z$
+    \item 
+      \textit{Симметричность}. 
+      $(x, y) \in \varepsilon \implies (y, x) \in \varepsilon$, 
+      то есть $x \cdot y = m \cdot k, \, \exists k \in Z \implies 
+      y \cdot x = m \cdot l, \, (\exists l \in Z)$ --- верно, 
+      то есть $l = -k \in Z$
+    \item
+      \textit{Транзитивность}. 
+      $(x, y) \in \varepsilon \land (y, z) \in \varepsilon \implies 
+      (x, z) \in epsilon$, то есть 
+      $x - y = m \cdot k, \, (\exists k \in Z) \lor 
+      y - z = m \cdot l, \, (\exists l \in Z) \implies 
+      x -z = m \cdot p, \, (\exists p \in Z)$.
+  \end{itemize}
+
+  $x - z = (x - y) + (y - z) = m \cdot k + m \cdot l = m \cdot (k + l)$ для $k + l \in Z$
+  
+  Получаем, что $\varepsilon$ --- отношение эквивалентности, которое 
+  обозначается $\text{mod}\, m$ и называется отношением сравнения по модулю $m$.
+
+  Классы отношения эквивалентности $\varepsilon$ : 
+  \begin{eqnarray}
+    \varepsilon(0) &= \{ 0, m, 2m, \dots, -m, -2m \} = m \cdot \Z \\
+    \varepsilon(1) &= \{ 1, m + 1, 2m + 1, \dots, -m + 1, -2m + 1 \} = m \cdot \Z + 1 \\
+    &\dots \\
+    \varepsilon(m - 1) &= \{ m - 1, 2m - 1, \dots \} = m \cdot \Z + (m - 1) \\
+    \varepsilon(m) &= m \cdot \Z + m = m \cdot (Z + 1) = m \cdot Z = m(0)
+  \end{eqnarray}
+
+  Фактор-множество $\Z/\text{mod}\, m = \{ \varepsilon(0), \dots, \varepsilon(m - 1) \}$
+\end{example}
+
+\begin{example}
+  На множестве $V$ всех векторов на плоскости рассмотрим бинарное отношение $\varepsilon$:
+  $(a, b) \in \varepsilon \iff (a \upuparrows b \land |a| = |b|)$. 
+  $\varepsilon$ является отношением эквивалентности с классами эквивалентности 
+  $\varepsilon(a) = \{ x \in V : a \upuparrows x \land |a| = |x| \}$.
+  Фактор-множество: $V/\varepsilon = \{ \varepsilon(a) : a \in V \}$
+\end{example}
+
+\begin{definition}
+  Бинарное отношение $\varepsilon$ на множестве $A$ называется \textit{отношением
+  эквивалентности} (или просто \textit{эквивалентностью}), если оно рефлексивно,
+  симметрично и транзитивно.
+\end{definition}
+
+\begin{definition}
+  \textit{Ядром отображения} $\phi: A \to b$ называется бинарное отношение 
+  $ker \phi$ на множестве $A$, которое определяется по формуле 
+  \begin{equation*}
+    ker \phi \{ (a, b) \in A^2 : \phi(a) = \phi(b) \}
+  \end{equation*}
+\end{definition}
+
+\begin{definition}
+  \textit{Каноническим отображением} эквивалентности $\varepsilon$ называется
+  отображение $nat \varepsilon$ множества $A$ на фактор-множество $A/\varepsilon$,
+  которое каждому элементу $a \in A$ ставит в соответствие содержащий его класс
+  эквивалентности $[a]$. Легко видель, что $ker nat \varepsilon = \varepsilon$
+\end{definition}
+
+\begin{definition}
+  Подмножество $T \subset A$ называется полной системой представителей классов
+  эквивалентности $\varepsilon$ на множестве $A$, если:
+  \begin{enumerate}
+    \item $\varepsilon(T) = A$
+    \item из условия $t_1 \equiv t_2(\varepsilon)$ следует $t_1 = t_2$
+  \end{enumerate}
+\end{definition}
+
+Классы эквивалентности $[t] \in A/\varepsilon$ могут быть отождествленны со 
+своими представителями $t$ и фактор-множество $A/\varepsilon$ может быть 
+отождествленно с множеством $T$.
+
+...
+
+Извествен алгоритм построения СДНФ для любой формулы $\Phi (\neq 0)$
diff --git a/sem5/universal-algebra/lectures/lecture4.tex b/sem5/universal-algebra/lectures/lecture4.tex
new file mode 100644
index 0000000..eb76b95
--- /dev/null
+++ b/sem5/universal-algebra/lectures/lecture4.tex
@@ -0,0 +1,84 @@
+% Лекция 4 01.10.21
+\begin{definition}[Принцип двойственности]
+  Если утверждение $\Phi$ верно для всех упорядоченных множеств, то
+  двойственное ему утверждение также верно для всех упорядоченных множеств.
+\end{definition}
+
+\begin{example}
+  \begin{enumerate}
+    \item
+      Для утверждения ``если в упорядоченном множестве существует $\sup X$,
+      то он единственнен'' двойственным будет ``если в упорядоченном
+      множестве существует $\inf X$, то он единственен''.
+    \item
+      Для утверждения ``упорядоченное множество $(A, \leq)$ имеет
+      наибольший элемент'' двойственным будет ``упорядоченное множество
+      $(A, \leq)$ имеет наименьший элемент''.
+  \end{enumerate}
+\end{example}
+
+\subsection{Упорядочивание множества слов}
+
+\subsection{Подмножества и морфизмы упорядоченных множеств}
+\begin{lemma}[Цорна]
+  Если в упорядоченном множестве любая цепь имеет верхнюю
+  грань, то каждый элемент этого множества содержится в
+  некотором максимальном элементе.
+\end{lemma}
+
+\begin{lemma}[Аксиома выбора]
+  Для любого множества $A$ существует такая функция
+  $f : P(A) \to A$, что $f(X) \in X$ для любого $X \in P(A)$.
+\end{lemma}
+
+\begin{definition}
+  Упорядоченное множество удовлетворяет \textit{условию минимальности},
+  если каждое его непустое подмножество имеет минимальный элемент.
+\end{definition}
+
+\begin{lemma}[Обобщённый принцип индукции]
+  Если упорядоченное множество удовлетворяет \textit{условию минимальности}
+  и подмножество $B \subset A$ содержит все такие элементы $a \in A$, для
+  которых при всех $x < a$ выполняется $x \in B$, то $B = A$.
+\end{lemma}
+
+\begin{definition}
+  \textbf{Морфизмы} --- это отображения $\varphi : A \to B$, которые сохряняют
+  дополнительную алгебраическую структуру на множества $(A, B)$.
+
+  Если $a_1 \leq_A a_2 \implies \varphi(a_1) \leq_B \varphi(a_2) \quad (\forall a_1, a_2 \in A)$
+\end{definition}
+
+\begin{example}
+  $\varphi : (\N, \leq_\N) \to (\Z, \leq_\Z)$
+\end{example}
+
+\subsection{Отношение квазипорядка}
+
+\begin{definition}
+  Бинарное отношение $\omega$ на множестве $A$ называется \textit{отношением
+  квазипорядка} (или просто \textit{квазипорядком}), если оно рефлексивно
+  и транзитивно.
+
+  Отношение $\delta = \omega \cap \omega^{-1}$ называется \textit{ядром}
+  квазипорядка $\omega$.
+\end{definition}
+
+\begin{example}
+  \begin{enumerate}
+    \item
+      Любая эквивалентность $\equiv$ и любой порядок $\leq$ на множестве
+      $A$ являются квазипорядками с ядрами $\delta = \equiv$ и
+      $\delta = \Delta_A$ соответственно.
+    \item
+      Отношение делимости $|$ на множество целых чисел $\Z$ является
+      квазипорядком с ядром $\delta = \{ (n, \mp n) | n \in \Z\}$.
+    \item
+      Отношение логического следлвания на множестве $F_{AB}$ формул
+      логики высказываний является квазипорядком, ядром которого
+      является отношение логической равносильности формул.
+    \item
+      Отношение достижимости вершин в ориентированном графе является
+      квазипорядком, ...
+  \end{enumerate}
+\end{example}
+\ No newline at end of file
diff --git a/sem5/universal-algebra/universal-algebra.tex b/sem5/universal-algebra/universal-algebra.tex
new file mode 100644
index 0000000..12f87bc
--- /dev/null
+++ b/sem5/universal-algebra/universal-algebra.tex
@@ -0,0 +1,14 @@
+\documentclass{../Lecture}
+\usepackage{../preamble}
+
+\begin{document}
+
+\author{Андрей гущин}
+\title{Универсальная прикладная алгебра}
+\maketitle
+
+\include{lectures/lecture1.tex}
+\include{lectures/lecture3.tex}
+\include{lectures/lecture4.tex}
+
+\end{document}