Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

62
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
Пусть A
i
= hA
i
; Σi, i ∈ I, — некоторые алгебры сигнатуры Σ. Декарто-
вым произведением алгебр A
i
, i ∈ I, называется алгебра
Y
i∈I
A
i
­
*
Y
i∈I
A
i
; Σ
+
,
в которой функциональные символы F
(n)
∈ Σ интерпретируются по сле- дующему правилу:
для любых функций f
1
, . . . , f
n
∈
Q
i∈I
A
i
полагаем
F (f
1
, . . . , f
n
) ­ f , где f (i) = F
A
i
(f
1
(i), . . . , f
n
(i)) для любого i ∈ I. Если
I = {1, 2, . . . , n}, то декартово произведение алгебр
Q
i∈I
A
i
будем, как и для множеств, обозначать через A
1
× A
2
× . . . × A
n
Пример 2.5.1. Для алгебр A
1
= hA
1
; +
1
i, A
2
= hA
2
; +
2
i операция +
декартова произведения A
1
× A
2
= hA
1
× A
2
; +i задается соотношением
(a
1
, a
2
) + (a
0
1
, a
0
2
) = (a
1
+
1
a
0
1
, a
2
+
2
a
0
2
). ¤
Пусть t
1
, t
2
— термы сигнатуры Σ. Запись t
1
≈ t
2
называется тожде-
ством сигнатуры Σ. Эта запись означает, что любые значения, вычислен- ные по терму t
1
, совпадают с соответствующими значениями, вычисленными по терму t
2
Пример 2.5.2. Если t
1
= x + y, t
2
= y + x — термы сигнатуры Σ = {+},
то тождество x + y ≈ y + x означает, что для символа + выполняется закон коммутативности. ¤
Класс K алгебр сигнатуры Σ называется многообразием, если существует множество тождеств T = {t
j
1
≈ t
j
2
| j ∈ J} сигнатуры Σ такое, что алгеб- ра сигнатуры Σ принадлежит классу K тогда и только тогда, когда в ней выполняются все тождества из множества T .
Пример 2.5.3. Множеством тождеств {x · (y · z) ≈ (x · y) · z, x · e ≈ x,
e · x ≈ x} сигнатуры Σ = {·
(2)
, e
(0)
} определяется многообразие, состоящее из всех моноидов. ¤
Теорема 2.5.1 (теорема Биркгофа). Непустой изоморфно замкнутый
класс алгебр K сигнатуры Σ тогда и только тогда является многообрази-
ем, когда K замкнут относительно подалгебр, фактор-алгебр и декартовых
произведений, т. е. класс K вместе с каждой алгеброй содержит любую ее
подалгебру, фактор-алгебру, а также вместе с любым семейством алгебр
содержит их декартово произведение. ¤

