Булевы алгебры (продолжение) [Автор Неизвестен] (pdf) читать онлайн

Прикладная алгебра. Тема 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

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

6

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

9 / 67

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

10 / 67

Алгебраические кольца: напоминание
Кольцом называется АС h R, +, ·, 0 i, где R — множество,
содержащее элемент нуль (0), на котором определены две
бинарные операции сложение (+) и умножение (·) такие, что
для любых x, y, z ∈ R справедливы соотношения
(x + y) + z = x + (y + z) , x + y = y + x ,
∀x ∃y : (x + y = 0)

x+0 = x

(указанное означает, что редукт h R, +, 0 i кольца есть абелева
группа по сложению, или модуль) и
(x + y) · z = x · z + y · z ,

x · (y + z) = x · y + x · z,

(дистрибутивность умножения по отношению к сложению).

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

Алгебраические кольца: напоминание
Нуль кольца — единственный элемент, обладающий свойством
x + 0 = x. Элемент y такой, что x + y = o называют
обратным к x, его обозначение — (−x) в силу единственности.
Если умножение обладает свойством ассоциативности
(x · y) · z = x · (y · z)
и/или коммутативности
x · y = x · y,
то и кольцо называют соответствующе.
Если кольцо содержит единицу (1) — уникальный элемент, для
которого
x · 1 = 1 · x = x,
то говорят о кольце с единицей (унитальном): h R, +, ·, 0, 1 i.

11 / 67

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

Булевы кольца
Определение
Ассоциативное кольцо, обладающие свойством x2 = x для
любого своего элемента называется булевым кольцом.
Теорема
Булево кольцо h R, +, ·, 0 i коммутативно и −x = x.
Доказательство
Докажем сначала второе утверждение:
x + x = (x + x)2 = x2 + x2 + x2 + x2 = (x + x) + (x + x) ⇒
x + x = 0.
Отсюда
x + y = (x + y)2 = x2 + xy + yx + y 2 = x + xy + yx + y ⇒
xy + yx = 0
и далее получаем
xy = xy + 0 = xy + (xy + yx) = (xy + xy) + yx = 0 + yx = yx.

12 / 67

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

От булевой алгебры к булеву кольцу
Теорема
Пусть B = h B, t, u, 0 , o, ι i — булева алгебра.
Для любых x, y ∈ B положим
x + y = (x u y 0 ) t (x 0 u y) , x · y = x u y.
Тогда АС B∗ = h B, +, ·, o, ι i — булево кольцо с единицей ι.
Доказательство
Коммутативность введённых операций сложения (+) и
умножения (·), ассоциативность умножения, справедливость
равенства x2 = x и наличие единицы ι с её свойством
x · ι = x для всех x — очевидны.
Условия теоремы позволяют не различать операции умножения
и пересечения.
С учётом этого — x + y = xy 0 t x 0 y = x ⊕ y.

13 / 67

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

От булевой алгебры к булеву кольцу...
Доказательство (продолжение)
Используя законы булевой алгебры, получим
(x + y) + z = (xy 0 t x 0 y)z 0 t (xy 0 t x 0 y) 0 z =
= xy 0 z 0 t x 0 yz 0 t (x 0 t y)(x t y 0 )z =
= xy 0 z 0 t x 0 yz 0 t x 0 y 0 z t xyz ,
x + (y + z) = x(yz 0 t y 0 z) 0 t x 0 (yz 0 t y 0 z) =
= x(y 0 t z)(y t z 0 ) t x 0 yz 0 t x 0 0 y =
= xy 0 z 0 t xyz t x 0 yz 0 t x 0 y 0 z .
Таким образом, (x + y) + z = (x + y) + z, и ассоциативность
операции + показана.

14 / 67

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

От булевой алгебры к булеву кольцу...
Доказательство (продолжение)
Далее: x + o = xo 0 t x 0 o = xι = x,
т.е. B∗ оказывается абелевой группой по сложению.
И, наконец, выкладки
(x + y)z = (xy 0 t x 0 y)z = xy 0 z t x 0 yz ,
xz + yz = xz(yz) 0 t (xz) 0 (yz) =
= xz(y 0 t z 0 ) t (x 0 t z 0 )yz = xy 0 z t x 0 yz
доказывают дистрибутивный закон умножения относительно
сложения.
Основным примером булева кольца и является как раз кольцо
h P(A), ⊕, ∩, ∅, A i, получаемое указанным способом из
тотальной алгебры множеств.

15 / 67

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

