Булевы алгебры

^Теория

Теория булевых алгебр является классическим разделом дискретной математики. Булевы алгебры возникли в трудах английского математика Дж. Буля в 50-х годах XIX века как аппарат логики. При этом элементы булевой алгебры трактовались как высказывания, а операциями являлись дизъюнкция, конъюнкция и отрицание.

Существуют различные подходы к определению булевой алгебры. Мы определим булеву алгебру как частный случай идемпотентного полукольца.

Определение 3.3. Полукольцо S = S, +, ⋅, 0, 1) называют симметричным (или взаимным), если оно идемпотентно и в нем выполнены следующие тождества:

а ⋅ а = а ( идемпотентность операции умножения полукольца);
а ⋅ b = b ⋅ а (коммутативность операции умножения полукольца);
а + (b ⋅ с) = (а + b) ⋅ (а + с) (дистрибутивность операции сложения полукольца относительно умножения);
1 + а = 1 (аннулирующее свойство единицы полукольца относительно сложения).

Можно дать определение, равносильное определению 3.3. Идемпотентное полукольцо S = E, +, ⋅, 0, 1) называется сим- симметричным (или взаимным), если алгебра Sf = E, •, +, 1, 0) также является идемпотентным полукольцом. При этом будем говорить, что идемпотентное полукольцо S' есть полукольцо, двойственное к идемпотентному полукольцу S.

Из определения следует, что в двойственном идемпотентном полукольце операция сложения — это операция умножения в исходном полукольце и наоборот; нуль двойственного полукольца — это единица исходного полукольца и наоборот. Легко видеть, что полукольцо S", двойственное к двойственному полукольцу S', есть исходное полукольцо S.

Запишем полностью все аксиомы (основные тождества) симметричного полукольца, объединяя двойственные аксиомы в пары (табл. 3.3).

В табл. 3.1 можно увидеть, что в симметричном полукольце операции сложения и умножения, равно как и элементы 0 и 1, полностью „взаимозаменяемые", или взаимно двойственные.

Таким образом, справедлив принцип двойственности для симметричных полуколец: любое тождество в симметричном полукольце остается верным, если в нем операцию сложения заменить операцией умножения и наоборот, а единицу заменить нулем и наоборот.

Пример 3.8. а. Полукольцо В (см. пример 3.2) симметричное.

б. Полукольцо R⁺ (см. пример 3.1) не является симметричным в силу неидемпотентности умножения полукольца, хотя в нем единица полукольца (число 0) имеет аннулирующее свойство, поскольку min(0, x) = 0.

в. Полукольцо S_A (см. пример З.З.б) симметрично в силу известных свойств операций пересечения и объединения множеств.

г. Полукольцо R_A (cm. пример З.З.в) не является симметричным.

д. Полукольцо S_[a,b] (см. пример З.З.г) симметрично.

Пример 3.9. Рассмотрим алгебру

D_n = (Дел(n), НОК,НОД, 1, n),

где Дел(n) — множество всех делителей натурального числа n; НОК — операция вычисления наименьшего общего кратного; НОД — операция вычисления наибольшего общего делителя двух чисел. Эта алгебра является симметричным полукольцом.

Действительно, для любых двух натуральных чисел m и р верно представление

m = 2^α₁3^α₂...p^α_kk и р = 2^β₁3^β₂...p^β_kk,

где p_k — наибольший простой множитель в разложении m и р.

Тогда

НОК(m,р) = 2^{max(α₁,β₁)}3^{max(α₂,β₂)}...p^{max(α_n,β_n)k} ,

НОК(m,р) = 2^{min(α₁,β₁)}3^{min(α₂,β₂)}...p^{min(α_n,β_n)k}

Таким образом, свойства операций НОК и НОД определяются свойствами операций max и min. В силу этого рассматриваемая алгебра и является симметричным полукольцом (см. пример 3.3.г). #

Рассмотрим некоторые свойства симметричного полукольца, вытекающие из его аксиом.

Свойство 3.1. Для любых элементов симметричного полукольца выполняются равенства

x(x+y) = x, x+xy=x.

