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

Частным случаем функции является операция, т.е. функциональное отображение вида : MnМ, где  знак отображения. Такая функция называется n-арной операцией, в ней области определения аргументов и область значений функции совпадают, n-местная операция по n элемен-там множества определяет (n+1)-й элемент этого же множества [9-10].
Алгеброй А называется совокупность <> множества М с заданными на нем операциями S={11,12,...1n1,21,...2n2,m1,m2,...mnm}, А=<М,S>, где множество М – носитель, S – сигнатура алгебры [9-10, 19]. Каждый первый индекс у идентификатора операции указывает ее местность.
Алгебра типа <М,2>, т.е. алгебра с бинарной операцией, называется группоидом.
Рассмотрим квадрат с вершинами в точках а1, а2, а3, а4, пронумерованных против часовой стрелки, и повороты квадрата вокруг центра также против часовой стрелки, переводящие вершины в другие вершины [19]. Таких поворотов бесконечное множество: на углы 0,  , , 3 , 2, 5 , ..., однако они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырем поворотам.
Можно сказать, что задана алгебра А=<М,1> с основным множеством М={а1,а2,а3,а4} и четырьмя унарными операциями ММ, которые обозначим буквами , , , . Зададим эти операции таблицей (табл. 1).
Таблица 1
Унарные операции алгебры поворотов квадрата
http://s60.radikal.ru/i168/1105/f4/35198cb04a2a.jpg

Можно интерпретировать такие операции также циклическими сдви-гами бит информации вида:
http://s57.radikal.ru/i155/1105/53/2c699518835c.jpg .
Множество 0={,,,} отображений вершин в себя вместе с бинарной операцией 020 последовательного выполнения отображений (выполнения поворота за поворотом, композиции поворотов), которую обозначим символом «¤» образует алгебру с бинарной операцией <0, ¤> [19]. Она задается табл. 2, в которой на пересечении строки i и столбца j записан результат операции ioj.
Таблица 2
Бинарные операции 020 алгебры
композиций поворотов квадрата

http://s59.radikal.ru/i163/1105/e1/9cfbb4fa3ec5.jpg

Такая таблица (см. табл. 2), задающая бинарную операцию, называется таблицей Кэли.
Можно представить бинарной операцией, например, смешивание красок, когда из двух цветов получается третий, входящий, однако во множество всех цветов.
Пусть А=<М,2> – группоид. Обозначим, как и в предыдущем примере, 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=.
Группа, все элементы которой являются степенями одного элемента а, называется циклической. Циклическая группа всегда абелева.
Множество рациональных чисел, не содержащее нуля, с операцией умножения является абелевой группой. Обратным к элементу а, является элемент  .

Алгебра множеств (алгебра Кантора)

Алгебра Кантора: <B(I),,,–>. Носителем ее является булеан универсального множества I, сигнатурой – операции объединения , пересечения  и дополнения –[9].
Для операций алгебры Кантора выполняются следующие законы:
http://s003.radikal.ru/i202/1105/c7/0223f5aba73e.jpg
1) коммутативности объединения и пересечения:
МаМb=МbМа, МаМb=МbМа;
2) ассоциативности объединения и пересечения:
Ма(Мb  Мс)=(МаМb)Мс, Ма(МbМс)=(МаМb)Мс;
3) дистрибутивности пересечения относительно объединения и объе-динения относительно пересечения:
Ма(МbМс)=(МаМb)(МаМс),
Ма(МbМс)=(МаМb)(МаМс),
причем последнее соотношение не имеет аналога в обычной алгебре;
4) идемпотентности объединения и пересечения:
МаМа=Ма, МаМа=Ма,
поэтому в алгебре Кантора нет ни степеней, ни коэффициентов;
5) де Моргана:
http://s004.radikal.ru/i205/1105/6d/83aa28319bfc.jpg
6) двойного дополнения:
.
Выполнимы также следующие действия с универсальным I и пустым  множествами:
7)http://s61.radikal.ru/i172/1105/5b/4efef17b135f.jpg
Все эти соотношения могут быть доказаны с использованием кругов Эйлера. Видны двойственность соотношений: они справедливы как относительно объединения, так и относительно пересечения.
Рассмотрим дополнительные законы:
8) склеивания:
http://s57.radikal.ru/i158/1105/c5/753defc6913e.jpg
9) поглощения:
М(МА)=М;
10) Порецкого – по фамилии российского логика, математика и астронома, профессора Казанского университета Платона Сергеевича Порецкого (1846-1907 гг.):
.
Алгебра Кантора по аддитивной операции объединения и мультипликативной операции пересечения является абелевой полугруппой, так как для этих операций выполняются законы коммутативности и ассоциативности, но она не является группой, поскольку уравнения МаХ=Мb, МаХ=Мb не имеют решения, например, для случая, когда множества не пересекаются: МаМb= [9]. Поэтому алгебра Кантора по двухместным операциям  и  не является кольцом. Эта алгебра принадлежит к другому классу фундаментальных алгебр – к классу решеток.