Булевы векторы. При рассмотрении конечных множеств вводится универсальное множество (универсум), обозначаемое обычно U, и всякое множество, подлежащее рассмотрению, считается подмножеством U. Тогда любое множество М представляется вектором, число компонент которого |U| и компоненты соответствуют элементам множества U. Компонента вектора равна 1, если соответствующий элемент принадлежит множеству М, и 0 – в противном случае. Пусть U = {a, b, c, d, e} и М = {a, b, d}. Тогда М представится вектором 11010. Векторы 00000 и 11111 представят соответственно пустое множество Æ и универсальное множество U.

Операции над множествами

Как было сказано выше, множество можно представить в виде результата операций над другими множествами.

Объединение множеств А и В представляет собой множество, содержащее те и только те элементы, которые принадлежат А или В:

А È В = {x / x Î A или x Î В}.

Пересечением множеств А и В является множество, содержащее те и только те элементы, каждый из которых принадлежит и А и В:

А Ç В = {x / x Î A и x Î В}.

Разность множеств А и В состоит из элементов множества А, которые не принадлежат множеству В:

А \ В = {x / x Î A и x Ï В}.

Сумма множеств А и В (ее называют еще симметрической разностью множеств А и В) содержит все элементы из А, не принадлежащие В, и все элементы из В, не принадлежащие А:

А + В = {x / (x Î A и x Ï В) или (x Î В и x Ï А)}.

Дополнение множества А состоит из элементов универсального множества U, не принадлежащих А:

`А = {x / x Î U и x Ï А}.

На рис.1.1 затемненными областями на диаграммах Эйлера-Венна показаны результаты перечисленных операций.

Рис.1.1. Операции над множествами

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

А + В = (А Ç`В) È (`А Ç В) = (А È В) \ (А Ç В);

`А = U \ А;

A \ B = A Ç`B.

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

Коммутативность:

А È В = В È А; А В = В А.

Ассоциативность:

А È (В È С) = (А È В) È С; А (В С) = (А В) С.

Дистрибутивность:

А (В È С) = А В È А С; А È В С = (А È В) (А È С).

Идемпотентность:

А È А = А; А А = А.

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

=`А`В; =`А È`В.

Законы операций с константами (пустым и универсальным множествами):

А È Æ = А; А U = А;

А Æ = Æ; А È U = U;

А È`А = U; А`А = Æ.

Закон двойного дополнения:

= А.

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

Заметим также, что для операции пересечения пустое множество имеет свойство нуля, т.е. эта константа ведет себя как нуль при арифметическом умножении: результатом этой операции с нулем всегда является нуль. Универсальное множество имеет свойство единицы, т.е. ведет себя как единица при арифметическом умножении. Для операции объединения универсальное множество имеет свойство нуля, а пустое множество – свойство единицы.

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

Например, закон поглощения А È А В = А, которого нет в приведенном списке, выводится следующим образом:

А È А В = А U È А В = А (U È В) = А.

Используя принцип двойственности, получим:

А (А È В) = А.

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

А È В С = (А È В) (А È С)

(дистрибутивность объединения относительно пересечения) можно получить следующим образом. Ее правую часть, используя дистрибутивность пересечения, представим как

(А È В) (А È С) = (А È В) А È (А È В) С.

Раскрыв скобки (по закону ассоциативности), получим

(А È В) А È (А È В) С = А А È В А È А С È В С.

Применим закон идемпотентности и используем константу U (А А = А = А U), в результате чего после применения закона коммутативности пересечения правая часть примет вид А U È А В È А С È В С. После вынесения за скобки А получим А (U È В È С) È В С, что равно левой части исходного выражения согласно свойству константы U.

Выведем теперь закон простого склеивания А В È`А В = В:

А В È`А В = В (А È`А) = В U = В.