Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


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


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

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


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


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


[math]\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}[/math]

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


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




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


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


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


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


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




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


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


[math]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},[/math]

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


[math]\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}[/math]

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




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


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


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


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

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


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


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


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


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


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


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


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

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


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


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


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


[math]x+\overline{x}=\bold{1},[/math]
(3.29)

[math]x\cdot \overline{x}=\bold{0}.[/math]
(3.30)

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


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


[math]\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}[/math]



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


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


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


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


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


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

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


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

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


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


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

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


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


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

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


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

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


[math]\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}[/math]

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


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


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


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

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

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

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




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


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


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


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

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


[math]\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}[/math]

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


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


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

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


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

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


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


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


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

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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved