Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
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 — конечное множество} является неглавным, 2.7. ИДЕАЛЫ И ФИЛЬТРЫ БУЛЕВОЙ АЛГЕБРЫ 69 поскольку для любого множества 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. 70 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ § 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 , то множество D i называется i-м доменом отношения R n , где i = 1, . . . , n), строка — кортежу значений доменов, находящихся в отношении R n 2.8. АЛГЕБРЫ ОТНОШЕНИЯ И РЕЛЯЦИОННЫЕ АЛГЕБРЫ 71 Таблица 2.1 R 4 D 1 D 2 D 3 D 4 1 A-1 Информатика 10 января Ауд. 320 2 A-2 Физика 10 января Ауд. 324 3 A-2 Анализ 15 января Ауд. 324 4 A-1 Физика 16 января Ауд. 320 5 A-1 Анализ 21 января Ауд. 324 6 A-2 Информатика 21 января Ауд. 320 Пример 2.8.3. Рассмотрим 4-местное отношение R 4 (расписание экза- менов) (табл. 2.1). Отношение R 4 является подмножеством декартова произведения D 1 × D 2 × D 3 × D 4 , и поэтому каждое из множеств D i является доменом: • домен D 1 (группа) содержит значения A-1, A-2: D 1 = {A-1, A-2}; • домен D 2 (дисциплина) — D 2 = {Информатика, Физика, Анализ}; • домен D 3 (дата) — D 3 = {10 янв., 15 янв., 16 янв., 21 янв.}; • домен D 4 (аудитория) — D 4 = {Ауд. 320, Ауд. 324}. Порядок столбцов в таблице фиксирован, строки в общем случае мо- гут располагаться произвольно. Цифры первого столбца 1, 2, . . . , 6 являются идентификаторами отношения R 4 . ¤ Итак, каждому отношению можно поставить в соответствие таблицу. Для преобразования отношений определим реляционную алгебру. Но- ситель реляционной алгебры представляет собой множество отношений R, а набор операций кроме введенных операций ∪, ∩, \, × включает специаль- ные операции над отношениями: выбор, проекцию и соединение. Операция выбора представляет собой процедуру построения “горизон- тального” подмножества отношения, т. е. подмножества кортежей, обладаю- щих заданным свойством. Пример 2.8.4. С помощью операции выбора построим из отношения R 4 (расписание экзаменов) отношение R 0 4 (расписание экзаменов по физике). Результатом операции выбора являются строки, в которых домен D 2 пред- ставлен значением “Физика”, это 2-я и 4-я строки (табл. 2.2). ¤ 72 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Таблица 2.2 R 0 4 D 1 D 2 D 3 D 4 2 A-2 Физика 10 января Ауд. 324 4 A-1 Физика 16 января Ауд. 320 Таблица 2.3 π R 4 2,3 D 2 D 3 1 Информатика 10 января 2 Физика 10 января 3 Анализ 15 января 4 Физика 16 января 5 Анализ 21 января 6 Информатика 21 января Результатом операции проекции отношения R n ⊆ A 1 × A 2 × . . . × A n на A i 1 , A i 2 , . . . , A i m , где {i 1 , . . . , i m } ⊆ {1, 2, . . . , n}, i j < i k при j < k, назы- вается множество π R n i 1 ,i 2 ,...,i m {(a i 1 , a i 2 , . . . , a i m ) | (a 1 , a 2 , . . . , a n ) ∈ R n }. Например, π R n 1 {a 1 | (a 1 , a 2 , . . . , a n ) ∈ R n }. Операция проекции определяет построение “вертикального” подмноже- ства отношения, т. е. из кортежей удаляются координаты, соответствующие невыделенным доменам. Пример 2.8.5. Проекция π R 4 2,3 отношения R 4 из примера 2.8.3 определяет множество пар, каждая из которых содержит название дисциплины и дату (табл. 2.3). ¤ Операция соединения по двум таблицам, имеющим общий домен, позво- ляет построить одну таблицу, каждая строка которой образуется соединени- ем двух строк исходных таблиц. Из заданных таблиц берут строки, содер- 2.8. АЛГЕБРЫ ОТНОШЕНИЯ И РЕЛЯЦИОННЫЕ АЛГЕБРЫ 73 Таблица 2.4 R 4 D 1 D 2 D 3 D 4 1 A-1 Информатика 10 января Ауд. 320 2 A-2 Физика 10 января Ауд. 324 Таблица 2.5 R 0 4 D 1 D 2 D 3 D 4 1 A-2 Анализ 15 января Ауд. 324 2 A-1 Физика 16 января Ауд. 320 жащие одно и то же значение общего домена; общему домену ставится в соответствие один столбец. Пример 2.8.6. Найдем по двум заданным таблицам (табл. 2.4, 2.5) результат соединения по домену D 1 (табл. 2.6). ¤ В примере 2.8.6 кортежи соединяются по условию равенства со- ответствующих координат: соединяются кортежи a = (a 1 , . . . , a i , . . . , a n ) и b = (b 1 , . . . , b i , . . . , b n ), когда a i = b i . В зависимости от практических по- требностей можно определять соединения по другим правилам, например, соединять кортежи a и b при совпадении нескольких соответствующих ко- ординат. Таблица 2.6 R 7 D 1 D 2 D 3 D 4 D 0 2 D 0 3 D 0 4 1 A-1 Информатика 10 янв. Ауд.320 Физика 16 янв. Ауд.320 2 A-2 Физика 10 янв. Ауд.324 Анализ 15 янв. Ауд.324 74 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Задачи и упражнения 1. Определены ли на множествах N, Z, 2Z {2n | n ∈ Z}, 2Z + 1 {2n + 1 | n ∈ Z}, Q, Q \ {0}, R, R + {a ∈ R | a > 0}, R \ {0} и C следующие операции: а) (a, b) 7→ a + b; б) (a, b) 7→ a − b; в) (a, b) 7→ a · b; г) (a, b) 7→ a b ; д) (a, b) 7→ a+b 2 ; е) (a, b) 7→ √ ab; ж) (a, b) 7→ ab − ba; з) (a, b) 7→ min{a, b}; и) (a, b) 7→ max{a, b}; к) (a, b) 7→ a b ; л) (a, b) 7→ a? 2. Установить, образуют ли алгебры следующие системы: а) hω; +, −i; б) hZ; :, ·i; в) hR; ·, −, 1 − 2 . ıi. 3. Обозначим через F множество функций, действующих на множестве A. Образует ли система hF; ◦i: а) полугруппу, б) моноид, в) группу? 4. Построить изоморфизм систем h{1, 2, 3, 4}; {(1, 3), (1, 4), (4, 2), (3, 2)}i и h{a, b, c, d}; {(b, a), (c, b), (c, d), (d, a)}i. Построить все гомоморфные образы указанных систем. 5. Построить всевозможные попарно неизоморфные группы с двух-, трех- и че- тырехэлементными носителями. 6. Рассмотрим алгебру A = h{a, b, c, d}; ·i, определенную следующей таблицей Кэли: · a b c d a a a b a b c d a b c a c d d d d a d a Имеет ли алгебра A подалгебру с носителем: а) {a, b, c}; б) {a}; в) {a, d}? ЗАДАЧИ И УПРАЖНЕНИЯ 75 7. Являются ли термами сигнатуры Σ = {f (1) , g (2) , h (3) } следующие выраже- ния: а) f (g(x, y)); б) g(f (x), h(x, y, z)); в) f (g(x), h(x, y, z))? 8. Указать алгоритм построения всех термов сигнатуры Σ от переменной x, если: а) Σ = {f (1) } и б) Σ = {g (2) }. 9. Пусть X 1 = {0}, X 2 = {1}, X 3 = {2}, X 4 = {2, 3}, X 5 = {−3}, X 6 = {−5}, X 7 = {4}, X 8 = {7}, X 9 = {3, 9}, X 10 = {−3, 9}, X 11 = {2, 16}, X 12 = {−2, 7}, X 13 = {−8, 6}, X 14 = {−3, 1, 4}, X 15 = {4, 6, 10}, X 16 = {−6, 9, 12}, X 17 = © 1 2 ª , X 18 = © 3 4 ª , X 19 = © 1 2 , 2 ª , X 20 = © 1 4 , 3 ª , X 21 = |