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

Рассматриваются алгебры с двумя бинарными операциями: , которые условно называются "сложением" и "умножением".

1. Кольца.

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

Таким образом, кольцо обладает, по определению, следующими свойствами:

1. - сложение ассоциативно.

2. - существует нуль.

3. - существует обратный элемент

4. - сложение коммутативно, т.е. кольцо – абелева группа по сложению.

5. - умножение ассоциативно, т.е. кольцо полугруппа по умножению.

6. - умножение дистрибутивно слева и справа.

7. - если умножение коммутативно, то кольцо коммутативное

8. - если существует единица, то кольцо называется кольцом с единицей. Кольцо с единицей – моноид по умножению.

Пример 1.

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

Пример 2.

В частности, машинная арифметика целых чисел - коммутативное кольцо с единицей.

Пример 3.

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

Теорема: В кольце выполняются следующие соотношения:

1. 

2. 

3. 

Доказательство:

1.

2.

3.

Если в кольце существует и такие, что , то называется левым, а y – правым делителем нуля.

Пример4: В машинной арифметике целых чисел имеем 256128=0.

2. Тело и поле

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

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

Таким образом, поле - алгебра с такими операциями и , что

1. (ab)c=a(bc) – сложение ассоциативно;

2. - существует нуль;

3. - существует обратный элемент по сложению;

4. - сложение коммутативно (абелева группа по сложению);

5. - умножение ассоциативно;

6. - существует единица;

7. - существует обратный элемент по умножению;

8. - умножение коммутативно, т.е. поле – абелева группа по умножению.

9. - умножение дистрибутивно относительно сложения.

Примеры:

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

2. Алгебра - поле рациональных чисел.

Схема образования некоторых понятий для алгебры с двумя операциями показана на рис.13.

Теорема: В поле выполняются следующие соотношения:

1. 

2. 

3. 

4. 

Доказательство:

1. 

2. 

3. 

4. и и

и

Алгебра

рис.13

1.11.6.Решетки

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

Определение. Решетка - это любая алгебра с двумя бинарными операциями и : такими, что выполнены следующие условия (аксиомы решетки):

1. Идемпотентность: ;

2. Коммутативность: ;

3. Ассоциативность:

4. Поглощение:

Решетка называется дистрибутивной, если она подчиняется дистрибутивным законам:

для всех a, b, c M.

Замечание. Если на множестве М введены операции и , то отношение можно установить следующим образом: , а так же .

Таким образом, можно сказать, что решетка – это алгебра

< М, ≤, , > с одним бинарным отношением (≤) и двумя бинарными операциями ( и ).

Примеры:

1. Любое конечное линейноупорядоченное множество является решеткой.

2. Семейство подмножеств Р(А) множества А частично упорядочено отношениям ≤, поэтому < Р(А), ≤ , , > - решетка, элементами которой являются множества, а операции – обычные – теоретико-множественные операции объединения и пересечения.

3. Рассмотрим частично упорядоченное множество , в котором a<b, a<c, a<d; b<e, c<e, d<e, а элементы b, c, d попарно не сравнимы. Система U обращает решетку, показанную на рисунке 14. (М₃)

Не все решетки являются дистрибутивными. Решетка М₃ не дистрибутивна, так как , тогда как .

Не дистрибутивна так же решетка P₅ (Рис.15)

Теорема: Решетка <M, , > дистрибутивна тогда и только тогда, когда она не имеет подрешеток, изоморфных М₃ и Р₅.

Ограниченные решетки

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

О бъединение всех элементов полной решетки – это максимальный элемент решетки, называемый единицей решетки (или верхней гранью решетки):

Рис.14. Рис.15.

Объединение всех элементов полной решетки – это максимальный элемент решетки, называемый единицей решетки (или верхней гранью решетки):

Пересечение всех элементов полной решетки – это минимальный элемент решетки, называемый нулем решетки (или нижней гранью решетки):

В конечных решетках всегда имеются нуль и единица.

Пример: в решетке М₃ (рис.11) а = 0; е =1.

Решетка с верхней и нижней гранью называется ограниченной.

Теорема: Если нижняя (верхняя) грань существует, то она единственная.

Доказательство: Пусть имеется два нуля 0 и 0^′ решетки. Тогда и . Следовательно, 0 = 0^|.

Теорема: <=> .

Доказательство: Пусть . Тогда . <= Пусть . Тогда .

Следствие: <=> ; <=> .

Решетка с дополнением

В ограниченной решетке элемент (или а^|) называется дополнением элемента а, если и .

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

Если решетка обладает нулем и такой унарной операцией , определяющей отрицание, что

,

, ,

,

то она называется решеткой с дополнением.

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

Замечание: упорядоченное множество, двойственное решетке, так же является решеткой, в которой пересечение и объединение меняются местами.