2.6. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ
63
§ 2.6.
Решетки и булевы алгебры
Следующей нашей целью является определение и изучение понятия бу- левой алгебры, но сначала рассмотрим более общее понятие — понятие ре- шетки.
Решеткой называется ч.у.м. A = hA; 6i, в котором каждая пара эле- ментов имеет супремум и инфимум. Для заданных элементов x, y ∈ A эле- мент inf{x, y} называется пересечением элементов x и y (обозначается x∧y),
а sup{x, y} называется объединением элементов x и y (обозначается x ∨ y).
Заметим, что если в системе A введены операции ∧ и ∨, то от- ношение 6 можно по этим операциям восстановить следующим образом:
x 6 y ⇔ x ∧ y = x, а также x 6 y ⇔ x ∨ y = y.
Наименьший (наибольший) элемент решетки, если он существует, назы- вается нулем (единицей). Обозначаются эти элементы соответственно через 0 и 1. В конечных решетках всегда имеются нуль и единица.
Пример 2.6.1. 1. Любое линейно упорядоченное множество является решеткой.
2. Рассмотрим ч.у.м. A = h{a, b, c, d, e}; 6i, в котором a < b, a < c,
a < d, b < e, c < e, d < e, а элементы b, c, d попарно несравнимы. Система A
образует решетку, показанную на рис. 2.2. В этой решетке a = 0, e = 1.
3. Если |A| > 1, то ч.у.м. hA; id
A
i не является решет-
•
•
•
•
•
¡
¡
¡
¡
@
@
@
@
¡
¡
¡
¡
@
@
@
@
a
e
c
b
d
Рис. 2.2
кой, поскольку для любых различных элементов x и y
не определены операции inf{x, y} и sup{x, y} по отно- шению id
A
. ¤
Определим
решетку
подсистем
системы
B = hB; Σi, содержащих непустое множество X ⊆ B.
Рассмотрим множество L(B, X) ­ {A | A = hA; Σi ⊆ B
и X ⊆ A} и зададим на нем частичный порядок 6
по следующему правилу: A
1 6 A
2
⇔ A
1
⊆ A
2
. Пара
hL(B, X); 6i образует решетку подсистем. В этой решетке для любых систем A
1
= hA
1
; Σi, A
2
= hA
2
; Σi из L(B, X) пересечение A
1
∧ A
2
есть подсистема hA
1
∩ A
2
; Σi, а объединение A
1
∨ A
2
— подсистема, порожденная множеством A
1
∪ A
2
: B(A
1
∪ A
2
).
Пример 2.6.2. Рассмотрим линейное пространство V
и множе- ство L(V, {0}) подпространств пространства V . Система hL(V, {0}); 6i,
где V
1 6 V
2
⇔ V
1
— подпространство V
2
, образует решетку подпространств,
в которой V
1
∧ V
2
= V
1
∩ V
2
, V
1
∨ V
2
= L(V
1
∪ V
2
). ¤

64
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
Пусть A = hA; Σi — алгебра, Con A ­ {θ | θ — конгруэнция на A}.
На множестве конгруэнций Con A зададим отношение 6 по следующему правилу: θ
1 6 θ
2
⇔ для любых элементов a, b ∈ A из условия a θ
1
b выте- кает a θ
2
b. Это означает, что каждый θ
2
-класс состоит из θ
1
-классов. Систе- ма hCon A; 6i образует решетку конгруэнций. В этой решетке пересечение
θ
1
∧ θ
2
конгруэнций θ
1
и θ
2
удовлетворяет следующему условию: для любых
a, b ∈ A тогда и только тогда a (θ
1
∧ θ
2
) b, когда a θ
1
b и a θ
2
b. Объединение
θ
1
∨ θ
2
конгруэнций θ
1
и θ
2
определяется следующим отношением: для лю- бых a, b ∈ A тогда и только тогда a (θ
1
∨ θ
2
) b, когда существуют такие
c
1
, c
2
, . . . , c
n
∈ A, что c
1
= a, c
n
= b, и справедливо c
i
θ
1
c
i+1
или c
i
θ
2
c
i+1
для любого i = 1, . . . , n − 1.
Решетка конгруэнций имеет нулевую конгруэнцию
•
•
•
•
•
¡
¡
¡
J
J
J
J
J
­
­
­
­­
@
@
@
Рис. 2.3
0
A
­ {(a, a) | a ∈ A} и единичную конгруэнцию 1
A
­ A
2
Решетка A = hA; , 6i называется дистрибутивной, ес- ли она подчиняется дистрибутивным законам
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z),
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
для всех x, y, z ∈ A.
Не все решетки являются дистрибутивными. Решетка M
3
, изображенная на рис. 2.2, не дистрибутивна, поскольку b ∧ (d ∨ c) = b ∧ e = b, тогда как
(b ∧ d) ∨ (b ∧ c) = a ∨ a = a. Недистрибутивной является также решетка P
5
,
изображенная на рис. 2.3.
Теорема 2.6.1. Решетка A = hA; , 6i дистрибутивна тогда и только
тогда, когда A не имеет подрешеток, изоморфных M
3
или P
5
. ¤
Дистрибутивная решетка A = hA; 6i называется булевой, если A имеет нуль 0, единицу 1, 0 6= 1 и для любого элемента x ∈ A найдется элемент x
(называемый дополнением элемента x) такой, что x ∨ x = 1 и x ∧ x = 0.
Предложение 2.6.2. Если A — булева решетка, то для любого элемен-
та x дополнение x единственно.
Доказательство. Предположим, что элемент x имеет два дополне- ния — y и z, т. е. x ∨ y = 1, x ∧ y = 0, x ∨ z = 1, x ∧ z = 0. Используя законы дистрибутивности, получаем, что элементы y ∨ z и y ∧ z также являются до- полнениями к x, т. е. x∨(y∨z) = 1, x∧(y∨z) = 0, x∨(y∧z) = 1, x∧(y∧z) = 0.