◀ Имеем х(х + у) = хх + ху = х + ху = х(1 + у) = х⋅1 = x. ▶

Равенства, приведенные в формулировке свойства 3.1, называют тождествами поглощения.

Свойство 3.2. В симметричном полукольце неравенство х ≤ у имеет место тогда и только тогда, когда ху = х.

◀ Вспомним, что по определению естественного порядка произвольного идемпотентного полукольца х ≤ у ⇔ х + у = у.

Пусть х ≤ у. Тогда ху = х(х + у) = х (по свойству 3.1).

Пусть теперь ху = х. Тогда х + у = ху + у = у. Следовательно, х ≤ у. >

Свойство 3.2 выражает связь умножения с естественным порядком идемпотентного полукольца: меньший сомножитель поглощает больший, т.е. порядок в двойственном полукольце S 'является порядком, двойственным к порядку в полукольце S. Но, как известно, при переходе к двойственному порядку наибольший (максимальный) элемент становится наименьшим (минимальным) элементом, а точная верхняя грань — точной нижней гранью.

Свойство 3.3. В симметричном полукольце произведение ху есть точная нижняя грань последовательности {x, у}:

xy = inf{x,y}

Свойство 3.4. Для любого элемента х симметричного полукольца имеет место неравенство 0 ≤ х ≤ 1.

◀ Первое неравенство 0 ≤ х равносильно равенству 0 + х = x, верному для любого х. Второе неравенство х ≤ 1 вытекает из четвертого тождества определения 3.3. ▶

Таким образом, в симметричном полукольце единица (1) является наибольшим элементом.

Определение 3.4. Булева алгебра — это симметричное полукольцо, в котором для каждого х существует элемент x, называемый дополнением х, такой, что

x + x = 1 (3.29)

x ⋅ x = 0 (3.30)

Обычно сложение в булевой алгебре называют булевым объединением и обозначают ∨, а умножение — булевым пересечением и обозначают ∧.

Запишем аксиомы булевой алгебры в виде табл. 3.4, объединяя „двойственные пары" (как это мы уже сделали, записывая аксиомы симметричного идемпотентного полукольца).

Рассмотрим некоторые важные свойства булевых алгебр, вытекающие из определения.

Свойство 3.5 (единственность дополнения). В булевой алгебре для любого х его дополнение x единственное.

◀ Пусть для элемента х найдется еще одно такое a, что а ∧ х = 0 и a ∨ x = 1

Имеем a = a ∨ O. Воспользовавшись свойством (3.29), получим a = a ∨ (х ∧ x). В силу дистрибутивности и с учетом свойств элемента а имеем a = (a ∨ х) ∧ (а ∨ x) = 1 ∧ (а ∨ x). С учетом свойств дополнения преобразуем последнее выражение следующим образом: a = (х ∨ x) ∧ (а ∨ x) = (х ∧ а) ∨ x. Поскольку x ∧ а = 0, то а = 0 ∨ x = x. Таким образом, элемент а совпадает с дополнением х. ▶

