Булевы алгебры
ТеорияТеория булевых алгебр является классическим разделом дискретной математики. Булевы алгебры возникли в трудах английского математика Дж. Буля в 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.
в. Полукольцо SA (см. пример З.З.б) симметрично в силу известных свойств операций пересечения и объединения множеств.
г. Полукольцо RA (cm. пример З.З.в) не является симметричным.
д. Полукольцо S[a,b] (см. пример З.З.г) симметрично.
Пример 3.9. Рассмотрим алгебру
Dn = (Дел(n), НОК,НОД, 1, n),
где Дел(n) — множество всех делителей натурального числа n; НОК — операция вычисления наименьшего общего кратного; НОД — операция вычисления наибольшего общего делителя двух чисел. Эта алгебра является симметричным полукольцом.
Действительно, для любых двух натуральных чисел m и р верно представление
m = 2α13α2...pαkk и р = 2β13β2...pβkk,
где pk — наибольший простой множитель в разложении m и р.
Тогда
НОК(m,р) = 2max(α1,β1)3max(α2,β2)...pmax(αn,βn)k ,
НОК(m,р) = 2min(α1,β1)3min(α2,β2)...pmin(α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 определим структуру булевой алгебры, положив для произвольных α˜ = (α1, ..., аn), β = (β1, ...,βn) из {0,1}n, что
α˜ ∨ β˜ = (α1 ∨ β1, ..., αn ∨ βn),
α˜ ∧ β˜ = (α1 ∧ β1, ..., αn ∧ βn),
0 = (0, ..., 0),
1 = (1, ..., 1).
Можно без труда показать, что все аксиомы булевой алгебры выполняются. Носитель определенной таким образом булевой алгебры называют булевым кубом размерности n, а его элементы — булевыми векторами (или булевыми наборами) размерности n. Вектор 0 называют при этом нулевым булевым вектором или нулевым набором, а вектор 1 — единичным булевым вектором или единичным набором. Заметим, что случаи n = 0 и n = 1 включаются в эту конструкцию. При n = 1 получаем уже рассмотренную двухэлементную булеву алгебру В, а при n = 0 — так называемую одноэлементную булеву алгебру, в которой 0 = 1. Но эта структура малоинтересна.
Итак, булевы операции над булевыми векторами выполняются покомпонетно — так же, как сложение векторов или умножение вектора на число в линейной алгебре. Отношение порядка здесь определено также покомпонентно, т.е. для произвольных α˜ = (α1, ..., αn), β˜ = (β1, ..., βn) ∈ {0,1}n неравенство α˜ ≤ β˜ означает, что α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. Полукольцо Sa (см. пример 3.3.б) — булева алгебра, в которой все булевы операции суть не что иное, как обычные теоретико-множественные операции, т.е. булево объединение есть обычное объединение множеств, булево пересечение — пересечение множеств, булево дополнение — дополнение множества.
Пример 3.13. а. Рассмотрим полукольцо D6 делителей числа 6 с операциями НОК и НОД. Из примера 3.9 следует, что это полукольцо симметричное. Нуль этого полукольца есть число 1, а единица — число 6. Убедимся, что каждый элемент полукольца имеет дополнение. Начнем с числа 1. Дополнение х должно удовлетворять равенствам 1 ∨ х = 6 и 1 ∧ x = 1. Первое равенство означает, что НОК(1,x) = 6, а второе — НОД(1,x) = = 1. Легко видеть, что х = 1 = 6. Рассуждая аналогично, получим 2 = 3. Следовательно, рассматриваемое полукольцо есть булева алгебра.
б. Полукольцо D12 делителей числа 12 не является булевой алгеброй, так как, например, из 2 ∨ х = НОК(2,x) = 12 = 1 следует, что х = 12, но 2 ∧ 12 = НОДB(2,12) = 2 ≠ 1 = 0, и элемент 2 не имеет дополнения. #
Теория булевых алгебр имеет многочисленные приложения: в математической логике, в теории вероятностей. Она позволяет, в частности, рассматривать с единой точки зрения операции над множествами, над высказываниями, над случайными событиями. В этой книге мы используем изложенные здесь факты в главе, посвященной булевым функциям.