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

Дистрибутивная ограниченная решетка , в которой для каждого элемента соответствует дополнение, называется булевой алгеброй.

Примеры.

1. - булева алгебра (алгебра Кантора) множеств. 1 =U, 0= .

Здесь - операции пересечения объединения и дополнения над множествами.

2. - булева алгебра двоичных векторов длины n.

Здесь B_n – множество всех двоичных векторов длины n, то есть

,

где B = {0,1}, - операции логического (компонентного) умножения, сложения и дополнения соответственно, определяемые следующим образом: для произвольных векторов и :

а) , при этом

;

б)

при этом .

в) , где .

2. Пусть U = {a} – одноэлементное множество. Переобозначим U – через 1, а – через 0; мы получим простейшую булеву алгебру <Р({a}), >, операции в которой задаются следующими таблицами:

	0	1			0	1
0	0	0		0	0	1		0	1	–
1	0	1		1	1	1		1	0	–

Читать такую таблицу надо так: на пересечении строки и столбца стоит результат указанной операции, проведенной над упорядоченной парой (а,b). Так, из таблиц видно, что

; ; и т.д.

Замечание: по определению булева алгебра есть ограниченная решетка, значит, она имеет нуль 0 и единицу 1. Так как для любого элемента а М существует его дополнение , то и . Таким образом булеву алгебру можно представить в виде алгебры <М, > с двумя двухместными операциями пересечения и объединения , одноместной операцией дополнения и двумя константами 0 и 1.

Оказывается, что основные свойства операций рассмотренные ранее, выполняются в булевой алгебре. Свойства булевой алгебры:

1. Закон идемпотентности

по определению решетки;

2. Коммутативность операций и :

по определению решетки;

3. Ассоциативность операций и :

по определению решетки;

4. Законы поглощения:

по определению решетки;

5. Законы дистрибутивности:

по свойству дистрибутивности;

6. Законы нуля и единицы:

по свойству ограниченности;

7.

по следствию из теоремы об ограниченности;

8. Закон двойного отрицания

по теореме о свойствах дополнения;

9. Законы де Моргана:

по теореме о свойствах дополнения;

10.

так как дополнение существует.

Теорема (Стоун): Любая конечная булева алгебра изоморфна некоторой алгебре Кантора.

Так как для любого множества U мощность множества P(U)равна , то из теоремы Стоуна вытекает важное следствие.

Следствие: Любые две булевы алгебры, имеющие одинаковое число элементов, изоморфны. Число элементов конечной булевой алгебры равно для некоторого n N.

Таким образом, конечная булева алгебра определяется однозначно с точностью до изоморфизма числом своих элементов.

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

Задачи для самостоятельного решения

1. Дана алгебра < 0,+, >, где 0+0=0; . Выяснить, является ли она кольцом, телом, полем.

2. Доказать, что всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента.

3. Построить пример частично упорядоченного множества, имеющего точно один минимальный элемент, но не имеющего наименьшего элемента.

4. Показать, что любое конечное множество можно линейно упорядочить.

5. Доказать, что любое линейно упорядоченное множество есть решетка.

6. Привести примеры решеток:

а) без наибольшего элемента, но с наименьшим элементом;

б) без наименьшего элемента, но с наибольшим элементом;

в) без наибольшего и без наименьшего элемента.

7. Доказать, что алгебра подмножеств, упорядоченная включением, есть булева алгебра.

8. Для изображенных ниже решеток определите, какие из них:

а) дистрибутивны,

б) с дополнением,

в) булевы

9. Установить, образуют ли алгебры следующие системы:

1. < N, +, − >, б) < Z, :,∙>, в) < R,∙,−1, 1−2i >

10. Обозначим через F множество функций, действующих на множестве А. Образует ли система < F; >:

а) полугруппу, б) моноид, в) группу?

11.Построить изоморфизм систем

<{1,2,3,4},{(1,3),(1,4),(2,4),(3,2)}> и <{a,b,c,d},{(b,a),(c,b),(c,d),(d,a)}>.

Построить все гомоморфные образы указанных систем.

12. Построить все возможные попарно неизоморфные группы с двухэлементным носителем.

13. Дана алгебра U=<{a,b,c,d},∙> определенная следующей таблицей Кэли:

∙	a b c d
a	a a b a
b	c d a b
c	a c d d
d	d a d a

Имеет ли алгебра U подалгеб ру c носителем

а) {a,b,c}; б){a}; в){a,d}?

14. Доказать, что в решетке максимальный элемент является наибольшим, а минимальный – наименьшим элементом.

15. Построить булеву алгебру подмножеств трехэлементного (четырехэлементного) множества.