Булевы алгебры и полукольца

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

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

Определение 3.3. Полукольцо [cbm]\mathcal{S}=(S,+,\cdot,\bold{0},\bold{1})[/cbm] называют симметричным (или взаимным), если оно идемпотентно и в нем выполнены следующие тождества:

1) [cbm]a\cdot a=a[/cbm] (идемпотентность операции умножения полукольца);
2) [cbm]a\cdot b=b\cdot a[/cbm] (коммутативность операции умножения полукольца);
3) [cbm]a+(b\cdot c)=(a+b)\cdot(a+c)[/cbm] (дистрибутивность операции сложения полукольца относительно умножения);
4) [cbm]\bold{1}+a=\bold{1}[/cbm] (аннулирующее свойство единицы полукольца относительно сложения).

Можно дать определение, равносильное определению 3.3. Идемпотентное полукольцо [cbm]\mathcal{S}=(S,+,\cdot,\bold{0},\bold{1})[/cbm] называется симметричным (или взаимным), если алгебра [cbm]\mathcal{S}'=(S,\cdot,+,\bold{0},\bold{1})[/cbm] также является идемпотентным полукольцом. При этом будем говорить, что идемпотентное полукольцо [cbm]\mathcal{S}'[/cbm] есть полукольцо, двойственное к идемпотентному полукольцу [cbm]\mathcal{S}[/cbm] .

Из определения следует, что в двойственном идемпотентном полукольце операция сложения — это операция умножения в исходном полукольце и наоборот; нуль двойственного полукольца — это единица исходного полукольца и наоборот. Легко видеть, что полукольцо [cbm]\mathcal{S}''[/cbm] , двойственное к двойственному полукольцу [cbm]\mathcal{S}'[/cbm] , есть исходное полукольцо [cbm]\mathcal{S}[/cbm] .

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

[cbm]\begin{array}{|r|l||r|l|}\multicolumn{4}{r}{\mathit{Table~3\!.3}} \\\hline & \text{Axiom} & & \text{Axiom} \\\hline \scriptstyle{\mathsf{1}}& a+(b+c)=(a+b)+c & \scriptstyle{\mathsf{7}}& a\cdot (b\cdot c)=(a\cdot b)\cdot c \\ \scriptstyle{\mathsf{2}}& a+b=b+a & \scriptstyle{\mathsf{8}}& a\cdot b=b\cdot a\\ \scriptstyle{\mathsf{3}}& a+a=a & \scriptstyle{\mathsf{9}}& a\cdot a=a\\ \scriptstyle{\mathsf{4}}& a+\bold{0}=a & \scriptstyle{\mathsf{10}}& a\cdot \bold{1}=a\\ \scriptstyle{\mathsf{5}}& a\cdot (b+c)=(a\cdot b)+(a\cdot c) & \scriptstyle{\mathsf{11}}& a+(b\cdot c)=(a+b)\cdot (a+c)\\ \scriptstyle{\mathsf{6}}& a\cdot\bold{0}=\bold{0} & \scriptstyle{\mathsf{12}}& a+\bold{1}=\bold{1}\\\hline \end{array}[/cbm]

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

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


Пример 3.8. а. Полукольцо [cbm]\mathcal{B}[/cbm] (см. пример 3.2) симметричное.

б. Полукольцо [cbm]\mathcal{R}^{+}[/cbm] (см. пример 3.1) не является симметричным в силу неидемпотентности умножения полукольца, хотя в нем единица полукольца (число 0) имеет аннулирующее свойство, поскольку [cbm]\min(0,x)=0[/cbm] .

в. Полукольцо [cbm]\mathcal{S}_A[/cbm] (см. пример 3.3,б) симметрично в силу известных свойств операций пересечения и объединения множеств.

г. Полукольцо [cbm]\mathcal{R}_A[/cbm] (см. пример 3.3,в) не является симметричным.

д. Полукольцо [cbm]\mathcal{S}_{[a;b]}[/cbm] (см. пример З.З,г) симметрично.


