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

	U	A			U	A			U	A
			B			B					B
		А В				А ∩ В				А \ В
		U	A				U
										A
				B
			А + В							А
			Рис. 1.1. Операции над множествами
Коммутативность:
А В = В А;						А В = В А.

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

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

Дистрибутивность:
А (В С) = А В А С;				А В С = (А В) (А С).
Идемпотентность:
А А = А;			А А = А.
Законы де Моргана:
		= А В;			= А В.
	A B			AB
Законы операций с константами (пустым и универсальным
множествами):
А = А;			А U = А;
А U = U;			А = ;
А А = U;			А А = .

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

A= А.

12

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

на символы U. При этом должен быть сохранен порядок действий. Этот факт известен под названием принципа двойственности.

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

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

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

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

А (А В) = А.

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

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

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

(А В) А (А В) С.

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

А А В А А С В С.

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

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

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

13

Формулу А В А С = А В А С В С (обобщенное склеивание) выведем следующим образом:

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

=А В (U С) А С (U В) = А В А С.

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

А А В = А В:

АА В = А U А В = А U А В U В =

=А А В В = А В.

14