2.6. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ
65
При этом из y 6= z следует, что 0 < (y ∧ z) < (y ∨ z) < 1. Отсюда получаем,
что подрешетка решетки A с носителем {0, y ∧ z, y ∨ z, x, 1} является ре- шеткой P
5
, что противоречит дистрибутивности решетки A. Следовательно,
двух различных дополнений элемента x не существует. ¤
Таким образом, булеву решетку можно представить в виде алгеб- ры B = hB; ∧, ∨, , 0, 1i с двумя двухместными операциями пересечения ∧
и объединения ∨, одноместной операцией дополнения (x 7→ x) и двумя кон- стантами 0 и 1. Алгебра B, соответствующая булевой решетке, называется
булевой алгеброй.
Пример 2.6.3. 1. Если на множестве {0, 1} задать линейный поря- док с условием 0 < 1, то получим двухэлементную булеву алгебру
h{0, 1}; ∧, ∨, , 0, 1i.
2. Рассмотрим множество A = {0, a, b, 1} и зада-
•
•
•
•
¡
¡
¡
@
@
@
¡
¡
¡
@
@
@
0 1
a = b
b = a
Рис. 2.4
дим частичный порядок 6 на A следующим образом:
0 < a, 0 < b, a < 1, b < 1, а элементы a и b несрав- нимы (рис. 2.4). Система hA; 6i является булевой ре- шеткой, в которой a = b, b = a.
3. Алгебра Кантора hP(U); ∩, ∪, , ∅, U i является булевой алгеброй. ¤
Оказывается, что основные свойства операций ∩,
∪ и из § 1.1 выполняются в любой булевой алгебре.
Теорема 2.6.3. Если B = hB; ∧, ∨, , 0, 1i — булева алгебра, то в B вы-
полняются следующие законы для любых x, y, z ∈ B:
1) ассоциативность операций ∨ и ∧:
x ∨ (y ∨ z) = (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z;
2) коммутативность операций ∨ и ∧:
x ∨ y = y ∨ x, x ∧ y = y ∧ x;
3) законы идемпотентности
x ∨ x = x, x ∧ x = x;
4) законы дистрибутивности
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z), x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z);

