Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
D i называется i-м доменом отношения R n , где i = 1, . . . , n), строка — кортежу значений доменов, находящихся в отношении R n 74 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Таблица 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). ¤ 2.8. АЛГЕБРЫ ОТНОШЕНИЯ И РЕЛЯЦИОННЫЕ АЛГЕБРЫ 75 Таблица 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). ¤ Операция соединения по двум таблицам, имеющим общий домен, позво- ляет построить одну таблицу, каждая строка которой образуется соединени- ем двух строк исходных таблиц. Из заданных таблиц берут строки, содер- 76 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Таблица 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 ЗАДАЧИ И УПРАЖНЕНИЯ 77 Задачи и упражнения 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}? 78 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ 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 = { √ 2 + i √ 2}, X 22 = {z 1 , z 2 } (z 1 , z 2 ∈ Z), X 23 = Z, X 24 = Z ∪ { . ı}, X 25 = R∪ { . ı}; B 1 = hω; +i, B 2 = hZ; +i, B 3 = hZ; +, −i, B 4 = hZ; ·i, B 5 = hQ; +i, B 6 = hQ; ·i, B 7 = hQ \ {0}; ·, :i, B 8 = hR; 3 √ i, B 9 = hC; +i, B 10 = hC; ·i, B 11 = hC; ·, 2i, B 12 = hC; +, ·i. Для множеств X i ⊆ B j построить подсистемы B j (X i ), i = 1, . . . , 25, j = 1 . . . , 12. 10. Рассмотрим алгебру A = h{a, b, c, d, e}; ·i, определенную следующей таблицей Кэли: · a b c d e a c d a b e b d c b b e c a a b a c d b a a b d e a b e e c Какое из следующих разбиений образует конгруэнцию на алгебре A: а) {{a, b, c}, {d, e}}; б) {{a, b}, {c, d}, {e}}? Построить фактор-алгебру алгебры A по найденной конгруэнции. 11. Доказать, что в решетке максимальный элемент является наибольшим, а минимальный — наименьшим. 12. Построить пример решетки с наибольшим элементом, но без наименьшего. 13. Построить булеву алгебру подмножеств трехэлементного (четырехэлемент- ного) множества. 14. Для терма x ∨ (y ∧ z) булевой алгебры найти соответствующий терм в буле- вом кольце. Глава 3 ЧИСЛОВЫЕ СИСТЕМЫ § 3.1. Бесконечные числовые системы 1. Системы Дедекинда—Пеано Как отмечалось в § 1.3, множество натуральных чисел можно определять двояко: 1) исходя из ∅ последовательно выражать натуральные числа как мно- жества, состоящие из предыдущих натуральных чисел; 2) задавать алгебраическую систему N = hN; 0, 0 i, удовлетворяющую си- стеме аксиом Дедекинда—Пеано. В дальнейшем мы будем рассматривать второй подход и называть такие системы системами Дедекинда—Пеано. Теорема 3.1.1 (теорема Дедекинда—Пеано). Любые две системы Деде- кинда—Пеано изоморфны. ¤ В § 1.3 показано, что по индукции в системе N однозначно определимы двухместные операции сложения и умножения. В дальнейшем через N будем обозначать систему Дедекинда—Пеано с этими операциями: hN; 0, 0 , +, ·i. 2. Кольцо целых чисел Определим с помощью системы N кольцо целых чисел Z = hZ; +, ·i. Рассмотрим множество N 2 = {(a, b) | a, b ∈ N} и зададим отношение ∼ по следующему правилу: (a, b) ∼ (c, d) ⇔ a + d = b + c. 80 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Положим (a, b) + (c, d) (a + c, b + d), (a, b) · (c, d) (a · c + b · d, a · d + b · c). Лемма 3.1.2. Отношение ∼ является конгруэнцией на алгебре hN 2 ; +, ·i. Доказательство. Покажем сначала, что ∼ является отношением экви- валентности. Действительно, ∼ рефлексивно, так как из a+b = b+a следует (a, b) ∼ (a, b). Из симметричности отношения равенства и (a, b) ∼ (c, d) сле- дует (c, d) ∼ (a, b), т. е. отношение ∼ симметрично. Установим теперь, что отношение ∼ транзитивно. Предположим, что (a 1 , b 1 ) ∼ (a 2 , b 2 ) и (a 2 , b 2 ) ∼ (a 3 , b 3 ). Тогда по опреде- лению выполняются равенства a 1 + b 2 = a 2 + b 1 и a 2 + b 3 = a 3 + b 2 . Складывая равенства, имеем a 1 + b 2 + a 2 + b 3 = a 2 + b 1 + a 3 + b 2 , отсюда a 1 + b 3 = a 3 + b 1 , т. е. (a 1 , b 1 ) ∼ (a 3 , b 3 ). Таким образом, ∼ — отношение эквивалентности. Докажем, что отношение ∼ согласовано с операциями + и ·. Предполо- жим (a 1 , b 1 ) ∼ (a 2 , b 2 ) и (c 1 , d 1 ) ∼ (c 2 , d 2 ). Необходимо доказать: 1) (a 1 , b 1 ) + (c 1 , d 1 ) ∼ (a 2 , b 2 ) + (c 2 , d 2 ); 2) (a 1 , b 1 ) · (c 1 , d 1 ) ∼ (a 2 , b 2 ) · (c 2 , d 2 ). Для доказательства свойства 1 нужно установить, что (a 1 + c 1 , b 1 + d 1 ) ∼ (a 2 + c 2 , b 2 + d 2 ). т. е. (a 1 + c 1 ) + (b 2 + d 2 ) = (a 2 + c 2 ) + (b 1 + d 1 ). По условию имеем a 1 + b 2 = a 2 + b 1 и c 1 + d 2 = c 2 + d 1 . (3.1) Тогда (a 1 + b 2 ) + (c 1 + d 2 ) = (a 2 + b 1 ) + (c 2 + d 1 ), откуда получаем искомое равенство. Для доказательства свойства 2 покажем, что (a 1 c 1 + b 1 d 1 , a 1 d 1 + b 1 c 1 ) ∼ (a 2 c 2 + b 2 d 2 , a 2 d 2 + b 2 c 2 ), 3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ 81 т. е. (a 1 c 1 + b 1 d 1 ) + (a 2 d 2 + b 2 c 2 ) = (a 2 c 2 + b 2 d 2 ) + (a 1 d 1 + b 1 c 1 ). Умножая поочередно первое равенство из (3.1) на c 1 , d 1 , c 2 , d 2 , получаем a 1 c 1 + b 2 c 1 = a 2 c 1 + b 1 c 1 , b 1 d 1 + a 2 d 1 = a 1 d 1 + b 2 d 1 , a 1 c 2 + b 2 c 2 = a 2 c 2 + b 1 c 2 , b 1 d 2 + a 2 d 2 = a 1 d 2 + b 2 d 2 . Аналогично, умножая поочередно второе равенство из (3.1) на a 1 , b 1 , a 2 , b 2 , имеем a 1 c 1 + a 1 d 2 = a 1 c 2 + a 1 d 1 , b 1 c 1 + b 1 d 2 = b 1 c 2 + b 1 d 1 , a 2 c 1 + |