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

переменных
является подалгеброй алгебры 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 --">