От булева кольца к булевой алгебре
Теорема
Пусть R = h R, +, ·, 0, 1 i — булево кольцо с единицей. Для
любых x, y ∈ R положим
x t y = x + y + x · y, x u y = x · y , x 0 = x + 1.
Тогда АС R∗ = h R, t, u, 0 , 0, 1 i — булева алгебра.
Доказательство
Ассоциативность введённых операций t, u и закон Id t (с
учётом x + x = 0 ) проверяются непосредственно, а Id u
наследуется из R.
Коммутативность булева кольца, обеспечивает
коммутативность t и u.
Далее в выкладках без пояснений используются свойства
булева кольца.

16 / 67

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

От булева кольца к булевой алгебре...
Доказательство (продолжение)
Установим справедливость законов поглощения:
(x t y) u x = (x + y + xy)x = x + xy + xy = x .
x t (x u y) = x t (xy) = x + xy + xy = x .
Таким образом, B∗ — решётка.
Непосредственно проверяется выполнение пар законов t o, u ι
и t ι, u o.
В силу этого 0 и 1 суть универсальные грани решётки B∗ .

17 / 67

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

От булева кольца к булевой алгебре... Стоуновская
двойственность
Доказательство (продолжение)
Из равенств
x u x 0 = x(1 + x) = x + x = 0 и
x t x 0 = x t (1 + x) = x + 1 + x + x(1 + x) = 1 + x + x = 1
вытекает, что B∗ — решётка с дополнениями.
Равенства
(x t y) u z = (x + y + xy)z = xz + yz + xyz = (x u z) t (x u z)
доказывают справедливость в B∗ первого дистрибутивного
закона, а второй доказывается двойственно.
Таким образом, любое булево кольцо с единицей может быть
задано с помощью булевой алгебры и наоборот.
Следствие: B∗∗ = B и R∗∗ = R.
Тем самым устанавливается т.н. стоуновская двойственность
между булевыми алгебрами и булевыми кольцами.

18 / 67

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

19 / 67

Булева структура
Определение
АС h B, t, u, 0 , v, o, ι i такая, что h B, t, u, 0 , o, ι i — булева
алгебра, а отношение v задаются по правилу
def

def

x v y = x u y = x (или x v y = x t y = y)
называется булевой структурой.
Утверждение
Элемент a булевой алгебры B является атомом, iff o l a.
Доказательство
Пусть a и b — элементы булевой алгебры B. Тогда
o l a ⇒ (a v b) ∨ (a 6∼ b) ⇒ (a u b = a) ∨ (a u b = o),
т.е. a ∈ At(B);
если a ∈ At(B) и a v b, то a u b = a 6= b и b 6∈ At(B).

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Разделы

1

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

2

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

3

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

4

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

5

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

6

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

20 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Булевы идеалы и фильтры: определение
Определение
Идеалом [фильтром] булевой алгебры называют её решёточные
идеалы [ фильтры ].
Если I — идеал булевой алгебры B, то пишут I P B.
Каждый булев идеал I и фильтр F булевой алгебры B
обладает всеми свойствами решёточных, и, кроме этих, ещё и
(x ∈ I) N (x 0 ∈ I) ⇒ I = B и (x ∈ F ) N (x 0 ∈ F ) ⇒ F = B.

Действительно, по определению идеала ι = x t x 0 ∈ I, откуда
I = B и аналогично для фильтров.
На идеалы и фильтры булевой алгебры переносятся понятия,
собственных, несобственных и главных идеалов и фильтров.
Поскольку булева алгебра есть решётка, то в конечной булевой
алгебре все идеалы и фильтры — главные.

21 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Булевы идеалы и фильтры: примеры
1

Пусть B ⊆ A. Тогда совокупность всех подмножеств
множества A, содержащихся в B есть идеал булевой
алгебры P(A), а содержащих B — фильтр P(A).
Это — главные идеалы и фильтры в бесконечной булевой
алгебре.

2

Приведём пример неглавных идеалов и фильтров.
Пусть A — бесконечное множество. Совокупность P0 (A)
всех конечных подмножеств A есть неглавный идеал, а
совокупность подмножеств, имеющих конечное дополнение
до A — неглавный фильтр булевой алгебры P(A).
Фильтр указанного вида называют фильтром Фреше.

То, что I — собственный идеал булевой алгебры B будем
записывать I / B.

22 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Максимальные идеалы и фильтры. Ультрафильтр
Определение
Идеал [ фильтр ] булевой алгебры называется максимальным,
если он не содержится ни в каком другом собственном идеале
[ фильтре ].
Фильтр булевой алгебры B называется ультрафильтром если
для любого b ∈ B ему принадлежит в точности один из
элементов b и b 0 .
Понятно, что если x — атом [ коатом ] конечной булевой
алгебры, то xM [ xO ] — её максимальный фильтр [ идеал ].
В конечных булевых алгебрах ультрафильтры других видов, в
очевидно (как в решётках), отсутствуют.

23 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Свойства максимальных булевых идеалов и фильтров
Теорема
1

Каждый собственный идеал булевой алгебры содержится в
некотором максимальном идеале.
Аналогично для фильтров.

