§ 2. Простейшие операционные структуры

Начнем детальное изучение алгебраических структур с рассмотрения тех из них, которые имеют только одну бинарную операцию. Где это возможно, будем в этом и последующих параграфах представлять структуры в (при­близительно) возрастающем порядке «силы». (Говорят, что структура А слабее структуры В, если А можно рас­сматривать как В «с отброшенной структурой». Как мы увидим позже, некоторые структуры получают путем «слияния» двух более слабых структур, и, следователь­но, строгий порядок здесь невозможен.)

Обычно каждую структуру можно определить в тер­минах основных свойств, а не только в терминах про­стейших структур.

Определение. Полугруппой называется множест­во S с бинарной операцией , которая удовлетворяет только требованию ассоциативности

х (у z) = (х у) z, x, у, z S. //

Определение. Моноидом называют множество М вместе с бинарной операцией такой, что

1. ассоциативна;

2. существует u М такое, что

и х = х = х и для всех х М;

называют единицей по отношению к . //

Полугруппы и моноиды имеют особое значение при обработке строк символов и теории языков.

Пример 2.1. Пусть А = (х, у, z). Рассматривая х, у и z просто как символы, а не как имена объектов или «переменных», получаем, что А является алфавитом. Оп­ределим А* как множество всех строк символов, принад­лежащих А. Тогда А* включает х, у, z, хх, ху, ух, xxyz, zyx и т. д.; А* бесконечно.

На А* можно определить операцию конкатенации следующим образом: если , А*, то = , т. е. результатом является строка и сразу же за ней за­писанная строка . Таким образом, имеем

xyz z = xyzz, xz ух = хzyx и т. д.

Каждая строка имеет конечную длину, которая обо­значается через и равна числу символов в (при в том разрешаются повторения). Таким образом,

|х| = 1, |ху| = 2, |xxxzy| = 5.

Это несколько похоже на обозначение мощности множества, Заметим, в частности, что

|х| = 1, |{х}| = 1,

|ху| = 2, |{х, у}| = 2,

|ух| = 2, |{y, х}| = 2,

но

|хух| = 3, |{х, у, х}| = |{х, у}| = 2.

Поэтому нет полной аналогии, хотя существует аналогия с пустым множеством. Для обозначения строки, анало­гичной пустому множеству, будем использовать специ­альный символ , А*. Таким образом, | | = и = = для всех строк .

Следовательно, для любого алфавита А структура (А*, ) является моноидом, а — единица по отноше­нию к . //

(Может показаться, что символ * неверно употреб­ляется в обозначении А*, однако это не так: А* = *( ), где

R = {( , ): = , А}.)

Приведенный выше пример чрезвычайно важен. Для заданного, достаточно большого алфавита А, содержаще­го, например, все символы, доступные периферийным уст­ройствам какого-либо компьютера, все языки, используе­мые в компьютерных системах, являются подмножеством А*. Это понятие является основным при формальном изучении языков (см. гл. 8).

Третьей (и последней) операционной структурой яв­ляется непосредственное и естественное расширение мо­ноида.

Определение. Группой G называют множество с бинарной операцией такой, что

а) ассоциативна;

б) существует элемент u G (единица по отношению к ) такой, что

и х = х = х и для всех x G;

в) каждому элементу x G соответствует элемент у G такой, что

х у = и = у х;

у называется обратным элементом к х по отношению к . //

В случаях, когда групповая операция обозначается символом , единичный элемент обозначается 1, а об­ратный к элементу х элемент записывается в виде х^-1. Когда групповая операция обозначается символом , еди­ничный элемент обозначается 0, а обратный к элементу х элемент записывается в виде –х.

По сравнению с первыми двумя структурами группы обладают следующими важными свойствами. Внутри группы (G, ) можно решить уравнение

а х = b.

Более того, решение легко найти (однако заметим, что для этого требуются все аксиомы группы). Если

а х = b

то

a^-1 (а а) = а^-1 b (a G а^-1 G), (а^-1 а) х = а^-1 b ( ассоциативна), и х = а^-1 b (свойство обратных элементов),

поэтому

х = а^-1 b (свойство единицы).

Часто к словам «группа» и «моноид» приписывают тер­мин «коммутативный». Это просто означает, что опера­ция в рассматриваемой структуре удовлетворяет свойству коммутативности, т. е.

у х = х у для всех х, у М или G.

Можно сделать много полезных выводов из аксиом груп­пы. Рассмотрим простой пример.

Пример 2.2. В группе (G, *)

(а * b)^-1 = b^-1 a^-1.

Доказательство.

(а * b) * (b^-1 * а^-1) = а * ( b * b^-1) * а^-1 = а * 1 * а^-1 = а * а^-1 = 1.

Следовательно, b^-1 * а^-1 является правым обратным эле­ментом к а * b. Аналогично можно показать, что он яв­ляется левым обратным элементом, откуда и следует требуемый результат. //

Группы дают нам первый пример широко используе­мых изоморфизмов. Эти изоморфизмы (между группами (R, +) и (]0, [, *)) называют логарифмами. Они по­зволяют выполнять умножение при помощи сложения на основе следующего тождества:

a * b = φ ^-1(φ(a) + φ (b)),

где

φ: х → log_p, (х) для некоторого р ] — 1, ∞[,

Упражнение 5.2.

1. Доказать единственность единичного элемента и обратных элементов в группе (G, ).

2. В группе (G, ) показать, что если а b = а с, то b = с, а если х а = у а, то х = у.

3. Проверить, что множество перестановок конечного множества образует группу по отношению к операции умножения перестановок,