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

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

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

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

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

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

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

Решение:

.

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

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

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

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

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

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

Дата добавления: 2015-10-28