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

( a R \ {1}) е R \ {1}: a е = е a = а. Рассмотрим равенство a е = а 2 (a – 1) (е – 1) + 1 = а. Выразим из этого равенства е:

2 (a – 1) (е – 1) – (а – 1) = 0 (a – 1) (2е – 2 – 1) = 0 (a – 1) (2е – 3) = 0

2е – 3 = 0 е = 3 R \ {1}. Следовательно, е = 3 – нейтральный элемент

4.4. Алгебры с двумя бинарными алгебраическими операциями

Среди алгебр с двумя бинарными алгебраическими операциями особо выделяются кольца и поля.

Определение 4.21. Алгебра А = < А, +, · > называется ассоциативным кольцом с единицей, если выполняются следующие условия (аксиомы):

1)алгебра < A, + > есть коммутативная аддитивная группа;

2)алгебра < A, · > есть мультипликативный моноид;

3)умножение дистрибутивно относительно сложения, то есть

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

Замечание 4.5. В дальнейшем под словом «кольцо» будем подразумевать ассоциативное кольцо с единицей.

Элементы множества А называются элементами кольца А = < А, +, · >.

Определение 4.22. Группа < A, + > называется аддитивной группой кольца А = < А, +, · >. Нейтральный элемент относительно сложения называется нулем кольца и обозначается через 0 или 0А.

Определение 4.23. Моноид < A, · > называется мультипликативным мо-

ноидом кольца А = < А, +, · >. Нейтральный элемент относительно умножения называется единицей кольца А и обозначается через 1 или 1А.

62

Определение 4.24. Кольцо называется коммутативным, если операция умножения коммутативна, т.е. ( a, b A) a b = b a .

Пример 4.14. Алгебра < Z, +, · > образует коммутативное кольцо целых чисел.

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

Пример 4.15. Кольцо целых чисел < Z, +, · > полем не является, так как ни один ненулевой элемент, кроме 1, не обладает обратным к нему.

Пример 4.16. Множества Q, R и С образуют бесконечные поля относительно обычных операций сложения и умножения, которые соответственно называются полем рациональных чисел, полем действительных чисел и полем комплексных чисел.

Решение. Докажем сначала, что операции сложения и умножения матриц являются бинарными алгебраическими операциями на множестве

относительно этих операций.

Следовательно, операции «+» и « » – бинарные алгебраические операции

на М.

Сложение произвольных матриц (если оно определено) коммутативно и ассоциативно. Значит, «+» коммутативно и ассоциативно на М. Очевидно, что

из множества М. Следовательно, < М, + > – коммутативная группа. Умножение произвольных матриц (если оно определено), а значит и мат-

63

x2a + y2 – y2a = x2 y2 (1 – a) = x2 (1 – a) 1 – a = 0 a = 1 b = y − y = 0. x

< М, > – моноид.

Известно, что умножение дистрибутивно относительно сложения для произвольных матриц (если операции имеют смысл), в частности, и для матриц из множества М.

Таким образом, алгебра < М, +, > – кольцо.

Получили, что « » – коммутативно. Следовательно, кольцо коммутативно.

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

Итак, алгебра < М, +, > образует коммутативное кольцо, но не является полем.

4.5. Конечные поля

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

64

Определим сначала бинарное отношение делимости на множестве Z. Определение 4.26. Целое число x делится на целое число y, если сущест-

вует z Z такое, что x = y z. При этом пишут x y и говорят, что «x делится на

y», или «x кратно y», или «y делит x».

Предложение «y делит x» записывают также в виде y | x.

Далее рассмотрим еще одно бинарное отношение ≡ на множестве Z. Определение 4.27. Целые числа x и y называются сравнимыми по модулю

n (n N), если разность (x – y) делится на n.

Если целое число x сравнимо с целым числом y по модулю n, то пишут

x ≡ y (mod n).

Покажем, что отношение сравнимости по модулю n обладает свойствами рефлексивности, симметричности и транзитивности, то есть является отношением эквивалентности. Действительно:

