От решёток к булевым алгебрам. Султанбеков Ф.Ф. - 14 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

ством H в 2.6 упростится, а именно I(H) = {x ∈ X : ∃h ∈ H(x ≤ h)}.
Двойственным образом, F (H) = {x ∈ X : ∃h ∈ H(x ≥ h)}. Следовательно,
x ∈ I ∩ F влечет существование таких элементов h
1
, h
2
∈ H , для которых
h
1
≤ x ≤ h
2
. Так как H выпукло, то x ∈ H . Итак, H = I ∩ F .
Установим единственность этого разложения. Предположим, что H = I
1
∩
F
1
. Тогда H ⊂ I
1
и значит I(H) ⊂ I
1
. Пусть x ∈ I
1
, h ∈ H . Так как h ∈ I
1
,
то I
1
∋ x ∨ h ≥ h ∈ F
1
, и x ∨ h ∈ F
1
. Итак, x ∨ h ∈ I
1
∩ F
1
= H . Поэтому
x ≤ x ∨ h ∈ H влечет x ∈ I(H). Тем самым мы показали, что I
1
= I(H).
Двойственным образом показываем, что F
1
= F (H).
2.10. Нулем 0 и единицей 1 у.м X называются наименьший и наибольший
элементы X , если таковые существуют. Ясно, что в конечной решетке L =
{x
1
, x
2
, ..., x
n
} 0 = x
1
∧ x
2
∧ ... ∧ x
n
, 1 = x
1
∨ x
2
∨ ... ∨ x
n
. Конечную решётку
можно задать с помощью таблиц для операций ∨, ∧ (алгебраический способ).
Другой способ (порядковый) основан на следующем понятии. Скажем, что
b покрывает a, если a < b и ̸ ∃x (a < x < b). Тогда решётку можно
представить в виде графа (V, E ), вершинами V которого являются элементы
решётки, а рёбрами E все те пары (a, b) в которых b покрывает a. При
этом на диаграмме вершина b располагается выше вершины a (тем самым
получается ориентируемый граф; о графах подробнее см. [7]). В конечных
у.м отношение покрываемости полностью определяет порядок: a ≤ b тогда и
только тогда, когда из a можно, поднимаясь строго верх по каждому ребру
графа, добраться до элемента b.
Приведём примеры простейших конечных решёток. Для краткости ребро
(a, b) входящее в E будем обозначать ab.
Диамант M
3
имеет множество вершин V = {0, x, y, z, 1} и множество
рёбер E = {0x, 0y, 0z, x1, y1, z1}.Пентагон N
5
имеет множество вершин
V = {0, a, b, c, 1} и множество рёбер E = {0a, 0c, ab, b1, c1}. Решётка (C
2
)
3
- это решётка всех подмножеств 3-элементного множества, упорядоченная
по включению. Такое обозначение выбрано в силу того, что она изморфна
прямому произведению трех экземпляров решётки C
2
= {0, 1}.
14
ством H в 2.6 упростится, а именно I(H) = {x ∈ X : ∃h ∈ H(x ≤ h)}.
Двойственным образом, F (H) = {x ∈ X : ∃h ∈ H(x ≥ h)}. Следовательно,
x ∈ I ∩ F влечет существование таких элементов h1 , h2 ∈ H , для которых
h1 ≤ x ≤ h2 . Так как H выпукло, то x ∈ H . Итак, H = I ∩ F .
  Установим единственность этого разложения. Предположим, что H = I1 ∩
F1 . Тогда H ⊂ I1 и значит I(H) ⊂ I1 . Пусть x ∈ I1 , h ∈ H . Так как h ∈ I1 ,
то I1 ∋ x ∨ h ≥ h ∈ F1 , и x ∨ h ∈ F1 . Итак, x ∨ h ∈ I1 ∩ F1 = H . Поэтому
x ≤ x ∨ h ∈ H влечет x ∈ I(H). Тем самым мы показали, что I1 = I(H).
Двойственным образом показываем, что F1 = F (H). 
  2.10. Нулем 0 и единицей 1 у.м X называются наименьший и наибольший
элементы X , если таковые существуют. Ясно, что в конечной решетке L =
{x1 , x2 , ..., xn } 0 = x1 ∧ x2 ∧ ... ∧ xn , 1 = x1 ∨ x2 ∨ ... ∨ xn . Конечную решётку
можно задать с помощью таблиц для операций ∨, ∧ (алгебраический способ).
Другой способ (порядковый) основан на следующем понятии. Скажем, что
b покрывает a, если a < b и ̸ ∃x (a < x < b). Тогда решётку можно
представить в виде графа (V, E ), вершинами V которого являются элементы
решётки, а рёбрами E все те пары (a, b) в которых b покрывает a. При
этом на диаграмме вершина b располагается выше вершины a (тем самым
получается ориентируемый граф; о графах подробнее см. [7]). В конечных
у.м отношение покрываемости полностью определяет порядок: a ≤ b тогда и
только тогда, когда из a можно, поднимаясь строго верх по каждому ребру
графа, добраться до элемента b.
  Приведём примеры простейших конечных решёток. Для краткости ребро
(a, b) входящее в E будем обозначать ab.
  Диамант M3 имеет множество вершин V = {0, x, y, z, 1} и множество
рёбер E = {0x, 0y, 0z, x1, y1, z1}.Пентагон N5 имеет множество вершин
V = {0, a, b, c, 1} и множество рёбер E = {0a, 0c, ab, b1, c1}. Решётка (C2 )3
- это решётка всех подмножеств 3-элементного множества, упорядоченная
по включению. Такое обозначение выбрано в силу того, что она изморфна
прямому произведению трех экземпляров решётки C2 = {0, 1}.

                                          14

Страницы