Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 543
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
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
=
что 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
=
1 ... 4 5 6 7 8 9 10 11 ... 29