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

Алгебраические методы описания моделей находят самое широкое применение при формализации различных предметных областей.
Грубо говоря, при построении модели предметной области все начинается с введения подходящих обозначений для операций и отношений с последующим исследованием их свойств.
1

Владение алгебраической терминологией, таким образом, входит в арсенал средств, необходимых для абстрактного моделирования, предшествующего практическому программированию задач конкретной предметной области.
2

Операции и алгебры
Всюду определенная (тотальная) функция
f: Мn → М называется n-арной (n-местной) операцией на М.
Если операция f— бинарная (то есть f: М х М -> М), то будем писать afb вместо f(а, b) или a о b, где о — знак операции.
3

множество М вместе с набором операций
∑ = {f1,. . . ,fm}, fi :Mni→ M, где ni — арность операции fi , называется алгебраической структурой, универсальной алгеброй или просто алгеброй.
множество М называется основным (несущим) множеством, или основой (носителем);
вектор арностей (ni,...,nm) называется типом;
множество операций ∑ называется сигнатурой;
запись: <М; ∑>
4

5

Многоосновная алгебра имеет несколько носителей, а каждая операция сигнатуры действует из прямого произведения некоторых носителей в некоторый носитель.
Другими словами
6

Замыкания и подалгебры
Подмножество X ⊂ M называется замкнутым относительно операции f, если ∀ x1, …, xn ∈ X, если X замкнуто относительно всех X f∈ X, то
называется подалгеброй
Пример
Алгебра
- поле действительных чисел. Тип – (2,2). Все конечные подмножества, кроме {0}, не замкнуты относительно обеих операция. Поле рациональных чисел
образует подалгебру.
7

8

Непустое пересечение подалгебр образует подалгебру.
ТЕОРЕМА
9

Замыканием множества X включенного в М относительно сигнатуры ∑ (обозначается [X]∑ ) называется множество всех элементов (включая сами элементы X), которые можно получить из X, применяя операции из ∑. Если сигнатура подразумевается, ее можно не указывать.
ТЕОРЕМА
Непустое пересечение подалгебр образует, подалгебру.
10

В алгебре целых чисел
замыканием числа 2 являются четные числа.
I. X ⊂ Y=[X] ⊂ [Y]; .
2. Х ⊂ [X];
3. [[X]] = [X];
4. [Х] ∪ [Y] ⊂ [X ∪ Y].
Свойства замыкания:
Пример
11

Пусть заданы сигнатура ∑ = (ϕ1, …, ϕm) типа N = (n1, …, nm) и множество переменных V = {x1, x2, …}. Определим множество термов Т в сигнатуре ∑ следующим образом:
V ⊂ T;
t1, …, tni ∈ T & ϕi ∈ ∑ ⇒ ϕ( t1, …, tni) ∈ T.
Алгебра 〈T; ∑〉 называется свободной алгеброй термов, или ∑-алгеброй.
Носителем ∑-алгебры является множество термов, то есть формальных выражений, построенных с помощью знаков операция сигнатуры ∑. Таким образом, с ∑-алгеброй не связано никакое конкретное множество, являющееся носителем. Поэтому ∑-алгебры используются в программировании для определения абстрактных типов данных.
12

Ассоциативность: (a○b)○c = a○(b○c);
Коммутативность: a○b = b○a;
Дистрибутивность слева: a◊(b○c) = (a◊b)○(a◊c);
Дистрибутивность справа: (a○b) ◊c = (a◊c)○(b◊c);
Поглощение: (a○b) ◊a = a;
Идемпотентность: a○a = a.
Свойства операций
Некоторые часто встречающиеся свойства операция имеют специальные названия. Пусть задана алгебра 〈М;∑〉 и a, b, c ∈ M; ○,◊ ∈ ∑; ○,◊: М × М → М.
Тогда:
13

Понятие изоморфизма, введенное в этом разделе, является одним из ключевых.
Алгебры с различными типами имеют различное строение.
А = 〈N; +〉, B = 〈N10;+10〉, где N10 = {0,1,2,3,4,5,6,7,8,9}, а +10 сложение по модулю 10.
Тогда f: = а mod 10 – гомоморфизм из А в В.
Морфизмы
Гомоморфизм
Пример
Пусть А = 〈A; ϕ1, …, ϕm〉 и В = 〈В; ψ1, …, ψm〉 - две алгебры одинакового типа. Если существует функция f: A→B, такая что ∀ i ∈ 1..m f(ϕi (a1, …, an)) = ψI (f(a1), …, f(an)), то говорят,
что f – гомоморфизм из А в В.
14

