Дискретная математика / ДМиМЛ-1 часть

2.1. Операции на множествах

Частным случаем функции является операция, т.е. функциональное отображение вида : MⁿМ, где  знак отображения. Такая функция называется n-арной операцией, в ней области определения аргументов и область значений функции совпадают, n-местная операция по n элементам множества определяет (n+1)-й элемент этого же множества [9-10].

Алгеброй А называется совокупность <> множества М с заданными на нем операциями S={₁₁,₁₂,...₁_n₁,₂₁,...₂_n₂,_m₁,_m₂,..._mnm}, А=<М,S>, где множество М – носитель, S – сигнатура алгебры [9-10, 19]. Каждый первый индекс у идентификатора операции указывает ее местность.

Алгебра типа <М,₂>, т.е. алгебра с бинарной операцией, называется группоидом.

Рассмотрим квадрат с вершинами в точках а₁, а₂, а₃, а₄, пронумерованных против часовой стрелки, и повороты квадрата вокруг центра также против часовой стрелки, переводящие вершины в другие вершины [19]. Таких поворотов бесконечное множество: на углы 0, ,, 3, 2, 5, ..., однако они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырем поворотам.

Можно сказать, что задана алгебра А=<М,₁> с основным множеством М={а₁,а₂,а₃,а₄} и четырьмя унарными операциями ММ, которые обозначим буквами , , , . Зададим эти операции таблицей (табл. 1).

Таблица 1

Унарные операции алгебры поворотов квадрата

				
а₁	а₁	а₂	а₃	а₄
а₂	а₂	а₃	а₄	а₁
а₃	а₃	а₄	а₁	а₂
а₄	а₄	а₁	а₂	а₃
	0			3

Можно интерпретировать такие операции также циклическими сдвигами бит информации вида:

Множество 0={,,,} отображений вершин в себя вместе с бинарной операцией 0²0 последовательного выполнения отображений (выполнения поворота за поворотом, композиции поворотов), которую обозначим символом «¤» образует алгебру с бинарной операцией <0, ¤> [19]. Она задается табл. 2, в которой на пересечении строки i и столбца j записан результат операции ioj.

Таблица 2

Бинарные операции 0²0 алгебры

композиций поворотов квадрата

i j				
				
				
				
					i¤j

Такая таблица (см. табл. 2), задающая бинарную операцию, называется таблицей Кэли.

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

Пусть А=<М,₂> – группоид. Обозначим, как и в предыдущем примере, ₂ символом ¤ [9].

Тогда элемент nМ называется правым нейтральным элементом группоида А, если для всякого mМ выполняется равенство m¤n=m.

Для левого нейтрального элемента выполняется равенство n¤m=m.

В дальнейшем для краткости вместо слов «все», «всякий» будем использовать символ  (перевернутая буква А – первая буква английского слова All – все, этот символ называется еще квантором общности; квантор существования обозначается  и означает «существует», «имеется», «есть»).

Элемент n, являющийся одновременно и левым, и правым нейтральным элементом, называют двухсторонним нейтральным элементом или просто нейтральным элементом.

Для смешивания красок нейтральный элемент – бесцветный лак.

Если группоид <М, ¤> мультипликативный, т.е. его бинарная операция ¤ имеет тип умножения (·), то нейтральный элемент называется единицей и обозначается 1, если группоид аддитивный, т.е. бинарная операция ¤ имеет тип сложения (+), то нейтральный элемент называется нулем и обозначается 0 [9]. Нейтральный элемент в группоиде всегда единственный.

Коммутативный группоид, т.е. группоид, в котором

(х,yМ)(х¤y=y¤х),

называется коммутативным или абелевым.

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

(х,y,zМ)(х¤ (y¤z)=(x¤y) ¤z),

называется ассоциативным или полугруппой.

Полугруппа с единицей называется моноидом. В алгебре поворотов квадрата (см. табл. 2) единицей служит поворот на нулевой угол ().

Группой называется полугруппа с единицей, в которой для каждого элемента а существует элемент а^-1, называемый обратным (а¤а^-1=а^-1¤а=n) и каждое из уравнений a¤x=b, y¤a=b обладает единственным решением [9].

В алгебре поворотов квадрата (см. табл. 2), являющейся группой, обратным к данному повороту является поворот, дополняющий его до 2:

^-1=, ^-1=, ^-1=.

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

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

Содержание