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

Естественно начать изучение алгебраических структур (алгебр) с наиболее простых. Самой простой алгеброй является алгебра с одной унарной операцией, но этот случай настолько тривиален, что про него нечего сказать. Поэтому начнем с алгебры с одной бинарной операцией .

1. Алгебра вида , где бинарная операция, называется группоидом.

Если – операция типа умножения, то группоид называется мультипликативным; если – операция типа сложения, группоид называется аддитивным.

2. Полугруппа – это группоид с одной ассоциативной бинарной операцией. Т.е. для всех элементов верно .

Пример 1. Всякое множество функций, замкнутое относительно суперпозиции, является полугруппой, (множество элементарных функций).

Пример 2. Множество слов W(X) алфавита X образует полугруппу относительно операции конкатенации.

Рассмотрим непустое множество символов X={x,y,z,...} независимое алфавитом. Конечные наборы написанных друг за другом символов из X называются словами. Например, x, y, xy, yx, zxx, xyyz и т.д. Элемент x_i слова x₁,x₂, ...,x_n называется его i-й координатой. Число n называется длиной слова. Считается, что множество W(X) слов алфавита содержит слово Λ, не имеющее символов и называемое пустым словом. Длина пустого слова Λ по определению равна 0.

Операция конкатенации на W(X) определяется следующим образом:

Если α,_,β € W(X), то αˆβ = αβ, т.е. результатом является слово, полученное соединением слов α и β (например, xyzˆzx = xyzzx). Операция ассоциативна, т.е. для любых слов α,β,γ верно (αˆβ)ˆγ = αˆ(βˆγ). Следовательно, алгебра <W(X);ˆ > является полугруппой.

Теорема (Марков-Пост, совр. мат. 1903-1979, без доказательства):

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

3. Моноиды. Полугруппа, содержащая нейтральный элемент (единицу), называется моноидом.

Т.е. существует eєA такой, что e°a = aºe = a для всех aєA.

Пример Так как для всех слов αєW(X) верно

Λˆα = αˆΛ = α, где Λ – пустое слово, то Λ удовлетворяет свойству единицы. Таким образом, алгебра <W(X);ˆ > является моноидом.

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

Теорема. Единица единственна.

Доказательство: Пусть существуют две единицы e₁ и e₂ для каждого a:

a°e₁ = e₁a = a и a°e₂ = e₂°a = a. Тогда

e₁°e₂ = e₁ и e₁°e₂ = e₂ => e₁ = e₂

4. Группы. Группа – это моноид, в котором для каждого элемента существует обратный:

для каждого a существует a^-1: aºa^-1 = a^-1ºa = e

Пример 1. Множество невырожденных квадратных матриц порядка n и операций умножения матриц образует группу. Единицей является единичная матрица. Обратным элементом является обратная матрица.

Пример 2. Множество взаимно однозначных функций ƒ: М→М является группой относительно операции суперпозиции. Единицей группы является тождественная функция, а обратным элементом – обратная функция.

Группа , в которой - коммутативная операция, называется абелевой, т.е. .

В абелевых группах приняты следующие обозначения:

групповая операция обозначается + или ;

обратный элемент к а (а^-1) обозначается – а;

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

Пример 3. <Z ;+> - множество целых чисел образует абелеву группу относительно сложения. Нулем является число 0. Обратным элементом группы является число с противоположным знаком: a^-1=-a

Пример 4.

Множество рациональных чисел, не содержащее 0, с операцией обычного умножения образует абелеву группу. Обратным элементом является обратное число .