Читаем онлайн «Булевы алгебры (продолжение)»
- 123 . . . последняя (9) »
Прикладная алгебра. Тема 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 переменных
является подалгеброй алгебры P2 всех логических
функций.
Пусть A ⊂ B. Тогда P(A) P(B), поскольку эти булевы
алгебры имеют, например, разные единичные элементы
(что повлечёт и несовпадение дополнений в них).
8 / 67
Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы кольца и структуры
Разделы
1
Булевы алгебры как решётки. Булевы гомоморфизмы
и подалгебры
2
Булевы кольца и структуры
3
Идеалы, фильтры и конгруэнции в булевой алгебре
4
Булевы многочлены
5
Булевы
Тема 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 переменных
является подалгеброй алгебры P2 всех логических
функций.
Пусть A ⊂ B. Тогда P(A) P(B), поскольку эти булевы
алгебры имеют, например, разные единичные элементы
(что повлечёт и несовпадение дополнений в них).
8 / 67
Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Булевы кольца и структуры
Разделы
1
Булевы алгебры как решётки. Булевы гомоморфизмы
и подалгебры
2
Булевы кольца и структуры
3
Идеалы, фильтры и конгруэнции в булевой алгебре
4
Булевы многочлены
5
Булевы
- 123 . . . последняя (9) »