Самопознание

человеческий потенциал безграничен


  • Первый семинар

  • Четвертый семинар

  • Тема: Бинарные отношения. Алгебры. Группы. Читаем, комментируем, решаем ДЗ.

    Рассмотрим пример бинарного отношения, которое изображено на рисунке
    1. Исследуем свойства Р, И, С, А, Т для этого отношения.

    Рис. 1:
    Пример отношения
    \includegraphics[width=14cm]{rel_nontrans.eps}

    рефлексивность
    диагональ не включается полностью в это отношение, значит оно нерефлексивно;
    симметричность
    график отношения симметричен относительно диагонали, значит это
    симметричное отношение;
    транзитивность
    транзитивность будем проверять, учитывая тот факт, что для
    транзитивных отношений выполняется
    $ \rho \circ \rho \subseteq \rho$.

    Рассмотрим, какие значения принимает отношения при различных $ x$. Для этого
    воспользуемся специальным обозначением сечения:
    $ \rho(X) = \{ y \vert (x, y) \in\rho, x \in X \} = \bigcup\limits_{x \in X} \rho(x)$. На рисунке
    1 показаны значения, которые отношение принимает при различных $ x$:

    $\displaystyle \rho\left(\frac{1}{2}\right) = [0, 1], \rho(0) = \rho(1) = \frac{1}{2},\rho\left(\frac{1}{4}\right) = \left[\frac{1}{4}, \frac{3}{4}\right]$

    Отметим, что $ \rho(x)$ для любого $ x$ содержит
    $ \frac{1}{2}$, а значит:

    $\displaystyle \begin{array}{l}\rho \circ \rho (0) = \rho \circ \rho (1) =\rho......eft(\left[\frac{1}{4},\frac{3}{4}\right]\right) = [0, 1],\\\dots\end{array}$

    Получается, что
    $ \rho \circ \rho = [0, 1]^2$, а значит
    $ \rho \circ \rho \nsubseteq\rho$, т.е. это отношение не транзитивно.

    Таким образом, это отношение имеет следующие свойства:

    Р И С А Т
    - - + - -


    Отношения порядка

    Отношения, обладающие свойствами рефлексивности, антисимметричности и
    транзитивности называют отношениями порядка.

    Исследуем свойства следующего отношения:
    $ \rho \subseteq \mathbb{N}^2, x \rho y\Leftrightarrow x \vert y$ ($ x$ делится нацело на $ y$).

    рефлексивность
    $ (\forall x)(x = x \Rightarrow x \vert x)$, рефлексивно;
    симметричность
    Симметричность в общем случае не выполняется (например, для чисел 3
    и 1).
    $ x \vert y \And y \vert x \Rightarrow x = y$, значит антисимметрично;
    транзитивность
    $\displaystyle \left.\begin{array}{r}x \vert y \Leftrightarrow x = k y, k \in \......htarrow y = m z, m \in \mathbb{N}\end{array}\right\} \Rightarrow x = (k m) z,$

    т.е. выпоняется $ x \vert z$, значит отношение транзитивно.

    Обобщим свойства отношения в таблице:

    Р И С А Т
    + - - + +

    В упорядоченных множествах два элемента называются сравнимыми, если для них можно
    определить, какой больше, а какой -- меньше. В случае обычного числового порядка
    ($ \leqslant$) все элементы оказываются сравнимыми, а в рассмотренном выше отношении
    порядка, например, элементы 2 и 3 не могут быть сравнены. Отношения порядка, при которых
    все элементы множества сравнимы, назваются линейными.

    Для отношений порядка на конечных множествах удобно использовать диаграмме Хассе: элемнты
    множества представляются точками на плоскости, два элемента соединяются линией в том
    случае, если элементы сравнимы и между ними не может быть помещён ещё один элемент. При
    этом, большие элементы рисуют выше, а меньшие -- ниже.

    На рисунке 2 показана диаграмма Хассе для рассмотренного выше отношения
    порядка на различных множествах целых чисел. На диаграмме можно легко увидеть несравнимые
    элементы и линейный порядок (все элементы выстраиваются в линию).

    Рис. 2:
    Диаграммы Хассе для отношения порядка делимости
    \includegraphics[width=12cm]{hass_div.eps}

    Рассмотрим другое отношение порядка: отношения включения теории множеств $ \subseteq$ на
    множестве $ 2^A$ всех подмножеств множества $ A$. Внимательно рассмотрев его свойства, можно
    увидеть, что это отношение также рефлексивно, антисимметрично и транзитивно.

    На рисунке 3 показан пример такого отношения на множестве, образованном
    тремя множествами $ A$, $ B$ и $ C$ и их объединениями. Диаграмма Хассе в данном случае имеет вид кубика,
    а отношение порядка не является линейным -- например, $ A$ и $ B \cup C$ не могут быть
    сравнимы, так как нельзя сказать, чтобы одно из этих множеств включалось в другое.

    Рис. 3:
    Диаграмма Хассе для отношения порядка включения
    \includegraphics[width=12cm]{hass_set.eps}

    Задания для самоподготовки. Рассмотрим множество слов русского алфавита.
    Каждое слово состоит из упорядоченного набора букв
    $ x = x_1 x_2 \dots x_n $. Для букв
    будем использовать стандартный порядок их следования в алфавите. Рассмотрим следующие
    два отношения:

    • $ x \rho y \Leftrightarrow x_1 < y_1 \vee (x_1 = y_1 \And x_2 <y_2) \vee (x_1 = y_1 \And x_2 = y_2 \And x_3 < y_3) \vee \dots$;
    • $ x \rho y \Leftrightarrow x_1 \leqslant y_1 \And x_2 \leqslant y_2 \And x_3\leqslant y_3 \And \dots$.

    Докажите, что они являются отношениями порядка. Какое из них является
    линейным? Изобразите диаграммы Хесса для следующего набора слов: ``бутылка'',
    ``банан'', ``бисквит'', ``бивень'', ``банджо''.


    Отношения эквивалентности

    Отношения, обладающие свойствами рефлексивности, симметричности и
    транзитивности называют отношениями эквивалентности.

    Примерами отношения эквивалентности является простое числовое равенство или отношение
    подобия для треугольников.

    Исследуем свойства отношения:
    $ A = M_{n \times n}(\mathbb{R}), \rho \subseteq A^2, P \rhoQ \Leftrightarrow \det P = \det Q$, т.е. на множестве квадратных матриц из действительных
    чисел отношение выполняется, если определители двух матриц равны.

    Свойства этого отношения вытекают из свойств числового равенства:

    рефлексивность
    $ (\forall X)(\det X = \det X)$, рефлексивно;
    симметричность
    $ (\forall X, Y)(\det X = \det Y)$, симметрично;
    транзитивность
    $ (\forall X, Y, Z)(\det X = \det Y \And \det Y = \det Z) \Rightarrow\det X = \det Z$, транзитивно.

    Отличительным свойством отношений эквивалентности является существование классов
    эквивалентности
    . Классом эквивалентности элемента $ x$ по отношению
    $ \rho \subseteq A^2$ называют
    множество всех элементов $ A$, эквивалентных по данному отношению $ x$:

    $\displaystyle [x]_\rho = \{ y \vert y \in A, x \rho y\}$

    Например, в рассмотренном выше отношении (ограничимся сейчас $ n = 2$) можно выделить
    множество всех матриц, определитель которых равен 1:

    \begin{displaymath}\left(\begin{array}{cc}1 & 0 \\0 & 1 \\\end{array}\r......n{array}{cc}0 & -1 \\1 & 1 \\\end{array}\right),\dots\end{displaymath}

    Таким образом, для каждого действительного числа $ x$ можно построить класс эквивалентности
    матриц, отпределитель которых равен $ x$:

    \begin{displaymath}\left[\left(\begin{array}{cc}x & 0 \\0 & 1 \\\end{ar......c}2x & 0 \\0 & 0.5 \\\end{array}\right), \dots\right\}\end{displaymath}

    Можно доказать, что классы эквивалентности образуют разбиение начального множества
    $ A$. Разбиением называется такой набор множеств $ A_1$, $ A_2$, $ \dots$, который
    удовлетворяет условиям:
    $ A_1 \cup A_2 \cup \dots \cup A_n \cup \dots = A$ и
    $ A_1 \capA_2 \cap \dots \cap A_n \cap \dots = \varnothing$, т.е. множества разбиения не
    пересекаются и при объединении дают начальное множество.

    Множество $ A$ можно представить в виде объединения классов эквивалентности некоторых его
    элементов:
    $ A = [x]_\rho \cup [y]_\rho \cup \dots$. В нашем примере множество всех матриц
    можно разбить на показанные выше классы эквивалентности, эти классы не будет пересекаться,
    так как в каждом из них определители матриц отличаются.

    Множество всех классов эквивалентности, задающих разбиение множества $ A$, называют
    фактор-множеством, а процесс его построения факторизацией. Обозначается
    фактор-множетство следующим образом:

    \begin{displaymath}\begin{array}{c}A /_\rho = \left\{ \left[\left(\begin{arra......t)\right]_\rho \right\vertx \in \mathbb{R}\right\}\end{array}\end{displaymath}

    Рассмотрим ещё одно отношение: на множестве целых чисел при заданном
    $ k \in \mathbb{N}$,

    $ \rho \subseteq \mathbb{Z}^2, x \rho y \Leftrightarrow x \equiv_k y$, что означает -- $ x$ и
    $ y$ равны по модулю $ k$ или имеют один остаток при делении на $ k$. Выясним свойства
    отношения:

    рефлексивность
    $ (\forall x)(x = x) \Rightarrow x \equiv_k x$, рефлексивно;
    симметричность
    $ (\forall x, y)(x \equiv_k y \Rightarrow y \equiv_k k)$, симметрично;
    транзитивность
    $\displaystyle \left.\begin{array}{r}x \equiv_k y \Leftrightarrow x = n k + r,\......+ r,\, z = l k + r\end{array}\right\} \Rightarrow x = n k + r,\, z = l k + r,$

    транзитивно

    Обобщим свойства отношения в таблице. Видно, что это отношение эквивалентности.

    Р И С А Т
    + - + - +

    Построим существующие классы эквивалентности:

    \begin{displaymath}\begin{array}{l}\left[ 0 \right]_{\equiv_k} = \{0, \pm k, ...... k + k - 1, \pm 2k + k - 1, \pm 3k + k - 1, \dots\}\end{array}\end{displaymath}

    Всего $ k$ классов эквивалентности, которые задают разбиение всего множества целых
    чисел. Для $ k = 2$ имеем следующие два класса эквивалентости:

    \begin{displaymath}\begin{array}{l}\left[ 0 \right]_{\equiv_2} = \{0, \pm 2, ......right]_{\equiv_2} = \{\pm 1, \pm 3, \pm 5, \dots\},\end{array}\end{displaymath}

    а фактор-множество равно:

    $\displaystyle \mathbb{Z} /_{\equiv_2} = \{\left[ 0 \right]_{\equiv_2}, \left[ 1 \right]_{\equiv_2}\}.$

    Задания для самоподготовки. Доказать, что отношение
    $ \rho \subseteq A^2$ является
    эквивалентностью. Построить фактор-множество $ A /_\rho$. Чем однозначно определяется каждый
    класс эквивалентности?

    • $ A = V_3 $ (множество векторов в пространстве),
      $ x \rho y \Leftrightarrow (xy, \vec{n}) = 0$, где
      $ \vec{n} \neq 0$ -- фиксированный вектор;
    • $ A = \mathbb{N}^2, (a, b) \rho (c, d) \Leftrightarrow ad = bc$.


    Мощности множеств

    Пока пропущено, возможно, будут рассмотрены позже.


    Алгебраические структуры

    Алгебраическая структура (алгебра) -- множество с операциями на нём. Обозначается
    следующим образом:
    $ \mathcal{A} (A, \Omega)$, где $ \Omega$ -- набор операций, называемый
    сигнатурой.

    Операция -- произвольное отображение
    $ \omega: A^n \rightarrow A$. Выделяют унарные
    операции ($ n = 1$), бинарные операции ($ n = 2$), тернарные операции ($ n = 3$). Также
    иногда представляют особый интерес некоторые элементы множества $ A$, при этом они могу
    добавляться в сигнатуру, превращаясь в так называемые нулярные операции.

    Чаще всего встречаются бинарные операции, они могу обладать следующими свойствами:

    коммутативность
    $ (\forall x, y \in A)(x * y = y * x)$;
    ассоциативность
    $ (\forall x, y, z \in A)(x * (y * z) = (x * y) * z)$;
    идемпотентность
    $ (\forall x \in A)(x * x = x)$.

    Примеры алгебр:

    • $ \mathcal{N} (\mathbb{N}, \{+, \cdot\})$ -- сложение и умножение на множестве натуральных
      чисел;
    • $ \mathcal{B}_A (2^A, \{\cup, \cap, \setminus, \neg, \varnothing, A\})$ -- операции над множеством
      всех подмножеств множества $ A$, два элемента из $ 2^A$:
      $ \varnothing$ и $ A$ были
      специально выделены;
    • $ \mathcal{V} (V_3, \{+, \cdot \alpha (\alpha \in \mathbb{R})\})$ -- множество
      векторов в пространстве с операциями сложения и умножения на число -- эта агебра
      интересна тем, что её сигнатура бесконечна.

    Примеры не-алгебр:

    • $ \mathcal{R} (\mathbb{R}, \{ +, \cdot, / \})$ -- не алгебра, так как деление
      определено не для всех пар чисел из
      $ \mathbb{R}$;
    • $ \mathcal{M} (M \rightarrow M, \{ \circ, {}^{-1}\})$ -- не алгебра, так как не для
      каждого отображения
      $ M \rightarrow M$ существует обратное отображение.


    Группы

    Любая алгебра с одной бинарной операцией
    $ \mathcal{A} (A, *)$
    называется группоидом. Примеры группоида:
    $ (\mathbb{N}, +)$ -- сложение натуральных
    чисел или
    $ (V_3, \times)$ -- множество векторов в пространстве с операцией векторного
    произведения.

    Группоид, операция которого обладает ассоциативностью, называется
    полугруппой. Примером полугруппы является алгебра бинарных отношений на множестве
    $ M$ с операцией композиции
    $ (2^{M \times M}, \circ)$ или та же алгебра
    $ (\mathbb{N}, +)$. А вот алгебра векторов с векторным произведением полугруппой уже не является, так как
    векторное произведение неассоциативно.

    Если
    $ \mathcal{A} (A, *)$ -- полугруппа и существует такое
    $ \varepsilon \in A$, что

    $ (\forall x \in A)(x * \varepsilon = \varepsilon * x = x)$, то такая полугруппа называется
    моноидом, а элемент
    $ \varepsilon$ -- нейтральным элементом. Обычно, нейтральный
    элемент записывается в сигнатуре. Можно доказать, что если полугруппа имеет нейтральный
    элемент, то он является единственным. Примером моноида является множество натуральных чисел с
    операцией умножения
    $ (\mathbb{N}, \cdot, 1)$. А полугруппа натуральных чисел со сложением
    должна быть дополнена нулём, чтобы стать моноидом:
    $ (\mathbb{N}_0, +, 0)$. Также моноид
    образуют теоретико-множественные операции объединения и пересечения:
    $ (2^A, \cup,\varnothing)$ и
    $ (2^A, \cap, A)$.

    Пусть
    $ \mathcal{M} (M, *, \varepsilon)$ -- произвольный моноид, тогда $ x' \in M$ называется
    обратным элемементом к $ x \in M$, если
    $ x * x' = x' * x = \varepsilon$. Моноид называется
    группой, если каждый элемент в нём имеет обратный. Можно доказать, что в группе для
    любого элемента существует единственный обратный элемент, или $ (x')' = x$.

    Примером группы являтся множество целых чисел с операцией сложения:
    $ (\mathbb{Z}, +, 0)$,
    при этом обратным элементом к любому числу является его отрицание. Можно увидеть, откуда
    взялось название полугруппы -- если мы возьмём две полугруппы натуральных и
    отрицательных чисел
    $ (\mathbb{N}, +)$ и
    $ (\mathbb{N}^-, +)$ и объединим их с добавлением
    нейтрального элемента 0, то получим полную группу.

    Также группой является множество всех невырожденных матриц
    $ (\mathcal{M}^+, \cdot, E, {}^-1)$ с
    операцией умножения. В этом случае обратная матрица является обратным элементом к любой
    матрице (она существует, так как матрицы невырождены).

    В группе можно решать уравнения вида $ a * x = b$ или $ x * a = b$, решением которых будет
    соответственно
    $ x = a' * b$ и
    $ x = b * a'$.

    Группа, операция которой коммутативна, называется абелева группа.

    Задания для самоподготовки. Задана алгебра $ (X, *)$ с одной бинарной
    операцией. Проверить свойства этой операции и указать, к какому типу эта алгебра
    относится.

    • $ X = \mathbb{N}, x * y = x^y$;
    • $ X = \mathbb{N}, x * y =$   НОК$ (x, y)$;
    • $ X = \mathbb{R}, x * y = x$;
    • $ X$ -- множество диагональных матриц порядка $ n$, $ x * y$ -- произведение
      матриц;
    • $ X = 2^A, x * y = A \setminus B$.

    Группа вычетов Особый интерес представляют группа следующего вида:
    $ \mathbb{Z}_K^+(\{0, 1, 2, \dots, k - 1\}, \oplus_k, 0)$, где $ \oplus_k$ -- операция сложения по модулю
    $ k$ (остаток от деления $ x + y$ на $ k$). Такая группа называется аддитивной группой
    вычетов
    . Аналогичная группа с операцией умножения по модулю $ k$
    $ \mathbb{Z}_K^*(\{0, 1, 2, \dots, k - 1\}, \odot_k, 1)$ называется мультипликативной группой вычетов.

    В мультипликативной группе вычетов элемент образует замыкание относительно операции
    умножения. Например, в
    $ \mathbb{Z}_5^* (\{0, 1, 2, 3, 4\}, \odot_5, 1)$:

    \begin{displaymath}\begin{array}{l}3^1 = 3\\3^2 = 3 \odot_5 3 = 4\\3^3 ......4 = 2 \odot_5 3 = 1\\3^5 = 1 \odot_5 3 = 3 = 3^1\end{array}\end{displaymath}

    Значит, $ 3^{2006}$ в этой группе вычисляется легко:
    $ 3^{2006} = 3^{2005} \odot_5 3 = 3^1 \odot_5 3 = 4$.


    Группа перестановок

    Рассмотрим конечное множество
    $ A = \{1, 2, \dots, n\}$, сотоящее из $ n$
    элементов. Перестановкой называется биекция
    $ A \rightarrow A$. Перестановка записывается в
    виде:

    \begin{displaymath}\left(\begin{array}{cccc}1 & 2 & \dots & n\\i_1 & i_2 & \dots & i_n\end{array}\right),\end{displaymath}

    где
    $ i_1, \dots i_n \in A$.

    На множестве перестановок можно определить операцию композиции:

    \begin{displaymath}\sigma = \left(\begin{array}{cccc}1 & 2 & \dots & n\\i...... 2 & \dots & n\\k_1 & k_2 & \dots & k_n\end{array}\right),\end{displaymath}

    где
    $ k_s = \tau(\sigma(s)) = \tau(i_s) = j_{i_s}$.

    Для каждой перестановки можно получить обратную перестановку:

    \begin{displaymath}\sigma = \left(\begin{array}{cccc}1 & 2 & \dots & n\\i......1 & i_2 & \dots & i_n\\1 & 2 & \dots & n\end{array}\right)\end{displaymath}

    Множество всех перестановок степени $ n$ образуют группу по операции композиции, при этом
    нейтральным элементом является тождественная перестановка:

    \begin{displaymath}\left(A \rightarrow A, \circ, \varepsilon\right),\varepsi......c}1 & 2 & \dots & n\\1 & 2 & \dots & n\end{array}\right)\end{displaymath}

    Такая группа называется группой перестановок.

    Рассмотрим уравнение над этой группой:

    \begin{displaymath}\begin{array}{c}\left(\begin{array}{cccc}1 & 2 & 3 & 4......& 3 & 4\\2 & 1 & 4 & 3\end{array} \right)\par\end{array}\end{displaymath}

    Первый и второй семинары:
    В виде PDF
    Исходный вариант






























































































































































  • Первый семинар

  • Четвертый семинар






  • Последние новости


    Дружба

    Все жизненные проблемы приносят с собой золотые самородки мудрости, обнаружить которые помогает истинная дружба. Вы замечали, что есть люди, которые дают вам силы, поднимают настроение и вызывают желание находиться рядом? И те, кто стремится вытянуть из вас энергию, надоедает вам и делает все так, что хочется сбежать. Нас подде...
    Читать далее »

    Советы, способствующие успеху

    ВЫЯВЛЕНИЕ ЦЕННОСТЕЙ Правильный выбор – Это результат жизни в соответствии со своими высшими ценностями, то есть путь к лучшей жизни. ЖИЗНЕННАЯ ЦЕЛЬ Лучшие люди выбирают цель, которая затрагивает лучшие струны в других. МИССИЯ Жизнь нельзя прожить дважды. Теперь или никогда, поэто...
    Читать далее »

    Утренние вопросы

    Если бы мне осталось жить всего месяц, что бы я делал из того, что делаю сегодня? Что я сделаю сегодня, чтобы почувствовать себя счастливым? Какие прекрасные воспоминания останутся у меня в памяти сегодня? Какие убеждения сделали мою жизнь такой, какая она есть? Во что нужно поверить, чтобы прожить удивительную жизнь? ...
    Читать далее »

    И еще несколько вопросов

    Знать мысли Бога – все равно что знать, как преуспеть в жизни. Глубоко поразмыслив над вопросами этой книги и записав свои ответы в дневник, вы развили в себе привычку анализировать. Поздравляю! Это важнейший навык успешной жизни. Способность к самоанализу и постановке правильных вопросов наряду с пониманием того, как использовать интуицию и природную мудрость, изменит нап...
    Читать далее »

    Путешествия

    Поставьте перед собой цель жить полноценно. Самый печальный итог – оглянуться назад и вопрошать, что можно было бы иметь, если бы… Дорожите своими заветными мечтами, воплощая их в жизнь. Ах, путешествия… Большинство из нас любят путешествовать и страстно стремятся к этому. Мы тоскуем по приключениям в реальной жизни. Хотим посетить удаленные места, узнать культуры, не...
    Читать далее »

    Счастье

    Там, где жизнь бьет ключом, где оживленно и весело, там и ищите свое счастье. Моя шестилетняя внучка Элла однажды зашла в мой офис и уселась в кресло. Она давно слышала, что я занимаюсь коучингом, поэтому я спросил ее: «Не хочешь побыть сегодня тренером и немного поучить других?» Малышка посмотрела на меня, выпрямилась в кресле, и я понял: она готова. Элла спросила: – О ч...
    Читать далее »

    Взаимоотношения

    Любовь Магия Бога выражается через любовь; наивысшая форма любви – бескорыстная помощь другим. Вы когда нибудь смотрели в глаза новорожденного и ощущали восторг, который ребенок приносит в этот мир? Большинство из нас чувствуют исходящую от детей любовь. Мы являемся в мир с любовью и открытым сердцем. С самого детства мы отдаем свою любовь этому миру. Из л...
    Читать далее »

    Ваш комментарий:


    Вы должны войти в систему, чтобы оставить комментарий.