Тема 8.5.Булева алгебра и теория множеств

Ранее были описаны булевы алгебры множеств, то есть алгебры вида , где– булеан множества, то есть множество всех возможных его подмножеств. Общий термин «булева алгебра» для алгебр множеств и логических функций не является случайным. Всякая алгебра называется булевой алгеброй, если её операции удовлетворяют соотношениям, приведённым в пункте 8.2.

В алгебре множеств элементами являются подмножества фиксированного универсального множества . В этой алгебре операция пересечения соответствует конъюнкции, операция объединения соответствует дизъюнкции, а операция дополнения соответствует отрицанию. Само множествоявляется единицей, а– нулём. Справедливость соотношений в пункта 8.2. для этой алгебры можно доказать непосредственно, рассматривая в них переменные как множества, а знаки логических функций – как соответствующие операции над множествами.

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

Пусть даны два вектора ииз множества. Тогда:

Поскольку компоненты (координаты) векторов принимают значения 0 или 1, то указанные операции – это просто логические операции над двоичными переменными, поэтому операции над векторами естественно назвать покомпонентными логическими операциями над двоичными векторами.

Пример 8.6:Даны векторыи. Найти.

Решение:

.

Заметим, что подобные операции (наряду с логическими операциями над переменными) входят в систему команд любой современной ЭВМ.

Теорема:Если мощность множества равна , то булева алгебра изоморфна булевой алгебре .

Эта простая по содержанию теорема имеет огромное значение в математике. Она позволяет заменить теоретико-множественные операции над системой подмножеств данного множества поразрядными логическими операциями над двоичными векторами.

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

Теорема:Если мощность множества равна , то булева алгебра изоморфна булевой алгебре функций .

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

0	0	0	0	0	0	0	1
0	0	1	1	1	1	1	0
0	1	0	0	1	1	0	1
0	1	1	0	0	0	0	1
1	0	0	1	0	1	0	0
1	0	1	1	1	1	1	0
1	1	0	0	0	0	0	1
1	1	1	0	1	1	0	1