Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
, . . . , n} — конечное множество индексов, де- картово произведение Y i∈I A i = {f | f : I → n ∪ i=1 A i , где f (1) ∈ A 1 , . . . , f (n) ∈ A n } можно взаимно однозначно рассматривать как множество n Y i=1 A i = {(f (1), . . . , f (n)) | f : I → n ∪ i=1 A i , где f (1) ∈ A 1 , . . . , f (n) ∈ A n }. Таким образом, данное определение согласуется с введенным ранее опреде- лением декартова произведения конечного числа множеств. 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. ¤ |