Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
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. 68 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ При этом из 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 0 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); 2.6. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ 69 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 70 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Для завершения доказательства осталось заметить, что для любых эле- ментов 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. ¤ 2.7. ИДЕАЛЫ И ФИЛЬТРЫ БУЛЕВОЙ АЛГЕБРЫ 71 Напомним, что единицей кольца R называется такой элемент e, что a · e = e · a = a для всех a ∈ R. Пусть B = hB; ∧, ∨, , 0, 1i — булева алгебра. Определим операции коль- цевых сложения и умножения на B по следующим правилам: x ⊕ y (x ∧ y) ∨ (x ∧ y), x ¯ y x ∧ y для всех x, y ∈ B. Операция ⊕ соответствует кольцевой сумме множеств, а операция ¯ — пересечению множеств (см. § 1.1). Теорема 2.6.7. Система hB; ⊕, ¯i является булевым кольцом с едини- цей 1. ¤ Имея булево кольцо с единицей hB; ⊕, ¯i, можно однозначно восстано- вить операции ∧, ∨, по следующим правилам: x ∧ y = x ¯ y, x ∨ y = x ⊕ y ⊕ (x ¯ y), x = 1 ⊕ x. § 2.7. Идеалы и фильтры булевой алгебры Пусть B = hB; ∧, ∨, , 0, 1i — булева алгебра. Множество I ⊆ B называется идеалом, если выполняются следующие условия: 1) из a, b ∈ I следует a ∨ b ∈ I; 2) если b ∈ I, a ∈ B и a 6 b, то a ∈ I. Таким образом, идеалы замкнуты относительно операции ∨ и взятия элементов, не превосходящих данного элемента идеала. Заметим, что если I 6= ∅, то 0 ∈ I. Идеал I называется главным, если существует элемент c ∈ I такой, что I = {a ∈ B | a 6 c}. Пример 2.7.1. 1. Рассмотрим алгебру Кантора hP(U); ∩, ∪, , 0, 1i и выберем произвольное подмножество C ⊆ U. Тогда множество I = {A | A ⊆ C} образует главный идеал. Действительно, если A, B ∈ I, то A, B ⊆ C, отсюда A ∪ B ⊆ C и, следо- вательно, A ∪ B ∈ I. Если же B ⊆ C и A ⊆ B, то в силу транзитивности отношения ⊆ имеем A ⊆ C, т. е. A ∈ I. 2. Если множество U бесконечно, то в алгебре Кантора идеал конечных множеств I = {A | A ⊆ U, A — конечное множество} является неглавным, 72 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ поскольку для любого множества C ∈ I найдется элемент x ∈ U \ C, т. е. {x} ∩ C = ∅, а {x} ∈ I. ¤ Понятие фильтра является двойственным к понятию идеала. Множество F ⊆ B называется фильтром, если выполняются следующие условия: 1) из a, b ∈ F следует a ∧ b ∈ F ; 2) если b ∈ F , a ∈ B и b 6 a, то a ∈ F . Фильтр F называется главным, если найдется элемент c ∈ F такой, что F = {a ∈ B | a > c}. Пример 2.7.2. 1. В алгебре Кантора P(U) для любого C ⊆ U множество F = {A | A ∈ P(U) и A ⊇ C} является главным фильтром. 2. Пусть U — бесконечное множество. Подмножество A ⊆ U называется коконечным, если множество A конечно. В алгебре Кантора P(U) фильтр F = {A | A ⊆ U, A — коконечное множество} является неглавным. Фильтр F называется фильтром Фреше на множестве U. ¤ Теорема 2.7.1. Если B — конечная булева алгебра, то в B все идеалы и фильтры являются главными. ¤ Если I — идеал булевой алгебры B, то множество I = {a | a ∈ I} является фильтром, называемым двойственным к идеалу I. Теорема 2.7.2. Отображение : I 7→ I является биекцией между мно- жеством идеалов и множеством фильтров булевой алгебры. ¤ Отметим связь идеалов и фильтров булевой алгебры с ее конгруэнциями. Теорема 2.7.3. Пусть I — идеал булевой алгебры B, ∅ 6= I ( B. Тогда бинарное отношение (I), определяемое по правилу a (I) b ⇔ a ⊕ b ∈ I, является конгруэнцией булевой алгебры B. Обратно, если имеется нееди- ничная конгруэнция θ булевой алгебры B, то класс эквивалентности θ(0) есть идеал, а θ(1) — фильтр булевой алгебры B. ¤ Таким образом, существуют, с одной стороны, биекция между множе- ством идеалов и множеством конгруэнций алгебры B, а, с другой стороны, по теореме 2.7.2 — биекция между множеством фильтров и множеством кон- груэнций булевой алгебры B. 2.8. АЛГЕБРЫ ОТНОШЕНИЯ И РЕЛЯЦИОННЫЕ АЛГЕБРЫ 73 § 2.8. Алгебры отношений и реляционные алгебры Важным классом алгебраических систем являются алгебры отношений и их расширения — реляционные алгебры. Рассмотрим алгебру отношений, носителем которой является множество отношений R = {P 1 , P 2 , . . . , P m , . . .}, а сигнатура Σ состоит из символов ча- стичных двухместных операций объединения ∪, пересечения ∩, разности \ и декартова произведения × отношений. Отношения P i и P j называются совместимыми, если P i , P j ⊆ A n для некоторого множества A и числа n ∈ ω. Объединением P i ∪ P j двух совместимых отношений P i и P j называется множество всех кортежей, каждый из которых принадлежит хотя бы одному из этих отношений: P i ∪ P j = {X | X ∈ P i или X ∈ P j }. Пересечением P i ∩ P j двух совместимых отношений P i и P j называется множество всех кортежей, принадлежащих как отношению P i , так и отношению P j : P i ∩ P j = {X | X ∈ P i и X ∈ P j }. Разностью P i \ P j двух совместимых отношений P i и P j называется множество всех кортежей, принадлежащих отношению P i и не принадлежащих отношению P j : P i \ P j = {X | X ∈ P i и X / ∈ P j }. Пример 2.8.1. Если P = {(a, b, d), (b, c, e)}, Q = {(a, b, d), (b, d, e)}, то P ∪ Q = {(a, b, d), (b, c, e), (b, d, e)}, P ∩ Q = {(a, b, d)}, P \ Q = {(b, c, e)}. ¤ Декартовым произведением P i × P j двух отношений P i и P j называется множество всех кортежей Z таких, что Z — конкатенация Z = XˆY кортежей X ∈ P i и Y ∈ P j , где XˆY = (x 1 , . . . , x r , y 1 , . . . , y s ), если X = (x 1 , . . . , x r ), Y = (y 1 , . . . , y s ). Итак, P i × P j = {XˆY | X ∈ P i , Y ∈ P j }. Пример 2.8.2. Если P = {(a, b), (b, c)}, Q = {(b, c, a), (c, a, a)}, то P × Q = {(a, b, b, c, a), (a, b, c, a, a), (b, c, b, c, a), (b, c, c, a, a)}. ¤ Алгебры отношений находят применение при формализации реальных объектов. Рассмотрим, как используется алгебра отношений при создании информационного обеспечения — разработке реляционной базы данных. Основой построения реляционной базы данных является двумерная табли- ца, каждый i-й столбец которой соответствует i-му домену (если n-местное отношение R n содержится в D 1 × D 2 × . . . D n , то множество |