Материал: Дискретная математика теория и практика

А4. Операции , дистрибутивны относительно друг друга, то есть

( a,b, c A) a (b c) = (a b) (a c) a (b c) = (a b) (a c) .

A5. ( a A) a A : a a = e2 , a a = e1.

Замечание 4.6. Аксиома А5 может побудить к ошибочному заключению о том, что элемент a является симметричным к элементу а, однако это неверно. Если бы a был симметричным элементом к а , то a a = e1 и a a = e2 . Срав-

нивая с аксиомой А5, заключаем, что a не является симметричным элементом к а ни для одной из бинарных операций.

Бинарную операцию называют сложением, бинарную операцию –

умножением, элементы a b и a b – суммой и произведением, соответствен-

но. Унарную операцию « » называют дополнением, а элемент a – дополнением

к элементу a.

Существует несколько альтернативных способов записи бинарных операций сложения и умножения:

Определение 4.30. Для любого выражения булевой алгебры двойствен- ным выражением (или дуализмом) называется выражение, полученное из исходного, заменой на , на , e1 на e2 , e2 на e1.

Заметим, что каждая из аксиом булевой алгебры – это пара аксиом. Внутри каждой пары каждая аксиома является двойственным выражением по отношению к другой.

Пример 4.20. Наиболее простой из булевых алгебр является алгебра <{0, 1}, , , >, в которой две бинарные операции (дизъюнкция), (конъюнкция) и одна унарная операция (отрицание) задаются таблицами Кэли:

Эта булева алгебра носит название двоичной алгебры логики. В ней роль операции сложения играет дизъюнкция, роль операции умножения – конъюнкция, роль операции дополнения – отрицание. Элемент 0 является нейтральным элементом относительно дизъюнкции, а элемент 1 – нейтральным элементом относительно конъюнкции.

Пример 4.21. Пусть А – непустое множество. Тогда < P(A), , ∩, >

есть булева алгебра, носящая название алгебры множеств (или алгебры Кан- тора). Носителем ее является булеан множества А, сигнатурой – операции объ-

67

единения, пересечения подмножеств множества А, дополнения данного подмножества до множества А, играющих соответственно роли сложения, умножения и дополнения. Пустое множество является нейтральным элементом относительно объединения, а само множество А – нейтральным элементом относительно пересечения.

Свойства булевой алгебры

Утверждение 4.2 (принцип двойственности). Для любой теоремы бу-

левой алгебры двойственная теорема также верна.

Теорема 4.5. Нейтральные элементы e1 и e2 относительно и соответственно единственны.

Теорема 4.6. ( a A) !a A : a a = e2 , a a = e1.

Замечание 4.7. Знак «!» означает слово «единственный».

Теорема 4.7 (закон идемпотентности).

( a A) a a = a , a a = a .

Теорема 4.8 (закон идентичности).

( a A) a e2 = e2 , a e1 = e1 a = e1 .

Теорема 4.9 (закон абсорбции или поглощения).

( a,b A)a (a b) = a , a (a b) = a .

Теорема 4.10 (закон инволюции).

( a A) a = a .

Теорема 4.11 (законы де Моргана).

( a,b A) a b = a b , a b = a b .

Теорема 4.12. e1 = e2 , e2 = e1 .

Докажем, например, теорему 4.11, в частности, a b = a b .

Из аксиомы A5 следует, что для этого достаточно показать выполнение ра-

венства (a b) (a b)= e2 . Действительно, (a b) (a b) = ((a b) a) ((a b) b)=

= (a (a b)) ((a b) b) = ((a a) b) (a (b b)) = (e2 b) (a e2 ) = e2 e2 = e2

a b = a b .

Второй закон де Моргана верен по принципу двойственности.

4.7. Гомоморфизмы алгебр

то есть для любого i {1, …, m} операция fi алгебры А и соответствующая ей операция fi′ алгебры В имеют одинаковые ранги. Говорят, что отображение h носителя А в носитель В сохраняет операцию fi алгебры А, если

где ni – ранг операции fi.

68

Определение 4.31. Гомоморфизмом алгебры А в (на) однотипную алгебру В называют такое отображение h носителя A в (на) носитель В, которое сохраняет все операции алгебры А , то есть для любой операции fi (i = 1, …, m) алгебры А выполняется условие ( ).

Определение 4.32. Гомоморфизм h алгебры А в алгебру В называется мо- номорфизмом (или вложением), если h является инъективным отображением носителя А в носитель В.

Определение 4.33. Гомоморфизм алгебры А на алгебру В называется

эпиморфизмом.

Определение 4.34. Гомоморфизм h алгебры А на алгебру В называют изоморфизмом, если h есть инъективное отображение носителя А на

носитель В.

Определение 4.35. Алгебры А и В называются изоморфными, если существует изоморфизм алгебры А на алгебру В. При этом пишут А В.

Другими словами, отображение h является изоморфизмом алгебры А на алгебру В, если h – биективное отображение носителя А на носитель В.

Определение 4.36. Гомоморфизм алгебры А в себя называется эндомор-

физмом.

Определение 4.37. Изоморфизм алгебры А на себя называется автомор-

физмом.

На рис. 4.1 представлена схема определения частного случая гомоморфизма.

h – инъекция

Изоморфизм

А = В

Автоморфизм

Рис. 4.1

Пример 4.22. Дано отображение

h: < {y = ax + b a,b R, a ≠ 0},o > → < R \ {0}, > , где y = ax + b a a .

Выяснить, является ли h гомоморфизмом. Если да, то какой частный случай гомоморфизма имеет место.

69

Решение. Пусть A = {y = ax + b a, b R, a ≠ 0}. Проверим, сохраняет ли h операцию o , то есть выполняется ли условие:

( a1x + b1, a2 x + b2 A) h((a1x + b1 )o (a2 x + b2 ))= h(a1x + b1 ) h(a2 x + b2 ) .

Преобразуя левую и правую части равенства, получим:

Из (15) и (16) следует, что h – гомоморфизм алгебры

< {y = ax + b a,b R, a ≠ 0}, o > в алгебру < R \ {0}, > .

Далее выясним, является ли отображение h инъективным или сюръектив-

ным.

= h(a2 x + b2 ) a1 x + b1 = a2 x + b2 .

Это условие не выполняется, так как для любых b1≠ b2

h(a1 x + b1 ) = h(a2 x + b2 ) . Следовательно, отображение h не является инъективным.

def

h – сюръекция Im h = R \ {0}.

множество положительных действительных чисел).

Решение. Проверим, сохраняет ли h операцию +, то есть выполняется ли условие: ( a,b R) h (a + b) = h(a) h(b) .

Преобразуя левую и правую части равенства, получим:

Из (17) и (18) следует, что h – гомоморфизм алгебры < R, + > в алгебру

< R+ , > .

Далее, ( a,b R ) 3a =3b a = b. Следовательно, h – инъекция. Имеем: ( c R+ ) h−1 (c) = log3 c . Следовательно, h – сюръекция.

Значит, h является изоморфизмом алгебры < R, + > на алгебру < R+ , > .

4.8. Алгебраические системы. Решетки

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

70