2

Идеал [ фильтр ] булевой алгебры B является
максимальным, iff для любого x ∈ B в нём содержится в
точности один из элементов x и x 0 .

3

Собственный идеал I булевой алгебры B будет
максимальным, iff для любых x, y ∈ B из условия
(x u y) ∈ I следует, что либо x, либо y принадлежит I.
Собственный фильтр F булевой алгебры B будет
максимальным, iff для любых x, y ∈ B из условия
(x t y) ∈ F следует, что либо x, либо y принадлежит F .

24 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Свойства максимальных булевых идеалов и фильтров:
замечание к теореме
K п. 1. Данное утверждение для фильтров часто называют
теоремой об ультрафильтрах булевой алгебры.
K п. 2. Данное утверждение доказывает эквивалентность понятий
«максимальный фильтр» и «ультрафильтр».
K п. 3. Простой — собственный фильтр F булевой алгебры B,
удовлетворяющий условию
(x t y) ∈ F ⇒ (x ∈ F ) ∨ (y ∈ F ).
Т.о. данное утверждение доказывает эквивалентность
понятий «ультрафильтр» и «простой фильтр» булевой
алгебры.
В булевой алгебре:
«максимальный» = «простой» = «ультрафильтр»

25 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Свойства максимальных булевых идеалов и фильтров:
замечание к теореме
Пусть B — булева алгебра, а ∼ — конгруэнция на ней, как на
решётке. Если при этом ещё и
x ∼ y ⇒ x 0 ∼ y 0,
то ∼ — конгруэнция на данной булевой алгебре.
Конгруэнции булевой алгебры B образуют полную
дистрибутивную решётку Con B. Её наименьшим элементом
является тождественная конгруэнция MB , а наибольшим —
аморфная конгруэнция OB .

26 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Свойства идеалов булевой алгебры
Отличие идеалов булевой алгебры от решёточных:
первые находятся во взаимно-однозначном соответствии с
конгруэнциями булевой алгебры, т.е. если ∼ = ∼I —
конгруэнция на булевой алгебре B и I = [ o ] — класс
эквивалентности, содержащий элемент o, то I — идеал B,
причём выполняется соотношение
a ∼I b ⇔ ∃ x (a t x = b t x).
I

И обратно, если I P B, то отношение ∼I на B, определённое
этим условием, будет конгруэнцией на B, причём [ o ] = I.
Более того, справедливо
Утверждение
Пусть a и b — элементы булевой алгебры B и I P B, тогда
a ∼I b ⇔ (a u b 0 ) t (a 0 u b) ∈ I.

27 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Факторалгебры
Если ∼ — конгруэнция на булевой алгебре B, а I — идеал,
соответствующий данной конгруэнции в указанном выше
смысле, то факторалгебру B/ ∼ обозначают B/I.
Отображение ϕ : B → B/ ∼, ϕ(x) = [x]∼ , ставящее в
соответствие элементу B его смежный класс по конгруэнции
∼∈ Con(B), является, очевидно, гомоморфизмом.
Такой гомоморфизм, в соответствии с общим подходом,
называется естественным. С другой стороны, если ϕ —
гомоморфизм булевой алгебры B, то ϕ(B) ∼
=b B/Ker ϕ и
Ker ϕ ∈ Con(B).
Теорема
Идеал I булевой алгебры B максимален, iff B/I ∼
=b 2.

28 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Факторалгебры: примеры
Справедлив изоморфизм B/xO ∼
=b [ o, x 0 ].
Пример
1. Был пример: пусть B — атомная булева алгебра и a — её
атом.
Тогда отображение ja : B → 2 такое, что

ι , если x содержит a ,
ja (x) =
o , иначе ,
есть гомоморфизм.
Идеалом приведённого в этого двузначного гомоморфизма ja
будет главный идеал (a 0 )O , порождённый коатомом a 0 .

29 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Факторалгебры: примеры...
2. Проиллюстрируем изоморфизм B/xO ∼
=b [ o, x 0 ] для
3
булевой алгебры B .
Её атомы будем обозначать a, b и c, а остальные элементы —
указанием содержащихся в них атомов. Если в качестве идеала
I взять aO , то классами эквивалентности по ∼aO будут
[a] = aO = I = { a, ∅ }, [b] = { ab, b }, [c] =
{ ac, c }, [bc] = { abc, bc }.
Факторалгеброй булевой алгебры B 3 по выбранному идеалу
будет изоморфная B 2 алгебра из указанных выше классов с
нулём I, атомами [b] и [c] и единицей [bc].
Поскольку bc = a 0 и ∅ ∈ I, то B/aO ∼
=b [ ∅, a 0 ].

30 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

31 / 67