Свойство 3.6 („симметричность" операции дополнения). В булевой алгебре выполняется тождество

Свойство 3.7. В булевой алгебре верны следующие тождества:

x ∨ y = x ∧ y, x ∨ y = x ∨ y. (3.31)

◀ В силу свойств 3.5 и 3.6 для доказательства первого закона достаточно показать, что (x ∧ y) ∨ (x ∨ у) = 1 и (x ∧ y) ∧ (х ∨ у) = 0.

Преобразуя выражения в левых частях, получаем

(x ∧ y) ∨ (x ∨ у) = (x ∨ x ∨ у) ∧ (y ∨ x ∨ у) = 1 ∧ 1 = 1,

(x ∧ y) ∧ (x ∨ у) = (x ∧ x ∧ у) ∨ (x ∧ y ∧ у) = 0 ∨ 0 = 0.

Первое тождество доказано. Второе тождество следует из принципа двойственности. ▶

Тождества (3.31) называют законами де Моргана.

Единственность дополнения означает, что в булевой алгебре возникает унарная операция — переход от элемента к его дополнению. Эту операцию можно ввести в сигнатуру алгебры, т.е. рассматривать булеву алгебру как алгебру вида

В = (В, ∨, ∧, , 0, 1)

с двумя бинарными, одной унарной и двумя нульарными операциями, такую, что:

(В, ∨, ∧, 0, 1) — симметричное полукольцо;
а ∨ а = 1 и а ∧ а = 0 (для любого а).

Дополнение в булевой алгебре называют булевым дополнением, а все операции булевой алгебры — булевыми операциями.

Рассмотрим теперь некоторые примеры булевых алгебр.

Пример 3.10. Полукольцо В (см. пример 3.2) является булевой алгеброй. Эта булева алгебра — важнейшая структура. Мы назовем ее двухэлементной булевой алгеброй и обозначим В. Видно, что в В

0 = 1, 1 = 0.

Пример 3.11. На множестве {0,1}ⁿ определим структуру булевой алгебры, положив для произвольных α˜ = (α₁, ..., а_n), β = (β₁, ...,β_n) из {0,1}ⁿ, что

α˜ ∨ β˜ = (α₁ ∨ β₁, ..., α_n ∨ β_n),

α˜ ∧ β˜ = (α₁ ∧ β₁, ..., α_n ∧ β_n),

0 = (0, ..., 0),

1 = (1, ..., 1).

Можно без труда показать, что все аксиомы булевой алгебры выполняются. Носитель определенной таким образом булевой алгебры называют булевым кубом размерности n, а его элементы — булевыми векторами (или булевыми наборами) размерности n. Вектор 0 называют при этом нулевым булевым вектором или нулевым набором, а вектор 1 — единичным булевым вектором или единичным набором. Заметим, что случаи n = 0 и n = 1 включаются в эту конструкцию. При n = 1 получаем уже рассмотренную двухэлементную булеву алгебру В, а при n = 0 — так называемую одноэлементную булеву алгебру, в которой 0 = 1. Но эта структура малоинтересна.

Итак, булевы операции над булевыми векторами выполняются покомпонетно — так же, как сложение векторов или умножение вектора на число в линейной алгебре. Отношение порядка здесь определено также покомпонентно, т.е. для произвольных α˜ = (α₁, ..., α_n), β˜ = (β₁, ..., β_n) ∈ {0,1}ⁿ неравенство α˜ ≤ β˜ означает, что α_i ≤ β_i, i = 1,n Так, например,

(0, 1, 0, 0, 1) ≤ (1, 1, 0, 0, 1),

а векторы (0, 1, 0, 0, 1) и (0, 1, 0, 0, 0) не сравнимы.

Пример 3.12. Полукольцо S_a (см. пример 3.3.б) — булева алгебра, в которой все булевы операции суть не что иное, как обычные теоретико-множественные операции, т.е. булево объединение есть обычное объединение множеств, булево пересечение — пересечение множеств, булево дополнение — дополнение множества.

Пример 3.13. а. Рассмотрим полукольцо D₆ делителей числа 6 с операциями НОК и НОД. Из примера 3.9 следует, что это полукольцо симметричное. Нуль этого полукольца есть число 1, а единица — число 6. Убедимся, что каждый элемент полукольца имеет дополнение. Начнем с числа 1. Дополнение х должно удовлетворять равенствам 1 ∨ х = 6 и 1 ∧ x = 1. Первое равенство означает, что НОК(1,x) = 6, а второе — НОД(1,x) = = 1. Легко видеть, что х = 1 = 6. Рассуждая аналогично, получим 2 = 3. Следовательно, рассматриваемое полукольцо есть булева алгебра.

б. Полукольцо D₁₂ делителей числа 12 не является булевой алгеброй, так как, например, из 2 ∨ х = НОК(2,x) = 12 = 1 следует, что х = 12, но 2 ∧ 12 = НОДB(2,12) = 2 ≠ 1 = 0, и элемент 2 не имеет дополнения. #

Теория булевых алгебр имеет многочисленные приложения: в математической логике, в теории вероятностей. Она позволяет, в частности, рассматривать с единой точки зрения операции над множествами, над высказываниями, над случайными событиями. В этой книге мы используем изложенные здесь факты в главе, посвященной булевым функциям.