Материал: Дискретная математика теория и практика

Пример 4.2. 1. Сложение и умножение действительных чисел являются коммутативными и ассоциативными бинарными алгебраическими операциями. Умножение действительных чисел дистрибутивно относительно сложения, но сложение не дистрибутивно относительно умножения, так как условие

( a, b, c А) a + b c = (a + b) (a + c) не выполняется.

2.Операции объединения и пересечения подмножеств непустого множества А коммутативны, ассоциативны и дистрибутивны относительно друг друга на булеане Р(А).

3.Композиция функций есть ассоциативная бинарная алгебраическая операция. Композиция функций не коммутативна, так как условие

( f, g) f ◦ g = g ◦ f не выполняется.

Нейтральные элементы

Пусть – бинарная алгебраическая операция на непустом множестве А. Определение 4.7. Элемент е А называется нейтральным относительно

операции , если ( a А) a e = e a = a.

Теорема 4.1. Если нейтральный элемент относительно операции существует, то он единственен.

Доказательство. Пусть e и e′ – нейтральные элементы относительно операции . Тогда e = e e′ = e′, то есть e = e′.

Пример 4.3. 1. Число 0 есть нейтральный элемент относительно сложения действительных чисел. Число 1 есть нейтральный элемент относительно умножения действительных чисел.

2. На булеане Р(А) пустое множество является нейтральным элементом относительно объединения подмножеств непустого множества А, а Р(А) – нейтральным элементом относительно пересечения подмножеств.

Симметричные элементы

Пусть есть бинарная алгебраическая операция на непустом множестве А и элемент е А – нейтральный элемент относительно .

Определение 4.8. Элемент а′ А называется симметричным к элементу а А относительно операции , если а a' = a′ a = е. В этом случае элемент а называется симметризуемым, а элементы а и а′ – взаимно симметричными.

Пример 4.4. 1. Любое целое число имеет симметричный к нему элемент относительно сложения – то же число, взятое со знаком минус.

2. Любое ненулевое действительное число а имеет симметричный к нему

элемент 1 , число нуль не имеет симметричного элемента относительно умно- a

жения.

Теорема 4.2. Если операция ассоциативна и элемент a симметризуем, то существует единственный элемент, симметричный к а.

Доказательство. Пусть a′, a″ есть элементы, симметричные к элементу a относительно . Следовательно, a a′ = a′ a = e и a a″ = a″ a = e. Тогда в силу ассоциативности операции получаем

a′ = a′ e = a′ (a a″ ) = (a′ a) a″ = e a″ = a″ , то есть a′ = a″ .

57

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

операции

Пусть – бинарная алгебраическая операция на непустом множестве А. Определение 4.9. Подмножество B множества А называется замкнутым

относительно операции , если ( a, b B) a b B.

Пустое множество замкнуто относительно любой операции .

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

Аддитивная и мультипликативная форма записи бинарной алгебраи-

ческой операции

Для обозначения бинарной алгебраической операции наиболее часто используются аддитивная и мультипликативная формы записи. При аддитивной форме записи операцию называют сложением, а ее результат a b – суммой а и b. При этом вместо a b пишут а + b. Нейтральный элемент относительно сложения называют нулевым элементом (или нулем) и обозначают символом 0.

Элемент, симметричный к элементу а, называют противоположным к элементу а и обозначают через –а.

При мультипликативной форме записи операцию называют умножени- ем, а ее результат а b – произведением а и b. При этом вместо а b пишут

a b. Нейтральный элемент относительно умножения называют единичным элементом (или единицей) и обозначают символом 1. Элемент, симметричный к элементу а, называют обратным к элементу а и обозначают через а-1.

4.2. Понятие алгебраической структуры

Определение 4.10. Алгебраической структурой (универсальной алгеброй

или просто алгеброй) называется упорядоченная пара А = < A, Σ >, где A – непустое множество и Σ – множество алгебраических операций на A.

Таким образом, алгебра представляет собой непустое множество A вместе

с заданной на нем совокупностью операций Σ = {f1, …, fm, …}, где fi: Ani → A и ni – ранг операции fi. Множество A называется основным (несущим) множест- вом или основой (носителем) алгебры; упорядоченная последовательность рангов (n1,…, nm) называется типом алгебры; множество операций Σ называется

сигнатурой алгебры.

Если < A, Σ > – алгебра, то также говорят, что множество A есть алгебра относительно операций Σ.

Наиболее частым является случай, когда сигнатура конечна. Если

Σ = {f1, …, fm}, то вместо записи А = < A, {f1, …, fm }> обычно употребляется запись А = < A, f1, …, fm >.

58

Замечание 4.1. Для обозначения алгебры везде, где это необходимо, используется рукописная прописная буква латинского алфавита, а для обозначе-

называются однотипными, если их типы совпадают, то есть ранг операции fi совпадает с рангом соответствующей ей операции fi′ для i = 1,…, m.

Пример 4.6. 1. Пусть + и · (сложение и умножение) – арифметические операции на множестве действительных чисел. Алгебра < R, +, · > является алгеброй типа (2, 2).

2. Пусть P(A) – булеан непустого множества A и , ∩, – операции пересечения, объединения и дополнения над подмножествами множества A. Алгеб-

Определение 4.13. Пусть А = < A, f1, …, fm > – алгебра и В A. Подмножество В множества A называется замкнутым в алгебре А, если В замкнуто относительно каждой операции fi (i = 1, …, m) алгебры А, то есть выполняется ус-

Если fi – нульарная операция, которая выделяет элемент a A, то условие (13) принимает вид a В.

Из определений 4.12 и 4.13 непосредственно вытекает следующая теоре-

ма.