Пример 3.9. Рассмотрим алгебру [cbm]\mathcal{D}=\bigl(\operatorname{dev}(n), \operatorname{lcm},\gcd,1,n\bigr)[/cbm] , где [cbm]\operatorname{dev}(n)[/cbm] — множество всех делителей натурального числа [cbm]n[/cbm] ; [cbm]\operatorname{lcm}[/cbm] — операция вычисления наименьшего общего кратного; [cbm]\gcd[/cbm] — операция вычисления наибольшего общего делителя двух чисел. Эта алгебра является симметричным полукольцом.

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

[cbm]m=2^{\alpha_1}\cdot 3^{\alpha_2}\cdot \ldots\cdot p_{k}^{\alpha_k},\qquad p=2^{\beta_1}\cdot 3^{\beta_2}\cdot \ldots\cdot p_{k}^{\beta_k},[/cbm]

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

[cbm]\begin{aligned}&\operatorname{lcm}(m,p)= 2^{\max(\alpha_1,\beta_1)}\cdot 3^{\max(\alpha_2,\beta_2)}\cdot \ldots\cdot p_{k}^{\max(\alpha_n,\beta_n)},\\[2pt] &\gcd(m,p)= 2^{\min(\alpha_1,\beta_1)}\cdot 3^{\min(\alpha_2,\beta_2)}\cdot \ldots\cdot p_{k}^{\min(\alpha_n,\beta_n)}.\end{aligned}[/cbm]

Таким образом, свойства операций [cbm]\operatorname{lcm}[/cbm] и [cbm]\gcd[/cbm] определяются свойствами операций [cbm]\max[/cbm] и [cbm]\min[/cbm] . В силу этого рассматриваемая алгебра и является симметричным полукольцом (см. пример 3.3,г).


Свойства симметричного полукольца

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

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

[cbm]x(x+y)=x,\qquad x+xy=x[/cbm] . Имеем [cbm]x(x+y)=xx+xy=x+xy=x(\bold{1}+y)=x\cdot \bold{1}=x[/cbm] .

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

Свойство 3.2. В симметричном полукольце неравенство [cbm]x\leqslant y[/cbm] имеет место тогда и только тогда, когда [cbm]xy=x[/cbm] .

Вспомним, что по определению естественного порядка произвольного идемпотентного полукольца [cbm]x\leqslant y\Leftrightarrow x+y=y[/cbm] .

Пусть [cbm]x\leqslant y[/cbm] . Тогда [cbm]xy=x(x+y)=x[/cbm] (по свойству 3.1).

Пусть теперь [cbm]xy=x[/cbm] . Тогда [cbm]x+y=xy+y=y[/cbm] . Следовательно, [cbm]x\leqslant y[/cbm] .

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

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

[cbm]xy=\inf\{x,y\}.[/cbm]

Свойство 3.4. Для любого элемента [cbm]x[/cbm] симметричного полукольца имеет место неравенство [cbm]\bold{0}\leqslant x\leqslant\bold{1}[/cbm] .

Первое неравенство [cbm]\bold{0}\leqslant x[/cbm] равносильно равенству [cbm]\bold{0}+x=x[/cbm] , верному для любого [cbm]x[/cbm] . Второе неравенство [cbm]x\leqslant\bold{1}[/cbm] вытекает из четвертого тождества определения 3.3.

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

Определение 3.4. Булева алгебра — это симметричное полукольцо, в котором для каждого [cbm]x[/cbm] существует элемент [cbm]\overline{x}[/cbm] , называемый дополнением [cbm]x[/cbm] , такой, что

[cbm]x+\overline{x}=\bold{1},[/cbm]
(3.29)
[cbm]x\cdot \overline{x}=\bold{0}.[/cbm]
(3.30)

Обычно сложение в булевой алгебре называют булевым объединением и обозначают [cbm]\lor[/cbm] , а умножение — булевым пересечением и обозначают [cbm]\land[/cbm] .

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