66
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
5) законы поглощения
x ∨ (x ∧ y) = x, x ∧ (x ∨ y) = x;
6) законы де Моргана
x ∨ y = x ∧ y, x ∧ y = x ∨ y;
7) законы нуля и единицы
x ∨ 0 = x, x ∧ 0 = 0, x ∨ 1 = 1, x ∧ 1 = x,
x ∨ x = 1, x ∧ x = 0, 0 6= 1;
8) закон двойного отрицания
x = x. ¤
В следующей теореме описываются все конечные булевы алгебры с точ- ностью до изоморфизма.
Теорема 2.6.4 (теорема Стоуна). Любая конечная булева алгебра изо-
морфна некоторой алгебре Кантора.
Доказательство. Пусть B = hB; ∧, ∨, , 0, 1i — конечная булева алгеб- ра. Обозначим через A множество всех атомов алгебры B, т. е. элементов
a из B, для которых 0 ≺ a. Покажем, что B ' hP(A); ⊆i. Рассмотрим отоб- ражение ϕ: B → P(A), действующее на каждом элементе b ∈ B по правилу:
ϕ(b) =
(
{a | a ∈ A, a 6 b}, если b 6= 0,
∅,
если b = 0.
Заметим, что каждый ненулевой элемент b конечной булевой алгебры представляется в виде объединения u ­ ∨ϕ(b) всех элементов из ϕ(b). Дей- ствительно, по определению u 6 b. Если u 6= b, то b = u∨ (u∧ b), где u∧ b 6= 0.
По условию найдется атом a
0
, для которого a
0
6 u ∧ b 6 b. Но тогда a
0
∈ ϕ(b),
откуда a
0
6 u ∧ u = 0. Полученное противоречие показывает, что ∨ϕ(b) = b.
Поскольку последнее равенство имеет место для любого ненулевого эле- мента b из B, отображение ϕ биективно. Действительно, разным ненуле- вым элементам b
1
и b
2
не могут соответствовать одинаковые множества ато- мов ϕ(b
1
) и ϕ(b
2
). С другой стороны, каждому непустому множеству атомов
A
0
⊆ A соответствует элемент b = ∨A
0
, для которого ϕ(b) = A
0

2.6. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ
67
Для завершения доказательства осталось заметить, что для любых эле- ментов b
1
, b
2
∈ B выполняется b
1 6 b
2
⇔ ϕ(b
1
) ⊆ ϕ(b
2
). ¤
Так как для любого множества U мощность множества P(U) равна 2
|U |
,
то из теоремы Стоуна вытекает
Следствие 2.6.5. Любые две конечные булевы алгебры, имеющие оди-
наковое число элементов, изоморфны. Число элементов конечной булевой
алгебры равно 2
n
для некоторого n ∈ ω \ {0}. ¤
Таким образом, конечная булева алгебра определяется однозначно, с точ- ностью до изоморфизма, числом своих элементов.
Аналогично примеру
2.2.2
булевы алгебры
hB; ∧, ∨, , 0, 1i
и hB; ∨, ∧, , 1, 0i изоморфны посредством изоморфизма ϕ: B → B, в кото- ром ϕ(x) = x. На этом основан следующий принцип двойственности для
булевых алгебр: если в справедливом утверждении о булевых алгебрах, ка- сающемся отношения 6 и операций ∧, ∨, , 0, 1, всюду заменить 6 на >,
∧ — на ∨, ∨ — на ∧, 0 — на 1, 1 — на 0, то получится также справедливое утверждение. Образованное таким образом утверждение называется двой-
ственным к исходному.
Пример 2.6.4. Закон де Моргана x ∧ y = x ∨ y является двойственным по отношению к закону де Моргана x ∨ y = x∧y, а закон x∧x = 0 — к закону
x ∨ x = 1. ¤
Остановимся на связи булевых алгебр с кольцами. Кольцо hR; +, ·i назы- вается булевым, если a
2
= a для всех a ∈ R.
Предложение 2.6.6. Булево кольцо hR; +, ·i коммутативно, и a+a = 0
для всех элементов a ∈ R.
Доказательство. Во-первых,
a + a = (a + a)
2
= a
2
+ a
2
+ a
2
+ a
2
= a + a + a + a,
откуда a + a = 0, т. е. a = −a. Во-вторых,
a + b = (a + b)
2
= a
2
+ ab + ba + b
2
= a + b + ab + ba.
Отсюда ab + ba = 0. Тогда ab = ab + (ba + ba) = (ab + ba) + ba = ba. ¤

68
Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ
Напомним, что единицей кольца