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

Ранее были описаны булевы алгебры множеств, то есть алгебры вида , где - булеан множества , то есть множество всех его подмножеств. Общий термин “булева алгебра” для алгебр множеств и логических функций не является случайным.

Определение. Всякая алгебра типа называется булевой алгеброй, если её операции удовлетворяют соотношениям 1 – 10 (см. предыдущую лекцию).

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

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

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

,

,

.

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

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

Решение:

.

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

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

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

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

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

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