[cbm]\begin{array}{|r|l||r|l|}\multicolumn{4}{r}{\mathit{Table~3\!.4}} \\\hline & \text{Axiom} & & \text{Axiom} \\\hline \scriptstyle{\mathsf{1}}& a\lor (b\lor c)=(a\lor b)\lor c & \scriptstyle{\mathsf{8}}& a\land (b\land c)=(a\land b)\land c \\ \scriptstyle{\mathsf{2}}& a\lor b=b\lor a & \scriptstyle{\mathsf{9}}& a\land b=b\land a\\ \scriptstyle{\mathsf{3}}& a\lor a=a & \scriptstyle{\mathsf{10}}& a\land a=a\\ \scriptstyle{\mathsf{4}}& a\lor \bold{0}=a & \scriptstyle{\mathsf{11}}& a\land \bold{1}=a\\ \scriptstyle{\mathsf{5}}& a\land (b\lor c)=(a\land b)\lor (a\land c) & \scriptstyle{\mathsf{12}}& a\lor (b\land c)=(a\lor b)\land (a\lor c)\\ \scriptstyle{\mathsf{6}}& a\land \bold{0}=\bold{0} & \scriptstyle{\mathsf{13}}& a\lor \bold{1}=\bold{1}\\ \scriptstyle{\mathsf{7}}& a\lor \overline{a}=\bold{1} & \scriptstyle{\mathsf{14}}& a\land \overline{a}=\bold{0}\\\hline \end{array}[/cbm]

Свойства булевых алгебр

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

Свойство 3.5 (единственность дополнения). В булевой алгебре для любого [cbm]x[/cbm] его дополнение [cbm]\overline{x}[/cbm] единственное.

Пусть для элемента [cbm]x[/cbm] найдется еще одно такое [cbm]a[/cbm] , что [cbm]a\land x=\bold{0}[/cbm] и [cbm]a\lor x=\bold{1}[/cbm] .

Имеем [cbm]a=a\lor\bold{0}[/cbm] . Воспользовавшись свойством (3.29), получим [cbm]a=a\lor(x\land\overline{x})[/cbm] . В силу дистрибутивности и с учетом свойств элемента [cbm]a[/cbm] имеем

[cbm]a=(a\lor x)\land (a\lor \overline{x})= \bold{1}\land (a\lor \overline{x}).[/cbm]

С учетом свойств дополнения преобразуем последнее выражение следующим образом:

[cbm]a=(x\lor \overline{x})\land (a\lor \overline{x})= (x\land a)\lor \overline{x}.[/cbm]

Поскольку [cbm]x\land a=\bold{0}[/cbm] , то [cbm]a=\bold{0}\lor \overline{x}= \overline{x}[/cbm] . Таким образом, элемент [cbm]a[/cbm] совпадает с дополнением [cbm]x[/cbm] .

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

[cbm]\overline{\overline{x}}=x\,.[/cbm]

Так как [cbm]\overline{\overline{x}}[/cbm] является дополнением к [cbm]\overline{x}[/cbm] , то [cbm]\overline{\overline{x}}\land \overline{x}=\bold{0}[/cbm] и [cbm]\overline{\overline{x}}\lor \overline{x}= \bold{1}[/cbm] . В то же время [cbm]\overline{x}\land x=\bold{0}[/cbm] и [cbm]\overline{x}\lor\overline{x}=\bold{1}[/cbm] . В силу единственности дополнения к элементу [cbm]\overline{x}[/cbm] имеем [cbm]\overline{\overline{x}}=x[/cbm] .

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

[cbm]\overline{x\lor y}= \overline{x}\land \overline{y},\qquad \overline{x\land y}= \overline{x}\lor \overline{y}\,.[/cbm]
(3.31)

В силу свойств 3.5 и 3.6 для доказательства первого закона достаточно показать, что

[cbm](\overline{x}\land \overline{y})\lor (x\lor y)=\bold{1}[/cbm] и [cbm](\overline{x}\land \overline{y})\land (x\lor y)[/cbm] .

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

[cbm]\begin{aligned}(\overline{x}\land \overline{y})\lor (x\lor y)&= (\overline{x}\lor x\lor y)\land (\overline{y}\lor x\lor y)= \bold{1}\land \bold{1}=\bold{1},\\[2pt] (\overline{x}\land \overline{y})\land (x\lor y)&= (\overline{x}\land \overline{y}\land x)\lor (\overline{x}\land \overline{y}\land y)= \bold{0}\lor \bold{0}=\bold{0}. \end{aligned}[/cbm]

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

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

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

[cbm]\mathsf{B}=\bigl(B,\lor,\land,\overline{\phantom{A}},\bold{0},\bold{1}\bigr).[/cbm]