Факторалгебры: примеры
Булева алгебра B 3 (классы эквивалентности по ∼aO выделены
двойными линиями) и факторалгебра B 3 /aO :
abc

[[[[

[[

ab [
[[[ ac [[[[ bc
[[ [[

a [
[[[ b  c
[[ 
I

∅

[[

[

[b]
[c]
[[
[ 
[bc]

I

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

32 / 67

Построение безатомной булевой алгебры факторизацией
1. Рассмотрим тотальную алгебру h P(Z), ∪, ∩, − , ∅,
множеством целых чисел.

Zi

над

2. Определим отношение ' над элементами P(Z): A ' B,
если симметрическая разность множеств A и B конечна.
Поскольку ' — отношение эквивалентности, можно образовать
фактормножество P(Z)/'. Все конечные (включая пустое)
подмножества P(Z) будут, очевидно, эквивалентными.
Обозначим этот класс эквивалентности [∅].
Также будут эквивалентными все подмножества целых чисел,
имеющих конечные дополнения до Z, включая само Z; этот
класс эквивалентности обозначим [Z].

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение безатомной булевой алгебры факторизацией...
3. Легко проверить, что введенное отношение является также и
стабильным относительно теоретико-множественных операций,
т.е. для любых A, B ∈ P(Z) из A ' A 0 и B ' B 0 следует
A ∪ B ' A 0 ∪ B 0 , A ∩ B ' A 0 ∩ B 0 и A ' A 0 . Это означает,
что АС h P(Z)/ ', ∪, ∩, − , [∅], [Z] i будет являться булевой
алгеброй.
4. Убедимся, что данная булева алгебра не имеет атомов:
действительно, любой отличный от [∅] элемент P(Z)/ ' есть
класс бесконечных множеств.
Атом — элемент, непосредственно следующий за [∅], а таковые
отсутствуют в P(Z)/ ' , т.е. в любом бесконечном множестве
X можно (с помощью АС!) указать подмножество Y такое,
что и оно, его дополнение бесконечны, и поэтому [Y ] строго
содержится в [X].

33 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Тривиальные ультрафильтры
Говорят, что главные ультрафильтры алгебры множеств,
поскольку все они имеют вид aM , фиксированы в точке a
множества. Их называют тривиальными ультрафильтрами.
Совместно с фильтрами Фреше они играют важную роль при
исследовании сходимости в анализе (топологическая система
окрестностей данной точки является фиксированным в ней
тривиальным ультрафильтром).
Главные ультрафильтры также используют, например, при
исследованиях полноты логических систем в алгебрах
Линденбаума–Тарского, порождённых соответствующей
логической теорией.

34 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Общее решение булева уравнения — ультрафильтр
Пусть A = { A, B, . . . } — множество формул над
высказываниями в КИВ.
Если A ≡ B — тавтология, то говорят, что формулы A и B
логически эквивалентны или равносильны, что записывают как
A ∼ B. Ясно, что ∼ есть отношение эквивалентности на A.
Класс эквивалентности, порождаемый формулой A будем
обозначать [A], классы тождественно истинных формул — T, а
тождественно ложных формул — F.
На фактормножестве A/ ∼ классов эквивалентности формул
алгебры логики можно задать теоретико множественные
операции дополнения (− ), объединения (∪) и пересечения
(∩), причём
[A] = [¬A],

[A] ∪ [B] = [A ∨ B], [A] ∩ [B] = [ANB].

35 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Общее решение булева уравнения — ультрафильтр...
Легко установить, что введённые операции над классами
эквивалентностей имеют следующие свойства:
операции ∪ и ∩ коммутативны и взаимно дистрибутивны;
выполняются соотношения [A] ∪ F = [A] и [A] ∩ T = [A];
справедливы законы [A] ∪ [A] = T и [A] ∩ [A] = F.
Это означает, что АС h A/∼, ∪, ∩, − , T, F i — булева алгебра,
называемая факторалгеброй логических формул; для КИВ она
совпадает с соответствующей алгеброй Линденбаума–Тарского
(в последней факторизация проводится по отношению '
такому, что A ' B ⇔ A ` B и B ` A).
С каждым элементом A/ ∼ связана соответствующая функция
алгебры логики.
Обозначим через An множество формул алгебры логики над n
элементарными высказываниями. Тогда An бесконечно, а
n
фактормножество An / ∼ — конечно (содержит 22 элементов).

36 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Общее решение булева уравнения — ультрафильтр...
Рассмотрим уравнение
a(x̃) N X(x̃) = F,
где a(x̃) и X(x̃) — формулы, реализующие соответственно
известную и искомую булевы функции (для простоты
указывают именно формулы, а не порождённые ими классы).
Тогда решением данного уравнения будет любая функция,
реализуемая формулами из главного идеала, порождённого
формулой a(x̃) в соответствующей алгебре
Линденбаума–Тарского.
Далее знак конъюнкции N будем для простоты опускать.

37 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

38 / 67

Общее решение булева уравнения — ультрафильтр...
Например, пусть a(x̃) = x1 x2 , т.е. дано уравнение
x1 x2 X(x1 , x2 ) = F.

(∗).

Имеем x1 x2 = x1 ∨ x2 , и главный идеал алгебры
Линденбаума–Тарского, порождённый классом формул
[ x1 ∨ x2 ], составляют классы [ x1 ∨ x2 ], [ x1 ], [ x2 ],
[ x1 x2 ∨ x1 x2 ], [ x1 x2 ], [ x1 x2 ], [ x1 x2 ] и F.
На рисунке следующего слайда данный идеал.
Для каждого класса указан вектор значений соответствующей
функции (подразумевается упорядочение наборов значений
переменных сначала по x, затем по y).

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

39 / 67

Общее решение булева уравнения — ультрафильтр...
[ x1 ∨ x2 ]
(0111)

[ x1 ]
(0011)

[ x1 x2 ]
(0010)

AA
A
A
A
AAA
[x x

∨ x1 x2 ]
(0110)

1 2

AA
A
A
AAA

[ x2 ]
(0101)

A
A
A
AAA
A
A
[x x ]
[x x ]
(0001)
A (0100)
A
A
AAA
A
A
1 2

F
(0000)

Решением уравнения (∗) будет любая булева функция,
реализующаяся формулами из приведённых классов.

1 2

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение неглавного ультрафильтра
В бесконечных булевых алгебрах, могут существовать и
неглавные (нетривиальные) ультрафильтры. Их также
называют свободными, поскольку они не фиксированы ни в
какой точке исходного множества. Пересечение всех элементов
такого фильтра есть единичный элемент.
Пример
Опишем в самом общем виде, как может быть построен
неглавный ультрафильтр F булеана P(N) .
1. Рассмотрим фильтр Фреше, который обозначим F0 . Он не
является максимальным, поскольку, например, ни множество
чётных чисел 2N, ни его дополнение (множество нечётных
чисел) не принадлежат F0 . Поэтому надо принять решение,
отнести 2N к конструируемому ультрафильтру F или нет.

40 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение неглавного ультрафильтра...
2. Пусть принято решение о том, что 2N ∈ F . Это будет
означать, что некоторые другие множества (все множества,
содержащие 2N ) также будут принадлежать F . Полученный
фильтр обозначим F1 .
Понятно, что он также не будет являться искомым
ультрафильтром, поскольку относительно ряда множеств
неопределённость останется: например, ни множество 3N, ни
его дополнение не принадлежат F1 . Здесь снова нужно
принять решение о вхождении одного из указанных множеств в
F1 , построить F2 и т.д.
3. Показано, что в результате выполнения “трансфинитного
числа шагов” будет построен искомый ультрафильтр F .

41 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение неглавного ультрафильтра...
Мы привели чрезвычайно грубый набросок способа построения
фильтра F , но в нём роль АС: никакого способа указать, какое
множество нужно рассматривать на каждом шаге для
включения его или его дополнения в F , нет.
Кроме того, на каждом шаге можно принять любую из
указанных альтернатив.
Мы видим, что процесс построения F существенно
неоднозначен, и, на самом деле, до сих пор не указано ни
одного неглавного ультрафильтра в явном виде, без
применения аксиомы выбора.

42 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение гипердействительных чисел
Множество гипердействительных чисел ∗ R представляет собой
неархимедово упорядоченное поле, являющееся расширением
поля R действительных чисел.

Это означает, что ∗ R — цепь, в которую вложено множество R
(стандартные гипердействительные числа) и содержащее,
кроме того, множество т.н. нестандартных гипердействительных
чисел. При этом в ∗ R выполняются все аксиомы поля, однако
не выполняется справедливая в R аксиома Архимеда:
«для любых двух положительных чисел a и b
существует натуральное n такое, что n · a > b».
Абрахам Робинсон (Abraham Robinson,
1918–1974) — американский математик,
создатель «нестандартного анализа».

43 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение гипердействительных чисел...
Согласно принципу наследования свойств при расширении,
аксиома Архимеда может нарушаться лишь когда хотя бы одно
из чисел a и b нестандартное.
Среди нестандартных чисел выделяют бесконечно большие и
бесконечно малые: если числа ε и I суть положительные
соответственно бесконечно малое и бесконечно большое
гипердействительные, а x — положительное действительное,
то неравенства n · ε > x и n · x > I не будут выполняться ни
для какого натурального n.
Поле гипердействительных чисел ∗ R можно построить,
используя некоторый неглавный ультрафильтр U в P(N).
Рассмотрим всевозможные последовательности обычных
действительных чисел. Будем говорить, что
последовательности a = (a1 , a2 , . . . ) и b = (b1 , b2 , . . .)
эквивалентны, если равенство ai = bi нарушается на
множестве, не принадлежащем U .

44 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение гипердействительных чисел...
Легко проверяется, что, в силу свойств ультрафильтров
введённое отношения действительно является отношением
эквивалентности и, например, все последовательности,
отличающиеся в конечном числе членов, эквивалентны.
Получающиеся классы эквивалентности назовём
гипердействительными числами; они и будут являться
элементами ∗ R.
Действительному числу a соответствует класс эквивалентности
[( a, a, . . . )], это — стандартное гипердействительное число.
Четыре арифметических действия производятся над
последовательностями почленно.
Будем считать, что a < b , если неравенство ai > bi
выполняется на каком-либо множестве, не входящем в U .

45 / 67

Прикладная алгебра. Тема V: Булевы алгебры (продолжение)
Идеалы, фильтры и конгруэнции в булевой алгебре

Построение гипердействительных чисел...
Нетрудно проверить, что, поскольку U — ультрафильтр,
получено упорядоченное поле.
В этом поле, однако, аксиома Архимеда не выполняется:
например, [( 1, 12 , 13 , . . . )] есть бесконечно малое, а
[( 1, 2, 3, . . . )] — бесконечно большое гипердействительные
числа.
При проверке этих свойств и требуется, чтобы U был
неглавным ультрафильтром.

46 / 67

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

Разделы

1

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

2

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

3

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

4

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

5

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

6

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

47 / 67

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

Булевы многочлены: определение
Определение
Пусть Xn = { x1 , . . . , xn } — n -элементное множество
переменных.
Булевы многочлены над Xn — формулы из переменных и
констант 0 и 1 над множеством символов { t, u, 0 }, т.е.
1
2

x1 , . . . , xn , 0, 1 — булевы многочлены;
если p и q — булевы многочлены, то таковыми являются
и (p t q), (p u q), (p 0 ).

Синтаксическое тождество: говорим, что многочлены p и q
равны, если
p = q ⇔ p и q совпадают как строки символов.
Pn — множество всех булевых многочленов над Xn .
Это не булева алгебра, т.к., например, x1 t x2 6= x2 t x1 .

48 / 67

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

Булевы многочлены: полиномиальная функция
Далее пользуемся известными правилами экономии скобок.
Определение
Пусть B — булева алгебра и p — булев многочлен из Pn .
Обозначим через pbB (b1 , . . . , bn ) элемент из B, который
получается из p заменой xi 7→ bi ∈ B, i = 1, n, а отображение
pbB : B n → B,

(b1 , . . . , bn ) 7→ pbB (b1 , . . . , bn )

назовём полиномиальной функцией, индуцированной булевым
многочленом p на B.
PBn = { pbB | p ∈ Pn } — множество всех полиномиальных
функций, индуцированных многочленами из Pn на B.
n
Ясно, что PBn ⊆ B B .

49 / 67

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

Булевы многочлены: полиномиальная функция...
Пример (везде n = 2)
1

Пусть B = 2 = { 0, 1}, p = x1 t x2 и q = x2 t x1 .
Тогда
p 6= q,
pbB = a ∨ b, qbB = b ∨ a,
pbB = qbB , т.к. при любой замене в этих выражениях букв a
и b элементами {0, 1} получим один и тот же элемент.

2

Пусть B = P(A), p = (x1 t x2 ) 0 и q = x1 0 u x2 0 .
Тогда
p 6= q,
pbB = X ∪ Y , qbB = X ∩ Y , где X, Y ⊆ A 6= ∅,
pbB = qbB .

50 / 67

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

PBn — подалгебра B B

51 / 67

n

Ясно, что h PBn , t, u, 0 , 0, 1 i — булева алгебра.
Теорема
n

PBn 6 B B .
Доказательство
Убедимся в устойчивости помножества PBn ⊆ B B
относительно операций булевой алгебры.

n

По определению полиномиальных функций, для t и
произвольного a ∈ B n имеем
\
(b
pB t qbB )(a) = pbB (a) t qbB (a) = (p
t q) (a) ∈ P n .
B

Устойчивость операций u и
Также

PBn

и

n
BB

0

B

доказывается аналогично.

содержат функции f0 ≡ 0 и f1 ≡ 1.

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

Булевы многочлены: эквивалентность
Определение
Два булевых многочлена p, q ∈ Pn называются
эквивалентными (символически p ∼ q ), если равны их
полиномиальные функции на 2, т.е. p ∼ q ⇔ pb2 = qb2 .
∼ действительно есть отношение эквивалентности на Pn
(свойства рефлексивности, симметричности и транзитивности
наследуются из отношения равенства функций).
С помощью теоремы Стоуна доказывается
Теорема
Пусть p, q ∈ Pn и p ∼ q.
Тогда для произвольной булевой алгебры B справедливо
pbB = qbB .

52 / 67

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

Фактормножество Pn по эквивалентности —
Теорема
Pn / ∼ есть булева алгебра, и Pn / ∼ ∼
=b P2n .
Доказательство
Определим отображение ϕ : P2n → Pn / ∼, которое переводит
полиномиальную функцию P2n , индуцированную многочленом
p на 2 в класс эквивалентности [p]∼ .
Данное определение корректно, т.к.
pb2 = qb2 ⇒ p ∼ q ⇒ [p]∼ = [q]∼ .
Легко проверить, что ϕ и есть искомый булев изоморфизм.

53 / 67

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

Булева алгебра: полиномиальная полнота
Если PBn ∼
=b B B , то назовём булеву алгебру B
полиномиально полной.
Полиномиальная полнота означает, что каждую функцию
можно представить полиномом.
n

Из единственности представления булевых (2n → 2) функций
в виде совершенных ДНФ, КНФ или АНФ (полиномов
n
Жегалкина), следует, что |Pn / ∼ | = 22 .
Отсюда:
поскольку Pn / ∼ ∼
=b P2n , то алгебра 2 полиномиально
полна.
если |B| = m > 2, то
n
n
n
|PBn | = |Pn / ∼ | = 22 < mm = |B B |, т.е. 2 —
единственная полиномиально полная булева алгебра.

54 / 67

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

Разделы

1

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

2

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

3

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

4

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

5

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

6

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

55 / 67

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

Булевы уравнения: определение
Определение
Пару (p, q), где p, q ∈ Pn назовём булевым уравнением.
Пусть B — произвольная булева алгебра.
Элемент (b1 , . . . , bn ) ∈ B n называется решением уравнения
(p, q) в булевой алгебре B, если
pbB (b1 , . . . , bn ) = qbB (b1 , . . . , bn ).
Совокупность { (pi , qi ) | i = 1, m } образует систему из m
уравнений.
Решением системы называется общее решение всех уравнений
системы.
Уравнение (p, q) допустимо записывать в виде p = q.
Например, x01 x2 ∨ x3 = x1 (x2 ∨ x3 ) — булево уравнение в 2,
а (101) — его решение.

56 / 67

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

Эквивалентное преобразование булева уравнения
Теорема
Уравнения p = q и (p u q 0 ) t (p 0 u q) = 0 имеют одни и те же
решения.
Доказательство
Пусть B — булева алгебра и (b1 , . . . , bn ) ∈ B n .
Положим a = pbB (b1 , . . . , bn ) и b = qbB (b1 , . . . , bn ).
Тогда, с одной стороны,
a = b ⇒ (a u b 0 ) t (a 0 u b) = (a u a 0 ) t (a 0 u a) = 0 t 0 = 0,
а с другой —


a u b0 = 0
(a u b 0 ) t (a 0 u b) = 0 ⇒
⇒
a0 u b = 0

a u b0 = 0
⇒
⇒ a = b 00 ⇔ a = b .
a t b0 = 1

57 / 67

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

58 / 67

Эквивалентное преобразование системы булевых уравнений
По данной теореме система уравнений
{ (pi , qi ) | i = 1, . . . , m }.
эквивалентна единственному уравнению
m
G



(pi u q 0i ) t (p 0i u qi ) = 0

(∗).

i=1

Если решение ищется в алгебре 2, то выразив левую часть в
конъюнктивной форме, получим, что уравнение (∗) имеет
решение, когда хотя бы один из сомножителей принимает
значение 0 и, приравнивая их последовательно к 0, находят все
решения системы.

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

Решение системы булевы уравнений: пример
Решим в 2 систему { (x1 x2 , x1 x3 ∨ x2 ), (x1 ∨ x 02 , x3 ) }.
Перепишем систему в привычном виде

x1 x2
= x1 x3 ∨ x2 ,
x1 ∨ x 02 = x3 .
Она эквивалентна единственному уравнению
x1 x2 (x1 x3 ∨ x2 )0 ∨ (x1 x2 )0 (x1 x3 ∨ x2 ) ∨
∨ (x1 ∨ x 02 )x 03 ∨ (x1 ∨ x 02 )0 x3 = 0.
Преобразуя левую часть в КНФ, получим уравнение
(x1 ∨ x2 ∨ x 03 )(x 01 ∨ x 02 ∨ x 03 ) = 0.
Таким образом, решения рассматриваемой системы —
элементы (b1 , b2 , b3 ) ∈ 23 удовлетворяющие соотношениям
(b1 ∨ b2 ∨ b3 )(b1 ∨ b2 ∨ b3 ) = 0,
т.е. это (001) и (111).

59 / 67

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

60 / 67

Системы булевы уравнений в произвольной булевой алгебре
В общем случае, когда решение ищется не в простейшей, а в
произвольной булевой алгебре B 6= 2, то приведение
уравнения (∗) к конъюнктивной форме приводит к потере
решений в силу того, что B не обладает свойством
полиномиальной полноты, и в ней
из a u b = o не следует, что либо a = o, либо b = o.

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

61 / 67

Выкладки в булевой структуре h B, t, u, 0 , v, o, ι i
1. a u x = 0 ⇔ (a u x) t a 0 = a 0 ⇔ (a t a 0 ) u (x t a 0 ) = a 0 ⇔
⇔ x t a 0 = a 0 ⇔ x v a 0 ( ⇔ a v x 0 ).
Аналогично b u x 0 = 0 ⇔ b v x.

2.



bvx
x v a0


⇔

x = b t u для некоторого u ∈ B
x u a0 = x

⇔

⇔ x = (b t u) u a 0 ⇔
⇔ x = (a 0 u u) t b.

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

Решение булева уравнения c одним неизвестным в
произвольной булевой алгебре
Пусть в булевой структуре h B, t, u, 0 , v, o, ι i задано
уравнение p = q , где p, q ∈ P1 .
Метод состоит в выполнении следующих шагов.
1

Приводим данное уравнение к равносильному уравнению с
o в правой части.

2

Приводим полученное уравнение к равносильному
уравнению вида (a u x) t (b u x 0 ) = o, где a и b —
известные элементы B.

3

Заменяем полученное уравнение на эквивалентную систему
a u x = o,
b u x 0 = o.

4

Если b 6v a 0 , то исходное уравнение решения не имеет.
Иначе, искомое решение — x такой, что
b v x v a 0 или x = (b t u) u a 0 = (a 0 u u) t b,
где u — произвольный элемент B.

62 / 67

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

Решение булева уравнения x t c = d
Решим булево уравнение
xtc = d
в произвольной булевой структуре h B, t, u, 0 , v, o, ι i.
1

x t c = d ⇔ ((x t c)0 u d) t ((x t c) u d 0 ) = o.

2

((xtc)0 ud) t ((xtc)ud 0 ) = (x 0 uc 0 ud) t (xud 0 ) t (cud 0 ) =
= (x 0 u c 0 u d 0 ) t (x u d 0 ) t (x u c u d 0 ) t (x 0 u c u d 0 ) =
= (x u (d 0 t (c u d 0 ))) t (x 0 u ((c 0 u d) t (c u d 0 ))) = o.
|
{z
}
d0

3

Имеем d 0 u x = o ,

((c 0 u d) t (c u d) 0 ) u x 0 = o.

63 / 67

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

64 / 67

Решение булева уравнения x t c = d ...
4

Исходное уравнение имеет решение если и только если
(c 0 u d) t (c u d 0 ) v d.
Покажем, что данное условие эквивалентно c v d:
((c 0 u d) t (c u d 0 )) v d ⇔ (c 0 ud) t (cud 0 ) t d = d ⇔
⇔ d t (c u d 0 ) = d ⇔ (d t (c u d 0 )) u c = d u c ⇔
⇔ (c u d) t (c u d 0 ) = d u c ⇔ c = c u d ⇔ c v d .

Общее решение исходного уравнения —
x = (c 0 u d) t (c u d 0 ) t u) u d = (c 0 u d) t (u u d) = d u (c 0 t u),
где u — произвольный элемент булевой структуры B.
Необязательная проверка:
Dtr2

cvd

(d u (c 0 t u)) t c = (d t c) u ι = d t c = d.

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

Разделы

1

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

2

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

3

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

4

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

5

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

6

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

65 / 67

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

Булева алгебра как решётка. Соотношения в булевой
алгебре. Булева алгебра отображений. Булев
гомоморфизм.
Булевы кольца. Теоремы построения булева кольца из
булевой алгебры и булевой алгебры из булева
кольца. Стоуновская двойственность между булевыми
алгебрами и булевыми кольцами. Булева структура.
Булевы идеалы и фильтры: определение. Фильтр Фреше.
Максимальные идеалы и фильтры. Ультрафильтр.
Свойства максимальных булевых идеалов и фильтров.
Факторалгебры.
Построение безатомной булевой алгебры факторизацией.
Тривиальные ультрафильтры. Общее решение булева
уравнения — ультрафильтр. Построение неглавного
ультрафильтра.

66 / 67

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

Булевы многочлены: определение, равенство,
полиномиальная функция, эквивалентность. Теорема:
n
PBn — подалгебра B B . Полиномиальная полнота булевой
алгебры.
Теорема об эквивалентном преобразовании булевых
уравнений. Решение булева уравнения в произвольной
булевой алгебре.

67 / 67