Лекция дискрет 09
.pdfЛекция № 9 06 ноября 2015 г.
Глава 2. Алгебраические структуры
§ 2.2. Примеры алгебр
Алгебра [ M; Ω ] |
Модель [ M; Θ ] |
Алгебра – множество М с заданной на нём совокупностью операций Ω = { φ1, φ2, … , φm, … }, т.е. структура
A = [ M; φ1, φ2, … , φm, … ]
М– основное множество (носитель) алгебры А
Ω= { φ1, φ2, … , φm, … } – сигнатура алгебры А
Тип алгебры А – вектор арностей её операций
Алгебра типа (2) - [аддитивная / мультипликативная] |
|
полугруппа / группа |
|
Полугруппа – алгебра с одной ассоциативной операцией |
|
+ коммутативность |
элемент |
Абелева (коммутативная) полугруппа |
|
+ нейтральный элемент |
+ нейтральный |
Моноид |
|
+ обратный элемент |
|
Группа |
|
Примеры групп и полугрупп из § 2.1:
[ R \ { 0 }; ] – мультипликативная коммутативная группа
[ N- { 0 } N+; + ] – аддитивная коммутативная группа
[ {Mn}; ] – мультипликативная некоммутативная группа
({Mn} – множество любых квадратных матриц n-ого порядка;- матричное умножение)
[ {Mn}; ] – мультипликативный некоммутативный моноид
(единица – матрица с единичной диагональю; {Mn} – множество невырожденных квадратных матриц n-ого порядка;- матричное умножение)
[ B (M); ] – аддитивный коммутативный моноид (ноль –
пустое множество )
[ B (M); ] – мультипликативный коммутативный
моноид (единица – множество М, выполняющее роль универсума)
y
c |
|
b |
|
|
α |
|
x |
Абелева группа обобщённых |
|
|
|
|||
a |
|
|
|
пифагоровых троек [ P; ] |
|
|
|
|
Модель скрещивания КРС-
моноид [ { a, b, c, d }; ]
2) Алгебры преобразований
Преобразование множества М – всюду определённое функциональное соответствие f: M Μ (§ 1.2)
Преобразование конечного множества M = { m1, m2, … , mn } - постановка в соответствие каждому элементу mi M элемента mj M того же множества (не требуя при этом сюръективность и инъективность), например:
M = { 1, 2, 3 } |
|
1 |
2 |
3 |
|
|
1 |
2 |
3 |
|||
α = |
|
|
|
|
β = |
|
|
|
||||
|
|
|
|
1 |
2 |
2 |
|
3 |
3 |
2 |
||
|
|
|
|
|
|
|
||||||
Композиция |
|
преобразований – последовательное |
|
|
||||||||
выполнение двух преобразований: |
|
|
|
|
|
|||||||
αΔβ = |
1 |
2 |
3 |
|
βΔα = |
1 |
2 |
3 |
|
|
|
|
|
3 |
3 |
3 |
|
|
|
2 |
2 |
2 |
|
|
|
По построению: операция – ассоциативная. Общее количество преобразований множества M = { 1, 2, 3 } – 33 = 27
Множество всех преобразований T(M) = { α1, α2, … , α27 } в силу своей исчерпывающей полноты замкнуто относительно операции Δ, значит, алгебра [ T(M); ] - полугруппа
Видели на простейшем примере: возможно αΔβ βΔα, значит, в общем случае алгебра [ T(M); ] – некоммутативная
Опять же, в силу своей исчерпывающей полноты множества всех преобразований T(M) = { α1, α2, … , α27 }, в нём имеется, в том числе, тождественное преобразование
Очевидно: αi |
1 |
2 |
3 |
= |
1 |
2 |
3 |
αi = αi |
моноид |
||
1 |
2 |
3 |
1 |
2 |
3 |
||||||
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
Нет инъективности нет гарантии обратного преобразования Итак, некоммутативный моноид преобразований конечного множества M = { 1, 2, 3 }
В T(M) построим подмножество T (M), замкнутое относительно
операции |
: |
|
|
|
|
|
|
|
|
|
|
|
|
||
α = |
1 |
2 |
3 |
|
|
|
1 |
2 |
3 |
|
|
2 |
1 |
2 |
3 |
|
|
|
|
|
β = |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
2 |
2 |
|
|
3 |
3 |
2 |
|
γ = β = |
2 |
2 |
3 |
||
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
||||||
δ = αΔβ = |
1 |
2 |
3 |
|
|
|
1 |
2 |
3 |
|
|
|
|||
|
|
|
|
|
ζ = βΔα = |
|
|
|
|||||||
3 |
3 |
3 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
2 |
2 |
2 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Результат применения операции
|
|
Правый операнд |
|
||||
|
|
|
|
|
|
|
|
операнд |
|
α |
β |
γ |
δ |
ζ |
|
|
|
|
|
|
|
||
α |
α |
δ |
ζ |
δ |
ζ |
||
|
|
|
|
|
|
||
β |
ζ |
γ |
β |
δ |
ζ |
||
Левый |
γ |
ζ |
β |
γ |
δ |
ζ |
|
|
|
|
|
|
|
||
δ |
ζ |
ζ |
δ |
δ |
ζ |
||
|
|
|
|
|
|
||
ζ |
ζ |
ζ |
ζ |
δ |
ζ |
||
|
|||||||
|
|
|
|
|
|
|
– в таблице Кэли:
Построена некоммутативная полугруппа преобразований множества М = { 1, 2, 3 } с
операцией и основным множеством Т (М) = { α, β, γ, δ, ζ }
|
|
Правый операнд |
|
|||||
|
|
|
|
|
|
|
|
|
операнд |
|
α |
β |
γ |
δ |
ζ |
ε |
|
|
|
|
|
|
|
|
||
α |
α |
δ |
ζ |
δ |
ζ |
α |
||
|
||||||||
|
|
|
|
|
|
|
|
|
|
β |
ζ |
γ |
β |
δ |
ζ |
β |
|
Левый |
|
|
|
|
|
|
|
|
γ |
ζ |
β |
γ |
δ |
ζ |
γ |
||
|
|
|
|
|
|
|
||
δ |
ζ |
ζ |
δ |
δ |
ζ |
δ |
||
|
||||||||
|
|
|
|
|
|
|
|
|
|
ζ |
ζ |
ζ |
ζ |
δ |
ζ |
ζ |
|
|
|
|
|
|
|
|
|
|
|
ε |
α |
β |
γ |
δ |
ζ |
ε |
|
|
|
|
|
|
|
|
|
Дополним Т (М) тождественным преобразованием
1 2 3
ε =
1 2 3
и включим в таблицу Кэли строку и столбец, получим моноид – полугруппу преобразований множества с нейтральным элементом
В связи с отсутствием инъективности обратное преобразование в общем случае не определено, поэтому требование из определения группы не выполнено