Теорема 4.3. Пусть А = < A, f1, …, fm > – алгебра и В – непустое подмножество множества A, замкнутое в алгебре А. Тогда алгебра В = < В, f1, …, fm > является подалгеброй алгебры А.

Пример 4.7. Рассмотрим алгебру < N, +, >, где + и – обычные операции сложения и умножения натуральных чисел. Пусть M – множество четных чисел, то есть M ={2k k N}. Множество M замкнуто относительно операций

сложения и умножения натуральных чисел. Действительно,

( 2k1, 2k2 M) 2k1 + 2k2 = 2(k1 + k2) M и 2k1 2k2 = 2(2k1 k2) M, так как множество N замкнуто относительно сложения и умножения. Следовательно,

по теореме 4.3 алгебра < M, +, > является подалгеброй алгебры < N, +, >.

4.3. Алгебры с одной бинарной алгебраической операцией

Рассмотрим алгебры, наиболее часто используемые в теории и на практи-

ке.

Пусть A – непустое множество.

59

Определение 4.14. Алгебра А = < A, >, где – бинарная алгебраическая операция, называется группоидом.

Таким образом, группоид определяется непустым множеством A и правилом, по которому можно найти значение операции для любых двух элементов из A.

Если множество A конечно, то эту информацию можно записать в виде таблицы.

Определение 4.15. Пусть на конечном множестве A = {a1, …, an} определена бинарная операция . Таблица, состоящая из n строк и n столбцов, в которой на пересечении i-й строки и j-го столбца располагается значение операции ai aj, называется таблицей Кэли:

Замечание 4.2. Артур Кли (1821 – 1895) – английский математик.

Замечание 4.3. 1. Если операция коммутативна, то таблица Кэли симметрична относительно главной диагонали.

2.Если для некоторого i {1, 2, …, n} элемент ai является нейтральным элементом относительно операции , то соответствующие этому элементу i-я строка и i-й столбец таблицы Кэли имеют вид (a1, a2, …, an).

3.Пусть элемент ai – нейтральный элемент относительно операции . Для элемента aj существует симметричный к нему элемент относительно , если в таблице Кэли среди элементов j-й строки и j-го столбца есть элемент ai.

Определение 4.16. Алгебра А = < A, >, где – ассоциативная бинарная алгебраическая операция, называется полугруппой.

Пример 4.8. Алгебра < N, + > является полугруппой, так как бинарная

операция + (обычная операция сложения натуральных чисел) ассоциативна. Определение 4.17. Алгебра А = < A, >, в которой является ассоциа-

тивной бинарной алгебраической операцией и существует нейтральный элемент e относительно , называется моноидом.

Другими словами, моноидом является полугруппа с нейтральным элемен-

том.

Пример 4.9. Алгебра < N, > образует моноид, так как бинарная операция умножения ассоциативна и натуральное число 1 является нейтральным элементом относительно умножения.

Определение 4.18. Алгебра А = < А, > называется группой, если выполняются условия (аксиомы):

1)– ассоциативная бинарная операция;

2)существует нейтральный элемент относительно ;

60

3) для каждого элемента a А существует симметричный к нему элемент a′ А относительно операции .

Таким образом, группа – это моноид, в котором каждый элемент симметризуем.

Определение 4.19. Полугруппа, моноид или группа называется комму- тативной (коммутативным) или абелевой (абелевым), если бинарная алгебраическая операция коммутативна.

Замечание 4.4. Нильс Абель (1802 – 1829) – норвежский математик. Определение 4.20. Если носитель группы имеет конечную мощность, то

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

Пример 4.10. Полугруппы < N, + > и < N, · > не являются группами, так как в первой из них не существует нейтральный элемент относительно сложения, а во второй для любого элемента, за исключением числа 1, не существует симметричный к нему элемент.

Пример 4.11. Алгебра < Z, + > образует коммутативную аддитивную группу целых чисел. Действительно, бинарная алгебраическая операция сложения ассоциативна, число 0 есть нейтральный (нулевой) элемент, а симметричным (противоположным) к любому z Z является число − z.

Пример 4.12. Алгебра < R \{0}, · > есть коммутативная мультипликативная группа действительных чисел, так как бинарная алгебраическая операция умножения ассоциативна, нейтральным (единичным) элементом является число 1 и для всякого ненулевого действительного числа r существует симметричный

(обратный) к нему элемент 1 . r

Пример 4.13. Доказать, что множество R \ {1} образует коммутативную группу относительно операции , где a b = 2 (a – 1) (b – 1) + 1.

Решение. Покажем, что R \ {1} замкнуто относительно операции , то есть ( a, b R \ {1}) a b R \ {1}.

Действительно, a b = 1 2 (a – 1) (b – 1) + 1 = 1(a – 1) (b – 1) =0 a = 1 b = 1. Отсюда

( a, b R) a ≠ 1 b ≠ 1 a b ≠ 1. Далее проверим выполнение аксиом группы.

1. Докажем, что операция ассоциативна, то есть

( a, b, c R \ {1}) (a b) c = a (b c).

Рассмотрим левую и правую части этого равенства:

(a b) c = (2 (a – 1) (b – 1) + 1) с = 2 ((2 (a – 1) (b – 1) + 1) – 1) (с – 1) + + 1 = 4 (а – 1) (b – 1) (с – 1) + 1,

а (b c) = а (2 (b – 1) (c – 1) + 1) = 2 (a – 1) ((2 (b – 1) (c – 1) + 1) – 1) +

+ 1 = 4 (а – 1) (b – 1) (с – 1) + 1.

Итак, первая аксиома группы выполняется. Легко видеть, что операция коммутативна, то есть ( a, b R \ {1}) a b = b a.

2. Покажем, что существует нейтральный элемент относительно , то есть

61