Дискретно-непрерывная математика (стр. 17 )

Ma Mb Mc) = Ma Mb Ma Mc,

Ma (Mb Мс) = (Ma Mb) (Ma Мс);

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

Ма Ма = Ма, Ма Ма = Ма;

действия с универсальным 1 и пустым множествами

M = M, M = , M 1 = 1, M 1=M, M = 1,

M = ;

де-Моргана

= a b, = а b;

двойного дополнения

= M.

Алгебра Кантора по аддитивной операции объединения и мультипликативной операции пересечения является абелевой полугруппой, так как для этих операций выполняются законы коммутативности и ассоциативности, но она не является группой, поскольку уравнения Ма X=Мb, Ма X=Мb не имеют решения, например для случая, когда множества не пересекаются: МаМ b =. Следовательно, алгебра Кантора по двуместным операциям и не является кольцом. Эта алгебра принадлежит к другому классу фундаментальных алгебр - к классу решеток, который будет рассмотрен дальше.

1.12. Свойства бинарных алгебраических операций.

Для того чтобы следующие соотношения выглядели более привычно, условимся результат применения бинарной операции φ к элементам a, b записывать не в функциональном виде φ(а, b), а в виде аφb, так, как это принято для арифметических операций.

Операция φ называется ассоциативной, если для любых элементов а, b, с

(аφb) φс =аφ(bφс).

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении аφbφс можно не проставлять. Сложение и умножение чисел ассоциативны, что и позволяет не ставить скобки в выражениях а+b+с и abc. Пример неассоциативной операции — возведение в степень аb: (аb)c≠а. Правда, запись а считается допустимой, но служит сокращением выражения а а не (аb)с, еоторое равно более компактному выражению аbс.

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

Операция φ называется коммутативной, если для любых элементов а, b

аφb = bφа.

Сложение коммутативно («от перемены мест слагаемых сумма не меняется»), равно как и умножение; вычитание и деление некоммутативны. Некоммутативным является умножение матриц, например

но

Операция φ называется дистрибутивной слева относительно операции ψ, если для любых а, b, с

аφ(bψс) = (аφb)ψ(аφс),

и дистрибутивной справа относительно ψ, если

(aψb)φс = (аφс)ψ(bφс).

Дистрибутивность позволяет раскрывать скобки. Например, умножение дистрибутивно относительно сложения слева и справа. Возведение в степень дистрибутивно относительно умножения справа: (ab)c=acbc, но не слева: abc≠аbас. Сложение не дистрибутивно относительно умножения: а+bс≠(а+ b)(а + с). Операции пересечения и объединения множеств дистрибутивны относительно друг друга слева и справа.

Гомоморфизм и изоморфизм. Алгебры с различными типами, очевидно, имеют существенным образом разное строение. Если же алгебры имеют одинаковый тип, то наличие в них сходства характеризуется с помощью понятий гомоморфизма, которые вводятся ниже, и изоморфизма.

Пусть дано две алгебры А=(К; φ1, ..., φр) и В=(М; ψ1, ..., ψр) одинакового типа.

Гомоморфизмом алгебры А в алгебру В называется отображение Г: К→ М, которое удовлетворяет условию

Г (φi ( ..... ))=ψi (Г( ),…,Г ( )) (1.74)

для всех i= 1, ..., р [l(i) — арность операций φи и ψi, которая в них по условию одинакова] и всех К. Смысл условия (1.74) в том, что, независимо от того, выполнена ли сначала операция φi в А и потом выполнено отображения Г, или сначала выполнено отображения Г, а затем в В выполнена соответствующая операция ψi, результат будет одинаков.

Изоморфизмом алгебры А на алгебру В называется взаимооднозначный гомоморфизм. В этом случае существует обратное отображение Г-1:М→ К, которое является также взаимооднозначным. Пусть Г (kj)= тj, тj М. Тогда kj = Г-1тj. Заменим в условии (1.74) левые части этих равенств на правые и применим Г-1 к обеим частям равенства, которые получены. Так как Г-1Г является тождественным отображением: Г-1Г (а) = а, то получим:

φи(Г-1 ( ).....Г-1( )=Г-1ψi ( ,…,)) (1.75)

Равенство (1.75) — это то же равенство (1.74) с заменой Г на Г-1, элементов К на элементы М и переменной мест φi и ψi; другими словами, Г-1 — это изоморфизм В на А. Следовательно, если существует изоморфизм А на В, то существует изоморфизм В на А; при этом алгебры А и В называются изоморфными. Мощности основных множеств изоморфных алгебр равны (при гомоморфизме это равенство может не выполняться). Если А = В, то изоморфизм называется

изоморфизмом на себя, или автоморфизмом; если ВА, то изоморфизм называется изоморфизмом в себя.

Отношение изоморфизма является отношением эквивалентности на множестве алгебр. Рефлексивность его очевидна, симметричность следует из существования обратного изоморфизма, а транзитивность устанавливается следующим образом: если Г1 — изоморфизм А на В, Г2 — изоморфизм В на С, то изоморфизмом А на С будет композиция Г1 и Г2. Классами эквивалентности в разбиении относительно изоморфизма есть классы изоморфных между собой алгебр.