Тема 1. Элементы общей алгебры

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

Алгеброй А называется совокупность < > множества М с заданными на нем операциями A = < M, S >, где множество М — носитель, S — сигнатура алгебры. Каждый первый индекс у идентификатора операции указывает ее местность.

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

Рассмотрим квадрат с вершинами в точках а1, а2, а3, а4, пронумерованных против часовой стрелки, и повороты квадрата вокруг центра также против часовой стрелки, переводящие вершины в другие вершины. Таких поворотов бесконечное множество: на углы однако они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырем поворотам.

Можно сказать, что задана алгебра А = < М, φ 1> с основным множеством М = {а1, а2, а3, а4} и четырьмя унарными операциями М ↦ М, которые обозначим буквами α, β, ν, δ. Зададим эти операции табл. 1.

Таблица 1

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

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

Множество 0 = { α, β, ν, δ } отображений вершин в себя вместе с бинарной операцией 02↦ 0 последовательного выполнения отображений (выполнения поворота за поворотом, композиции поворотов), которую обозначим символом «¤», образует алгебру с бинарной операцией < 0, ¤>. Она задается табл. 2, в которой на пересечении строки i и столбца j записан результат операции i ¤ j.

Таблица 2

Бинарные операции 02 ↦ 0 алгебры композиций поворотов квадрата

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

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

Пусть А = < М, φ 2> — группоид. Обозначим, как и в предыдущем примере, φ 2символом ¤.

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

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

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

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

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

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

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

( ∀ x, у ∈ М) (х ¤ у = у ¤ х),

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

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

( ∀ x, у, z ∈ М) (х ¤ (у ¤ z ) = (х ¤ у) ¤ z ),

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

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

Группой называется полугруппа с единицей, в которой для каждого элемента а существует элемент а–1, называемый обратным (а ¤ а–1= а–1 ¤ а = n ), и каждое из уравнений а ¤ х = b, у ¤ а = b обладает единственным решением.

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

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

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

Группа подстановок Галуа

Рассмотрим знаменитую группу подстановок, которую исследовал выдающийся французский математик Э. Галуа (1811–1832).

Подстановкой n -й степени называется взаимно однозначное отображение множества из n элементов в себя.

Рассмотрим всего три элемента: х1, х2, х3.

Существует шесть вариантов последовательностей из трех элементов:

х1х2х3, х2х3х1, х1х3х2, х3х1х2, х2х1х3, х3х2х1.

Запишем порождение этих вариантов следующим образом:

Эта запись означает, что х1переходит (отображается) в х2, х2— в х3, х3 — в x 1.

Число таких возможных подстановок равно числу вариантов последовательностей из трех элементов. Обозначим возможные подстановки:

Произведением подстановок назовем последовательное выполнение сначала первой, а затем второй из перемножаемых подстановок.

Например,

Таким образом, имеем алгебру < П, ¤>, где П — множество подстановок {а, b, с, d, e, f }, ¤ — бинарная операция П2 ↦ П.

Соответствующая таблица Кэли для алгебры постановок Галуа имеет вид табл. 3.

Таблица 3

Таблица Кэли для алгебры подстановок Галуа

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

Нейтральным элементом является подстановка а.

Группа — это полугруппа взаимно однозначных преобразований, причем именно однозначность гарантирует наличие обратного преобразования. Можно сказать, что в группе при любом числе умножений не теряется информация об исходном элементе: если известно, на что умножали, всегда можно узнать, что умножали. Для полугруппы это верно не всегда. Пусть дана дискретная система с конечным числом состояний S = { S 1..., Sn}, на вход которой может быть подано входное воздействие из множества х = {х1,..., х m}. Всякое входное воздействие однозначно переводит состояние системы в некоторое другое состояние, т. е. является преобразованием множества S. Последовательности воздействий — композиция преобразований, поэтому множество всех последовательностей — полугруппа с образующими {х1,..., х m}. Если такая полугруппа является группой, то по любой входной последовательности и заключительному состоянию системы можно однозначно определить ее начальное состояние.

Алгебра < М, ·, +>, которая по умножению (·) является мультипликативным группоидом, а по сложению (+) — абелевой группой, причем умножение связано со сложением законом дистрибутивности

называется кольцом. Например, числовыми кольцами являются множество целых чисел, множество рациональных чисел, множество действительных чисел, множество комплексных чисел.

Кольцо, в котором все отличные от нуля элементы составляют группу по умножению, называется телом (имеются обратные элементы по умножению). Тело, у которого мультипликативная группа абелева, называется полем. Таковы поля Галуа.

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

Алгебра Кантора: < B ( I ), ∪ , ∩ , –>. Носителем ее является булеан универсального множества I, сигнатурой — операции объединения ∪ , пересечения ∩ и дополнения.

Для операций алгебры Кантора выполняются следующие законы:

1) коммутативности объединения и пересечения:

2) ассоциативности объединения и пересечения:

3) дистрибутивности пересечения относительно объединения и объединения относительно пересечения:

причем последнее соотношение не имеет аналога в обычной алгебре;

4) идемпотентности объединения и пересечения:

поэтому в алгебре Кантора нет ни степеней, ни коэффициентов;

5) де Моргана:

6) двойного дополнения:

Выполнимы также следующие действия с универсальным I и пустым ∅ множествами:

7 )

Все эти соотношения могут быть доказаны с использованием кругов Эйлера. Видна двойственность соотношений: они справедливы как относительно объединения, так и относительно пересечения.

Рассмотрим дополнительные законы:

8) склеивания:

9) поглощения:

10) Порецкого — по фамилии российского логика, математика и астронома, профессора Казанского университета Платона Сергеевича Порецкого (1846–1907 гг.):

Алгебра Кантора по аддитивной операции объединения и мультипликативной операции пересечения является абелевой полугруппой, так как для этих операций выполняются законы коммутативности и ассоциативности, но она не является группой, поскольку уравнения не имеют решения, например, для случая, когда множества не пересекаются: . Поэтому алгебра Кантора по двухместным операциям ∩ и ∪ не является кольцом. Эта алгебра принадлежит к другому классу фундаментальных алгебр — к классу решеток.

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