Автор Неизвестен - Булевы алгебры (продолжение)

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)

Тема V
Булевы алгебры (продолжение)

1 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

Разделы

1

Булевы алгебры как решётки. Булевы гомоморфизмы
и подалгебры

2

Булевы кольца и структуры

3

Идеалы, фильтры и конгруэнции в булевой алгебре

4

Булевы многочлены

5

Булевы уравнения

6

Что надо знать

2 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

Новое определение булевой алгебры
Определение
Дистрибутивная решётка с дополнениями называется булевой
алгеброй.
Нетрудно установить, что оба определения булевой алгебры —
данное только что и в на первой лекции — эквивалентны:
согласно первому определению, в булевой алгебре
выполняются законы дистрибутивной решётки с дополнениями,
а в ней дополнения единственны и справедливы аксиомы Dtr
и Abs вместе с Cmp 0 и Isl 0 .

3 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

4 / 67

Соотношения в булевой алгебре
Теорема
Для любых элементов x и y булевой алгебры (с нулевым и
единичным элементами o и ι соответственно) справедливо
1

2

x v y ⇔ x u y0 = o ⇔ x0 t y = ι ⇔
⇔ x u y = x ⇔ x t y = y;
x v y ⇔ x 0 w y 0 — закон антиизотонности дополнения.

Доказательство
1

Следует из определение отношения v в решётках —
def

def

x v y = x u y = x (или x v y = x t y = y)
— и леммы об основных соотношениях в булевой алгебре.
2

x v y ⇔ x u y = x ⇔ (x u y) 0 = x 0 ⇔ x 0 t y 0 = x 0 ⇔
⇔ y 0 v x 0 ⇔ x 0 w y 0.

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

5 / 67

Булева алгебра отображений
Теорема
Пусть h B, t, u, 0 , o, ι i — булева алгебра и A — непустое
множество. Тогда множество B A также будет булевой




алгеброй относительно «поточечных» операций t, u и


8

—



(f t g)(x) = f (x) t g(x), (f u g)(x) = f (x) u g(x),
(f 8 )(x) = (f (x)) 0
для любых f, g ∈ B A . Нулём и единицей B A будут постоянные
отображения f0 (x) ≡ o и f1 (x) ≡ ι соответственно; x ∈ A.
n

При A = B n получим булеву алгебру B B всех функций из
B n в B, играющую важную роль в теории булевых
многочленов.
n
B частности, при B = 2 получаем булеву алгебру 22 всех
булевых функций от n переменных.

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

Булев гомоморфизм
Определение
Булевым гомоморфизмом называют решёточный
гомоморфизм ϕ между булевыми алгебрами, обеспечивающий
равенство ϕ(x 0 ) = ϕ(x)0 .
Инъективные булевы гомоморфизмы называют булевыми
мономорфизмами.
Таким образом, булев гомоморфизм — это отображение одной
булевой алгебры в другую, согласованное со всеми пятью
булевыми операциями.
При любом булевом гомоморфизме ϕ обязательно имеет место
ϕ(o) = o, ϕ(ι) = ι.
Булев гомоморфизм будет булевым изоморфизмом при
биективности соответствующего отображения.

6 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

Булев гомоморфизм: пример
Пусть B — атомная булева алгебра и a — её атом. Тогда
отображение ja : B → 2 такое, что

ι , если x содержит a ,
ja (x) =
o , иначе ,
есть гомоморфизм. Такие гомоморфизмы булевой алгебры
называют двузначными или характерами.
Произвольный решёточный гомоморфизм одной булевой
алгебры в другую может и не быть булевым гомоморфизмом:
например, если A ⊂ B, то естественное вложение P(A) в
P(B) является решёточным мономорфизмом, но не булевым
гомоморфизмом (и подавно, не булевым мономорфизмом), т.к.
для произвольного подмножества A его дополнения в A и B
различны.
Прообраз нуля ϕ ] (o) булева гомоморфизма ϕ — его ядро.

7 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы алгебры как решётки. Булевы гомоморфизмы и подалгебры

Подалгебры булевой алгебры
Определение
Булева алгебра B 0 называется подалгеброй булевой алгебры
B, символически B 0 6 B, если B 0 ⊆ B и на B 0 устойчивы
сужения всех операций B.
Булева алгебра и её подалгебры имеют общие o и ι.
Пример
1

2

Булева алгебра P2n логических функций от n --">