Глава 13. Алгебраические структуры. Операции и алгебры

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

Всюду определенная (тотальная) функция J: Мп ® М Называется П-арной (П-местной) операцией На М.

Если операция J — бинарная (то есть J: М ´ М ® M), то будем писать AJ B Вместо J (A, B) или А B, где — знак операции.

Множество М Вместе с набором операций å = {J1, ..., JM}, JI : МM ® М, Где Ni — арность операции JI, Называется Алгебраической структурой, универсальной алгеброй Или просто Алгеброй. Множество М Называется Основным (Несущим) множеством, или Основой (Носителем); вектор арностей (N1, ...,Nm) называется Типом; Множество операций å называется Сигнатурой. Запись: (М; å) или (М; J1, ..., JM).

Если в качестве JI Допускаются не только функции, но и отношения, то множе­ство М Вместе с набором операций и отношений называется Моделью.

В приложениях обычно используется следующее обобщение понятия алгебры. Пусть М = {M1, ... , Мn } — множество Основ, å = {JI, … , JM} – сигнатура, причем JI : Mi1 ´ … ´ Min. ® Mj. Тогда (M; å) называется Многоосновной Ал­геброй. Другими словами, многоосновная алгебра имеет несколько носителей, а каждая операция сигнатуры действует из прямого произведения некоторых но­сителей в некоторый носитель.

Замыкания и подалгебры

Подмножество X Ì М Называется Замкнутым Относительно операции J, если

" X1 , … , Xn Î C J( X1 , … , Xn) Î X.

Если X Замкнуто относительно всех J Î å, то (X; åX) называется Подалгеброй (M; åX), где åX = .

Пример

1. Алгебра {R; +, *} — Поле действительных чисел. Тип — (2,2). Все конечные подмножества, кроме {0}, не замкнуты относительно обеих операций. Поле рациональных чисел (Q; +, *) образует подалгебру.

2. Алгебра (2M; , , —) — Алгебра подмножеств Над множеством M. Тип — (2,2,1). При этом (2M; , , —) для любого подмножества X Множества М Обра­зует подалгебру.

3. Алгебра ({F | F : R ® R}; ), где — операция дифференцирования. Мно­жество элементарных функций образует подалгебру.

Свойства операций

Некоторые часто встречающиеся свойства операций имеют специальные назва­ния. Пусть задана алгебра (M; ∑) и A,B,C Тогда:

1. Ассоциативность:

2. Коммутативность:

3. Дистрибутивность слева:

4. Дистрибутивность справа:

5. Поглощение:

6. Идемпотентность:

Пример

1. Ассоциативные операции: сложение и умножение чисел, объединение и пере­сечение множеств, композиция отношений. Неассоциативные операции: воз­ведение чисел в степень, вычитание множеств.

2. Коммутативные операции: сложение и умножение чисел, объединение и пе­ресечение множеств. Некоммутативные операции: умножение матриц, компо­зиция отношений.

3. Дистрибутивные операции: умножение относительно сложения чисел. Недис­трибутивные операции: возведение в степень дистрибутивно относительно умножения справа, но не слева:

((Ab)C = Acbc, Abc ¹ аbас).

4. Пересечение поглощает объединение, объединение поглощает пересечение. Сложение и умножение не поглощают друг друга.

5. Идемпотентные операции: наибольший общий делитель натуральных чисел, объединение и пересечение множеств. Неидемпотентные операции: сложение и умножение чисел.

< Предыдущая		Следующая >