24. Алгебраическая структура (универсальная алгебра, алгебра). Основа (носитель, основное, несущее множество) алгебры. Тип и сигнатура алгебры.
Определение
4.10.
Алгебраической
структурой
(универсальной
алгеброй
или просто алгеброй)
называется упорядоченная пара
= < A, Σ >, где A – непустое множество
и Σ – множество алгебраических операций
на A.
Замечание 4.1. Для обозначения алгебры везде, где это необходимо, используется рукописная прописная буква латинского алфавита, а для обозначения ее носителя – соответствующая печатная прописная буква.
Определение
4.11. Алгебры
=
< A,
,
…,
> и
=
< В,
,
…,
> называются однотипными,
если их типы совпадают, то есть ранг
операции
совпадает с рангом соответствующей ей
операции
для i = 1,…, m.
Определение
4.12. Пусть
алгебры
= < A,
,
…,
> и
=
< В,
,
…,
>
– однотипные алгебры. Алгебра
называется подалгеброй
алгебры
, если В ⊆
A и
любая
операция
(i = 1, …,
m) алгебры
и
соответствующая
ей
операция
алгебры
удовлетворяют
условию:
(∀
,
…,
∈
B)
(
,
…,
)=
(
,
…,
), где
или (
)–
ранг операций
и
.
Определение 4.13. Пусть = < A, , …, > – алгебра и В ⊆ A. Подмножество В множества A называется замкнутым в алгебре , если В замкнуто относительно каждой операции (i = 1, …, m) алгебры , то есть выполняется условие: (∀ ,…, ∈ B) ( ,…, )∈B, где – ранг операции .(13)
Если – нульарная операция, которая выделяет элемент a ∈ A, то условие (13) принимает вид a ∈ В. Из определений 4.12 и 4.13 непосредственно вытекает следующая теорема.
Теорема 4.3. Пусть = < A, , …, > – алгебра и В – непустое подмножество множества A, замкнутое в алгебре . Тогда алгебра = < В, , …, > является подалгеброй алгебры .
25. Алгебры с одной бинарной операцией: группоид. Таблица Кэли.
Пусть A – непустое множество.
Определение 4.14. Алгебра = < A, ∗ >, где ∗ – бинарная алгебраическая операция, называется группоидом. Таким образом, группоид определяется непустым множеством A и правилом, по которому можно найти значение операции ∗ для любых двух элементов из A.
Определение
4.15. Пусть
на конечном множестве A ={
,
…,
}
определена бинарная операция ∗.
Таблица,
состоящая
из
n строк
и
n столбцов,
в
которой
на
пересечении
i-й
строки
и
j-го
столбца
располагается
значение
операции
∗
,
называется
таблицей
Кэли:
Замечание 4.3. 1. Если операция ∗ коммутативна, то таблица Кэли симметрична относительно главной диагонали.
Полугруппа — это алгебра с одной ассоциативной бинарной операцией: а * (b * с) = (а * b) * с
Гомоморфизм,
который является инъекцией, называется
м
ономорфизмом
31. Нок, нод, Алгоритм Евклида
1) НОК
Пусть имеются целые числа a1, a2…an. НОК – наименьшее общее кратное этих чисел. Обозначается как [a1, a2 … an]
2) НОД
Пусть имеются целые числа a1, a2, … an. НОД (наибольший общий делитель) – наибольшее число, которое нацело делит каждое из этих чисел. Обозначается (a1, a2, … an).
3) Алгоритм Евклида
Для произвольного целого числа a и произвольного целого положительного числа b существуют такие числа t и r, что a = bt + r, где 0 <= r < b.
Причем такое представление единственное.
Тогда эти числа можно представить в следующей форме:
a = bt1 + r2, 0 < r2 < b;
b = r2t2 + r3, 0 < r3 < r2;
r2 = r3t3 + r4, 0 < r4 < r3 …
rn–1 = rntn + rn+1
Последний ненулевой остаток в этйо последовательности равенств и будет НОД. НОК = a*b/(a,b)