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

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

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

А  В  В  А; А В  В А.

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

А  (В  С)  (А  В)  С; А (В C)  (А В) С.

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

А (В  С)  А В  А С; А  В С  (А  В) (А  С).

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

А  А  А; А А  А.

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

=АВ; =А В.

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

А    А; А U  А;

А   ; А  U  U;

А А  U; АА  .

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

А.

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

Формула, в которой присутствуют символы операций над множествами, есть способ задания множества. Две формулы равносильны, если они представляют одно и то же множество. Любую формулу булевой алгебры множеств можно вывести путем равносильных преобразований, используя формулы из приведенного списка. Данный список является достаточным, но для вывода любой формулы данной алгебры можно воспользоваться меньшим списком, т.е. некоторые формулы этого списка можно вывести из других. Например, формулу А  В С  (А  В) (А  С) (дистрибутивность объединения относительно пересечения) можно получить следующим образом. Ее правую часть, используя дистрибутивность пересечения, представим как (А  В) (А  С)  (А  В) А  (А  В) С. Раскрыв скобки (по закону ассоциативности), получим (А  В) А  (А  В) С  А А  В А  А С  В С. Применим закон идемпотентности и введем константу U (А А  А  А U), в результате чего после применения закона коммутативности пересечения правая часть примет вид А U  А В  А С  В С. После вынесения за скобки А получим А (U  В  С)  В С, что равно левой части исходного выражения согласно свойству константы U.

Подобным образом выведем закон поглощения А  А В  А, которого нет в приведенном списке:

А  А В  А U  А В  А (U  В)  А.

Используя принцип двойственности, получим: А (А  В)  А.

Формулу А В А С  А В А С  В С выведем следующим образом:

А В А С  В С  А В А С  В С(А А)  А В(U С) А С(U В)  А В А С.

Используя только что выведенную формулу и закон поглощения, докажем А В  А  В:

А В  А U В  А U В  U В  А В  В  А  В.