с двумя бинарными, одной унарной и двумя нульарными операциями, такую, что:
1) [cbm](B,\lor,\land,\bold{0},\bold{1})[/cbm] — симметричное полукольцо;
2) [cbm]a\lor \overline{a}=\bold{1}[/cbm] и [cbm]a\land \overline{a}=\bold{0}[/cbm] (для любого [cbm]a[/cbm] ).

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


Примеры булевых алгебр

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

Пример 3.10. Полукольцо [cbm]\mathcal{B}[/cbm] (см. пример 3.2) является булевой алгеброй. Эта булева алгебра — важнейшая структура. Мы назовем ее двухэлементной булевой алгеброй и обозначим [cbm]\mathbb{B}[/cbm] . Видно, что в [cbm]\mathbb{B}[/cbm]

[cbm]\overline{0}=1,\qquad \overline{1}=0.[/cbm]

Пример 3.11. На множестве [cbm]\{0;1\}^n[/cbm] определим структуру булевой алгебры, положив для произвольных [cbm]\widetilde{\alpha}= (\alpha_1,\ldots,\alpha_n),[/cbm] [cbm]\widetilde{\beta}=(\beta_1,\ldots,\beta_n)[/cbm] из [cbm]\{0;1\}^n[/cbm] , что

[cbm]\begin{aligned}& \widetilde{\alpha} \lor \widetilde{\beta}= (\alpha_1\lor \beta_1, \ldots, \alpha_n\lor\beta_n),\\ & \widetilde{\alpha} \land \widetilde{\beta}= (\alpha_1\land \beta_1,\ldots, \alpha_n \land\beta_n),\\ & \overline{\widetilde{\alpha}}= (\overline{\alpha}_1, \ldots,\overline{\alpha}_n),\\ & \bold{0}=(0,\ldots,0),\\ & \bold{1}=(1,\ldots,1). \end{aligned}[/cbm]

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

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

[cbm]\widetilde{\alpha}= (\alpha_1,\ldots,\alpha_n)\in\{0;1\}^n,\qquad \widetilde{\beta}= (\beta_1,\ldots,\beta_n)\in\{0;1\}^n[/cbm]

неравенство [cbm]\widetilde{\alpha}\leqslant \widetilde{\beta}[/cbm] означает, что [cbm]\alpha_i \leqslant \beta_i,~ i=\overline{1,n}[/cbm] . Так, например,

[cbm](0,1,0,0,1)\leqslant (1,1,0,0,1)[/cbm] , а векторы [cbm](0,1,0,0,1)[/cbm] и [cbm](1,1,0,0,1)[/cbm] не сравнимы.

Пример 3.12. Полукольцо [cbm]\mathcal{S}_A[/cbm] (см. пример 3.3.б) — булева алгебра, в которой все булевы операции суть не что иное, как обычные теоретико-множественные операции, т.е. булево объединение есть обычное объединение множеств, булево пересечение — пересечение множеств, булево дополнение — дополнение множества.

Пример 3.13. а. Рассмотрим полукольцо [cbm]\mathcal{D}_6[/cbm] делителей числа 6 с операциями [cbm]\operatorname{lcm}[/cbm] и [cbm]\gcd[/cbm] . Из примера 3.9 следует, что это полукольцо симметричное. Нуль этого полукольца есть число 1, а единица — число 6. Убедимся, что каждый элемент полукольца имеет дополнение. Начнем с числа 1. Дополнение х должно удовлетворять равенствам [cbm]1\lor x=6[/cbm] и [cbm]1\land x=1[/cbm] . Первое равенство означает, что [cbm]\operatorname{lcm}(1,x)=6[/cbm] , а второе — [cbm]\gcd(1,x)=1[/cbm] . Легко видеть, что [cbm]x=\overline{1}=6[/cbm] . Рассуждая аналогично, получим [cbm]\overline{2}=3[/cbm] . Следовательно, рассматриваемое полукольцо есть булева алгебра.

б. Полукольцо [cbm]\mathcal{D}_{12}[/cbm] делителей числа 12 не является булевой алгеброй, так как, например, из [cbm]2\lor x=\operatorname{lcm}(2,x)=12= \bold{1}[/cbm] следует, что [cbm]x=12[/cbm] , но

[cbm]2\land12= \gcd(2,12)=2\ne1=\bold{0}[/cbm] и элемент 2 не имеет дополнения.

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: