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

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

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

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


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

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


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


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


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


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

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


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


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


\begin{aligned} \mathit{Table~3.3}~&\\ \begin{array}{|r|l||r|l|}\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}& \end{aligned}

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


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




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


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


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


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


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




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


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


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},

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


\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}

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




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


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


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


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

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


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


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


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


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


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


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


xy=\inf\{x,y\}.

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


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


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


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


x+\overline{x}=\bold{1},
(3.29)

x\cdot \overline{x}=\bold{0}.
(3.30)

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


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


\begin{aligned} \mathit{Table~3.4}~&\\ \begin{array}{|r|l||r|l|} \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} \end{aligned}



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


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


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


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


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


a=(a\lor x)\land (a\lor \overline{x})= \bold{1}\land (a\lor \overline{x}).

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


a=(x\lor \overline{x})\land (a\lor \overline{x})= (x\land a)\lor \overline{x}.

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


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


\overline{\overline{x}}=x\,.

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


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


\overline{x\lor y}= \overline{x}\land \overline{y},\qquad \overline{x\land y}= \overline{x}\lor \overline{y}\,.
(3.31)

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


(\overline{x}\land \overline{y})\lor (x\lor y)=\bold{1} и (\overline{x}\land \overline{y})\land (x\lor y).

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


\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}

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


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


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


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

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


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

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




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


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


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


\overline{0}=1,\qquad \overline{1}=0.

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


\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}

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


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


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

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


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

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


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


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


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

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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