Гомоморфизмы, обладающие дополнительными свойствами, имеют специальные названия:
Гомоморфизм, который является инъекцией, называется мономорфизмом.
Гомоморфизм, который является сюръекцией, называется эпиморфизмом (или эпиоморфизмом).
Гомоморфизм, который является биекцией, называется изоморфизмом.
Если А=В,
то гомоморфизм называется эндоморфизмом,
а изоморфизм называется автоморфизмом.
15

Изоморфизм
Пусть А = 〈A; ϕ1, …, ϕm〉 и В = 〈В; ψ1, …, ψm〉 - две алгебры одинакового типа., и f: А→В – изоморфизм.
f
Если f: А→В – изоморфизм, то алгебры А и В называют изоморфными и обозначают так А ~ В.
Если f: А→В – изоморфизм, то f-1: В→А тоже изоморфизм.
ТЕОРЕМА
16

ТЕОРЕМА
Отношение изоморфизма на множестве однотипных алгебр является эквивалентностью.
17

x2
f
ln
Понятие изоморфизма является одним из центральных понятий, обеспечивающих применимость алгебраических методов в различных областях.
Алгебраические структуры принято рассматривать с точностью до изоморфизма, то есть рассматривать классы эквивалентности по отношению изоморфизма.
Пример
18

Алгебры с одной операцией
Естественно начать изучение алгебраических структур с наиболее простых.
Самой простой структурой является алгебра с одной унарной операцией, но этот случай настолько тривиален, что про него нечего сказать.
Следующим по порядку является случай алгебры с одной бинарной операцией
○: M × M → M
19

Полугруппы
Полугруппа — это алгебра с одной ассоциативной бинарной операцией:
a○(b○c) = (a○b)○c.
Множество слов А+ в алфавите А образует полугруппу относительно операции конкатенации.
Всякое множество функций, замкнутое относительно суперпозиции, является полугруппой.
Пример
20

Если в полугруппе существует система образующих, состоящая из одного элемента, то такая полугруппа называется циклической.
(N; +) является циклической полугруппой, поскольку {1} является системой образующих.
Пример
21

Моноиды
Моноид — это полугруппа с единицей:
∃ e ∀ a a○e = e○a = a.
Множество слов A* в алфавите А вместе с пустым словом Λ образуют моноид.
Пусть Т – множество термов над множеством переменных V и сигнатурой Σ. Подстановкой, или заменой переменных, называется множество пар
σ = {ti//vi}i∈I,
где ti – термы, а vi – переменные, причем vi ∉ ti. Результатом применения подстановки σ к терму t (обозначается tσ) называется терм, который получается заменой всех вхождений переменных vi на соответствующие термы ti.
Пример
22

Пусть ∃ e1 , e2 ∀ a a ○ e1 = e1 ○ a = a & a ○ e2 = e2 ○ a = а. Тогда e1 ○ e2 = e1 & e1 ○ e2 = e2 ⇒ e1 = e2.
ТЕОРЕМА
Единица единственна.
Доказательство
23

Группы
Группа — это моноид, в котором
Элемент a -1 называется обратным.
∀ a ∃ a-1 a ○ a-1 = a-1○ a = e
24

Множество невырожденных квадратных матриц порядка n образует группу относительно операции умножения матриц. Единицей группы является единичная матрица. Обратным элементом является обратная матрица.
Множество подстановок на множестве М, то есть множество взаимно однозначных функций f: M→ M является группой относительно операции суперпозиции. Единицей группы является тождественная функция, а обратным элементом – обратная функция.
25

Пусть a ○ a-1 = a-1○ a = e & a ○ b = b ○ a = e.
Тогда a-1 = a-1○ e = a-1○ (a ○ b) = (a-1○ a) ○ b = e ○ b = b.
ТЕОРЕМА
Обратный элемент единственен.
Доказательство
ТЕОРЕМА
В группе выполняются следующие соотношения:
(a ○ b) -1= b-1 ○ a-1;
a ○ b = a ○ с ⇒ b = с;
b ○ a = с ○ а ⇒ b = с;
(a-1)-1 = а.
26

(a ○ b)○(b-1○ a-1) = a ○(b ○ b-1) ○ a-1 = a ○ e ○ a-1 = a ○ a-1 = e.
а ○ b = a ○ с ⇒ a-1○(a ○ b) = a-1○(a ○ c) ⇒ (a-1○ a) ○ b = (a-1○ a) ○ c ⇒ e ○b = e ○ c ⇒ b = c.
b ○ a = с ○ а ⇒ (b ○ a) ○ a-1 = (с ○ а) ○ a-1 ⇒ b ○ (a ○ a-1) = с ○ (а ○ a-1) ⇒ b ○ e = c ○ e ⇒ b = с.
(a-1) ○ a = a-1 ○ a =e.
Доказательство
27

a ○ x = b ⇒ a-1 ○ (a ○ x) = a-1 ○ b ⇒ (a-1 ○ a) ○ x = a-1 ○ b ⇒ e ○ x = a-1 ○ b ⇒ x = a-1 ○ b
Коммутативная группа, то есть группа, в которой
a ○ b =b ○ a,
называется абелевой. В абелевых группах приняты следующие обозначения: групповая операция обозначается + или ⊕, обратный элемент к а обозначается -а, единица группы обозначается 0 и называется нулем.
ТЕОРЕМА
В группе можно однозначно решить уравнение a ○ x = b , (решение: x = a-1 ○ b).
Доказательство
28

〈Z; +〉 - множество целых чисел образует абелеву группу относительно сложения. Нулем группы является число 0. Обратным элементом является число с противоположным знаком: x-1= -x.
〈Q+; ⋅〉 - множество положительных рациональных чисел образует абелеву группу относительно умножения. Нулем группы является число 1. Обратным элементом является обратное число: (m/n)-1: = n/m.
〈2M; Δ〉 - булеан образует абелеву группу относительно симметрической разности. Нулем группы является пустое множество ∅. Обратным элементом является дополнение: X-1: = M\X.
29

Алгебры с двумя операциями
В этом разделе рассматриваются алгебры с двумя бинарными операциями:
которые условно называются «сложением» и «умножением», соответственно.
⊕, ⊗: M × M → M,
30

Кольца
Кольцо – это множество М с двумя бинарными операциями ⊕ и ⊗, в котором:
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) сложение ассоциативно;
∃ 0 ∈M ∀ a a ⊕ 0 = 0 ⊕ a = a существует нуль;
∀ a ∃ - a a ⊕ - a = 0 существует обратный элемент;
A ⊕ b = b ⊕ a сложение коммутативно, то есть кольцо – абелева группа по сложению;
a⊗( b ⊗ c) = (a ⊗ b) ⊗ c умножение ассоциативно, то есть кольцо – полугруппа по умножению;
a⊗(b ⊕ c) = (a ⊗ b) ⊕ ( a ⊗ c) умножение дистрибутивно
(a ⊕ b) ⊗ c = (a ⊗ с) ⊕ ( b ⊗ c) слева и справа.
Кольцо называется коммутативным, если
a ⊗ b = b ⊗ a умножение коммутативно.
Коммутативное кольцо называется кольцом с единицей, если
∃ 1 ∈ M a ⊗ 1 = 1 ⊗a = a существует единица, то есть кольцо с единицей – моноид по умножению.
31

0 ⊗ a = (0 ⊕ 0) ⊗ a = (0 ⊗ a) ⊕ (0 ⊗ a) ⇒ -(0 ⊗ a) ⊕ (0 ⊗ a) = -(0 ⊗ a) ⊕ ((0 ⊗ a) ⊕ (0 ⊗ a)) = (-(0 ⊗ a) ⊕ (0 ⊗ a)) ⊕ (0 ⊗ a) ⇒ 0 = 0 ⊕ (0 ⊗ a) = 0 ⊗ a.
(a ⊗ (-b)) ⊕ (a ⊗ b) = a ⊗ (-b ⊕ b) = a ⊗ 0 = 0 ⇒ a ⊗ (-b) = -( a ⊗ b), (a ⊗ b) ⊕((-a) ⊗ b) = (a ⊕ (-a)) ⊗ b = 0 ⊗ b = 0 ⇒ (-a) ⊗ b = -( a ⊗ b).
(-a) ⊗ (-b) = -(a ⊗ ( -b)) = -(-( a ⊗ b)) = a ⊗ b.
ТЕОРЕМА
В кольце выполняются следующие соотношения:
0 ⊗ a = a ⊗ 0 = 0;
a ⊗ (-b) = (-a) ⊗ b = -( a ⊗ b);
(-a) ⊗ (-b) = a ⊗ b.
Доказательство
32

Если в кольце ∃x ≠ 0 ∃y ≠ 0 x ⊗ y = 0, то x называется левым, а у – правым делителем нуля.
Пример
Пример
33

⇒: От противного. Пусть x ⊗ y = 0. Тогда x ≠ 0 & x ⊗ y = 0 & x ⊗ 0 = 0 ⇒ y = 0, y ≠ 0 & x ⊗ y = 0 & 0 ⊗ y = 0 ⇒ x = 0.
⇐: 0 = (a ⊗ b) ⊕ (-(a ⊗ b)) = (a ⊗ b) ⊕ (-(a ⊗ с)) = (a ⊗ b) ⊕ (a ⊗ (-с)) = a ⊗ (b ⊕ (-с)), a ⊗ (b ⊕ (-с)) = 0 & a ≠ 0 ⇒ b ⊕ (-с) = 0 ⇒ b = c.
ТЕОРЕМА
Доказательство
34

Коммутативное кольцо с единицей, не имеющее делителей нуля, называется областью целостности.
Пример
35

Поле – это множество М с двумя бинарными операциями ⊕ и ⊗, такими что:
(a ⊕b) ⊕ c = a ⊕ (b ⊕ c) сложение ассоциативно;
∃ 0 ∈M a ⊕ 0 = 0 ⊕ a = a существует нуль;
∀ a ∃ - a a ⊕ - a = 0 существует обратный элемент по сложению;
а ⊕ b = b ⊕ a сложение коммутативно, то есть поле – абелева группа по сложению;
a⊗( b ⊗ c) = (a ⊗ b) ⊗ c умножение ассоциативно;
∃ 1 ∈ M a ⊗ 1 = 1 ⊗a = a существует единица;
∀ a ≠ 0 ∃ a-1 a-1 ⊗ a = 1 существует обратный элемент по умножению;
a ⊗ b = b ⊗ a умножение коммутативно, то есть поле – абелева группа по умножению;
a⊗(b ⊕ c) = (a ⊗ b) ⊕ ( a ⊗ c) умножение дистрибутивно относительно сложения
Поля
36

〈R; +, ⋅〉 - поле вещественных чисел.
〈Q; +, ⋅〉 - поле рациональных чисел.
Пусть E2 : = {0, 1}. Определим операции ⊕, ⋅: E2 × E2→ E2 следующим образом: 0⋅0 = 0, 0⋅1 = 0, 1⋅0 = 0, 1⋅1 = 1, 0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1=0. Тогда ε2: = 〈 E2; ⊕, ⋅〉 является полем и называется двоичной арифметикой.
Пример
37

(a ⊗ (-1)) ⊕ a = (a ⊗ (-1)) ⊕ (a ⊗ 1) = a ⊗ (-1 ⊕ 1) = a ⊗ 0 = 0.
(а ⊕ b) ⊕ ((-а) ⊕ (-b)) = (а ⊕ b) ⊕ ((-b) ⊕ (-а)) = а ⊕ (b ⊕ (-b)) ⊕ (-а) = а ⊕ 0 ⊕ (-а) = а ⊕ (-а) = 0.
а-1 ⊗ a = 1.
а ⊗ b = 0 & а ≠ 0 ⇒ b =1 ⊗ b = (а-1 ⊗ a) ⊗ b = а-1 ⊗ (a ⊗ b) = а-1 ⊗ 0 = 0, а ⊗ b = 0 & b ≠ 0 ⇒ a = 1 ⊗ a = (b-1 ⊗ b) ⊗ a = b-1 ⊗ (b ⊗ a) = b-1 ⊗ (а ⊗ b) = b-1 ⊗ 0 = 0.
ТЕОРЕМА
В поле выполняются следующие соотношения:
(-а) = а ⊗ (-1);
–(а ⊕ b) = (-а) ⊕ (-b);
а ≠ 0 ⇒ (a-1)-1 = a;
a ⊗ b = 0 ⇒ a = 0 ∨ b = 0.
Доказательство
38

а ⊗ x ⊕ b = 0 ⇒ а ⊗ x ⊕ b ⊕ (-b) = 0 ⊕ (-b)а ⊗ x ⊕ (b ⊕ (-b)) = -b ⇒ а ⊗ x + 0 = -b ⇒ а ⊗ x = -b ⇒ а-1 ⊗ (а ⊗ x) = а-1 ⊗ (-b) ⇒ (а-1 ⊗ а) ⊗ x = -( а-1⊗ b) ⇒ 1 ⊗ x = -( а-1 ⊗ b) ⇒ x = -( а-1 ⊗ b).
ТЕОРЕМА
Если а ≠ 0, то в поле единственным образом разрешимо уравнение
а ⊗ x ⊕ b = 0, (х = -( а-1) ⊗ b).
Доказательство
391

Решетки иногда называют «структурами», но слово «структура» перегружено, и мы не будем использовать его в этом значении.
Решетки сами по себе часто встречаются в разных программистских задачах, но еще важнее то, что понятие решетки непосредственно подводит нас к понятию булевой алгебры, которое имеет множество приложений в программировании и вычислительной технике.
Решётки
40

⇒: Пусть a ∩ b = b. Тогда a ∪ b = a ∪ (a ∩ b) = (a ∩ b) ∪ a = a.
⇐: Пусть a ∪ b = a. Тогда a ∩ b = (a ∩ b) ∩ b = (b ∪ a) ∩ b = b.
ТЕОРЕМА
Если нижняя (верхняя) грань существует, то она единственна
ТЕОРЕМА
a ∩ b = b ⇔ a ∪ b = a.
Доказательство
Если в решетке ∃0 ∈M ∀ a 0 ∩ a = 0, то 0 называется нулем (или нижней гранью) решетки. Если в решетке ∃1 ∈M ∀ a 1 ∪ a = 1, то 1 называется единицей (или верхней гранью) решетки. Решетка с верхней и нижней гранями называется ограниченной.
Пусть 0’ – еще один нуль решетки. Тогда 0 ∩ 0’ = 0’ и 0’ ∩ 0 = 0.
Следовательно 0 = 0’.
Доказательство
41

В ограниченной решетке элемент а’ называется дополнением элемента а, если a ∩ а’ = 0 и a ∪ а’ = 1.
Если ∀ а ∈M ∃ а’ ∈M a ∩ а’ = 0 & a ∪ а’ = 1, то ограниченная решетка называется решеткой с дополнением. Вообще говоря, дополнение не обязано существовать и не обязано быть единственным.
ТЕОРЕМА
(о свойствах дополнения) В ограниченной дистрибутивной решетке с дополнением выполняется следующее:
дополнение а’ единственно;
дополнение инволютивно: а” = а;
грани дополняют друг друга: 1’ = 0, 0’ = 1;
выполняются законы де Моргана: (a ∪ b)’ = а’ ∩ b’, (a ∩ b)’ = а’ ∪ b’.
42

Частичный порядок в решётке
ТЕОРЕМА
Доказательство
43

44

ТЕОРЕМА
Если в частично упорядоченном множестве для любых двух элементов существуют нижняя и верхняя грани, то это множество образует решетку относительно inf u sup (то есть x ∩ y: inf(x, y), x ∪y: sup(x, y)).
ТЕОРЕМА
Если нижняя(верхняя) грань существует, то она единственна.
Доказательство
45

Булевы алгебры
Дистрибутивная ограниченная решетка, в которой для каждого элемента существует дополнение, называется булевой алгеброй.
Пример
46

a ∪ a = a, a ∩ a = a
по определению решетки;
2. a ∪ b = b ∪ a, a ∩ b = b ∩ a,
по определению решетки;
a ∪ (b ∪ c) = (a ∪ b) ∪ c, a ∩ (b ∩ c) = (a ∩ b) ∩ c
по определению решетки;
(a ∩ b) ∪ a = a, (a ∪ b) ∩ a =a
по определению решетки;
a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c), a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
по свойству дистрибутивности;
a ∪ 1 = 1, a ∩ 0 = 0
по свойству ограниченности;
a ∪ 0 = a, a ∩ 1 = a
по следствию из теоремы ограниченности;
a’’ = a
по теореме о свойствах дополнения;
(a ∩ b)’ = a’ ∪ b’, (a ∪ b)’ = a’ ∩ b’
по теореме о свойствах дополнения;
a ∪ a’ = 1, a ∩ a’ = 0
так как дополнение существует.
47