1)( x Z) x – x = 0 n x ≡ x (mod n) ≡ – рефлексивное отношение;

2)( x, y Z) x ≡ y (mod n) y ≡ x (mod n), так как (x – y) n y – x = = – (x – y) n. Следовательно, отношение ≡ симметрично.

3)( x, y, z Z) x ≡ y (mod n) y ≡ z (mod n) x ≡ z (mod n), так как если

(x – y) n (y – z) n, то (x – y) + (y – z) = x – z n. Следовательно, отношение ≡ транзитивно.

По теореме 3.1 отношение эквивалентности ≡ определяет разбиение множества Z на классы эквивалентности, которые называются классами вычетов по модулю n и обладают следующими свойствами:

1)любые два класса вычетов по модулю n либо совпадают, либо не пересекаются. Объединение всех классов вычетов по модулю n совпадает с множеством Z;

2)пусть A и B – классы вычетов по модулю n, a A и b B. Классы A и B совпадают тогда и только тогда, когда a ≡ b (mod n);

3)если A – класс вычетов по модулю n и a – произвольный элемент множества A, то A= {a + n k k Z}.

Пример 4.18. Пусть A – класс вычетов по модулю 2, и целое число 5 является представителем этого класса. Тогда

A= {5 + 2 k k Z} = {…, –9, –7, –5, –3, –1, 1, 3, 5, 7, 9, …}.

Выясним, какова мощность фактор-множества Z /≡, то есть сколько существует классов вычетов по модулю n.

Утверждение 4.1. Целые числа x и y сравнимы по модулю n тогда и только тогда, когда при делении на n они дают одинаковые остатки.

Существуют n различных остатков при делении целых чисел на n: 0, 1, 2, …, n – 1. Согласно утверждению 4.1 получаем, что Z / ≡ = n.

Итак, множество целых чисел по отношению сравнимости по модулю n разбивается на n классов эквивалентности, которые обозначим следующим образом: 0, 1,... , n −1 . Фактор-множество Z / ≡ обозначим через Z n .

65

Определение 4.28. Введем на множестве Z n ={0, 1, ..., n − 1} бинарные операции сложения и умножения следующим образом: x + y = x + y и x y = x y .

Определение операций сложения и умножения на множестве Z n кор-

ректно, так как если х1 ≡ х (mod n) и y1 ≡ y (mod n), то х1 + у1 ≡ (х + у) (mod n) и x1 · y1 ≡ x y (mod n).

Алгебра Zn = < Z n , +, · > является коммутативным кольцом, которое на-

зывается кольцом вычетов по модулю n.

Пример 4.19. Рассмотрим кольцо Z2 = < Z 2 , +, · >, где Z2 = {0; 1}. Приведем таблицы Кэли операций сложения и умножения в кольце Z2, где для простоты вместо 0 и 1 будем писать 0 и 1 :

Кольцо Z2 коммутативно, нулем кольца является класс вычетов 0 , который отличен от единицы кольца – класса вычетов 1. Кроме того, единственный ненулевой элемент 1 кольца Z2 имеет обратный к нему – этот же класс 1, так как 1 1=1. Следовательно, Z2 = < Z 2 , +, · > является полем. Оно имеет большое

значение для приложений. Следующая теорема говорит о том, что существует много конечных по-

лей.

Теорема 4.4. Кольцо Zn является полем тогда и только тогда, когда n – простое число.

4.6. Булевы алгебры

Рассмотрим понятие булевой алгебры, имеющее большое число приложений в программировании и вычислительной технике. Оно возникло в трудах ирландского математика и логика Джорджа Буля (1815 – 1864) как аппарат символической логики.

Определение 4.29. Алгебра А = < А, , , > типа (2, 2, 1) называется булевой алгеброй, если выполняются следующие условия (аксиомы):

А1. Существуют различные элементы e1, e2 А, являющиеся нейтральными относительно бинарных операций , соответственно, то есть

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

А2. Операции , ассоциативны, то есть

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

A3. Операции , коммутативны, то есть

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

66