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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

23
◦
. Расставьте на графе свободной решётки F
M
(3) все остальные элементы
( см. рис. 5).
24
◦
. Постройте реализации свободных решёток C
2
∗ C
1
и C
3
∗ C
1
.
25
◦
. Постройте графы свободных решёток F
K
(C
2
∪ C
1
) и F
K
(C
3
∪ C
1
) для
многообразий K = M, D.
§6. Булевы алгебры
6.1. Пусть X у.м с 0 и 1. Говорят, что x, y ∈ X дизъюнктны, если x∧y = 0.
Элементы x, y ∈ X дополнительны, если x ∧ y = 0, x ∨ y = 1. Часть D ⊂
X называется дизъюнктной, если любая пара элементов из D дизъюнктна.
Множество A дизъюнктно множеству B , если ∀a ∈ A ∀b ∈ B(a ∧ b = 0).
Например, в решётке промежутков L < a, b > отрезок [a, c] и промежуток
[a, c) дополнительны к (c, b]. Если же a < c < d < b, то [c, d] не имеет
дополнения.
6.2. Булевой алгеброй (б.а) называется дистрибутивная решётка с 0 и 1 в
которой каждый элемент имеет дополнение. Б.а {0, 1} называется вырож-
денной. Б.а X называется полной , если ∀E ⊂ X(sup E ∈ X, inf E ∈ X).
Если это условие выполняется для всех счетных подмножеств E , то б.а X
называется σ -полной.
6.3. Предложение. В булевой алгебре любой элемент имеет единствен-
ное дополнение.
Действительно, пусть y
1
, y
2
дополнительны к x. Тогда y
1
= y
1
∧ 1 = y
1
∧
1(x ∨ y
2
) = (y
1
∧ x) ∨ (y
1
∧ y
2
) = 0 ∨ (y
1
∧ y
2
) = y
1
∧ y
2
. Значит y
1
≤ y
2
.
Аналогично y
2
≤ y
1
. Дополнение к элементу x в ба обозначается x
′
.
6.4. Свойства дополнения:
a) x
′′
= x; b) x ∧ y = 0 ⇔ y ≤ x
′
c) x ≤ y ⇔ y
′
≤ x
′
;
27
23 ◦ . Расставьте на графе свободной решётки FM (3) все остальные элементы
( см. рис. 5).

24 ◦ . Постройте реализации свободных решёток C2 ∗ C1 и C3 ∗ C1 .

25 ◦ . Постройте графы свободных решёток FK (C2 ∪ C1 ) и FK (C3 ∪ C1 ) для
многообразий K = M, D.




                            §6. Булевы алгебры


  6.1. Пусть X у.м с 0 и 1. Говорят, что x, y ∈ X дизъюнктны, если x∧y = 0.
Элементы x, y ∈ X дополнительны, если x ∧ y = 0, x ∨ y = 1. Часть D ⊂
X называется дизъюнктной, если любая пара элементов из D дизъюнктна.
Множество A дизъюнктно множеству B , если ∀a ∈ A ∀b ∈ B(a ∧ b = 0).
Например, в решётке промежутков L < a, b > отрезок [a, c] и промежуток
[a, c) дополнительны к (c, b]. Если же a < c < d < b, то [c, d] не имеет
дополнения.

  6.2. Булевой алгеброй (б.а) называется дистрибутивная решётка с 0 и 1 в
которой каждый элемент имеет дополнение. Б.а {0, 1} называется вырож-
денной. Б.а X называется полной , если ∀E ⊂ X(sup E ∈ X, inf E ∈ X).
Если это условие выполняется для всех счетных подмножеств E , то б.а X
называется σ -полной.
  6.3. Предложение. В булевой алгебре любой элемент имеет единствен-
ное дополнение.
  Действительно, пусть y1 , y2 дополнительны к x. Тогда y1 = y1 ∧ 1 = y1 ∧
1(x ∨ y2 ) = (y1 ∧ x) ∨ (y1 ∧ y2 ) = 0 ∨ (y1 ∧ y2 ) = y1 ∧ y2 . Значит y1 ≤ y2 .
Аналогично y2 ≤ y1 . Дополнение к элементу x в ба обозначается x′ .
  6.4. Свойства дополнения:
            a) x′′ = x; b) x ∧ y = 0 ⇔ y ≤ x′ c) x ≤ y ⇔ y ′ ≤ x′ ;


                                       27

Страницы