diff options
Diffstat (limited to 'sem5/universal-algebra/lectures')
| -rw-r--r-- | sem5/universal-algebra/lectures/lecture1.tex | 50 | ||||
| -rw-r--r-- | sem5/universal-algebra/lectures/lecture3.tex | 92 | ||||
| -rw-r--r-- | sem5/universal-algebra/lectures/lecture4.tex | 84 |
3 files changed, 226 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 |