Основные тождества алгебры множеств
Для любых множеств A, B, C справедливы следующие тождества:
1. Коммутативность.
а) A È B = B È A (для объединения);
б) A Ç B = B Ç A (для пересечения).
2. Ассоциативность.
а) A È (B È C) = (A È C) È C (для объединения);
б) A Ç (B Ç C) = (A Ç B) Ç C (для пересечения).
3. Дистрибутивность.
а) AÈ (BÇC) = (AÈB) Ç (AÈC) (для объединения относительно пересечения);
б) AÇ(BÈC) = (AÇB)È(AÇC) (для пересечения относительно объединения).
4. Закон де Моргана.
а) 
= 
Ç 
(дополнение к объединению есть пересечение дополнений);
б) 
= È (дополнение к пересечению есть объединение дополнений).
5. Идемпотентность.
а) A È A = A (для объединения);
б) A Ç A = A (для пересечения).
6. Поглощение.
а) A È (A Ç B) = A;
б) A Ç (A È B) = A.
7. Расщепление (склеивание).
а) (A È B) Ç (A È ) = A;
б) (A Ç B) È (A Ç ) = A.
8. Двойное дополнение.
= A.
9. Закон исключенного третьего. 
A È = U.
10. Операции с пустым и универсальным множествами.
а) A È U = U;
б) A È Æ = A;
в) A Ç U = A;
г) A Ç Æ = Æ;
д) 
= U;
е) 
= Æ.
11. А \ В = A Ç .
Чтобы доказать некоторое тождество A = B, нужно доказать, что, во-первых, если xÎ А, то xÎВ и, во-вторых, если xÎВ, то xÎ А. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а)):
AÈ (BÇC) = (AÈB) Ç (AÈC).
1. Сначала предположим, что некоторый элемент x принадлежит левой части тождества, т.е. xÎ AÈ (BÇC), и докажем, что x принадлежит правой части, т.е. xÎ(AÈB) Ç (AÈC).
Действительно, пусть xÎ AÈ (BÇC). Тогда либо xÎ A, либо xÎ BÇC. Рассмотрим каждую из этих возможностей.
Пусть xÎ A. Тогда xÎ A È B и xÎ A ÈC (это верно для любых множеств B и C). Следовательно, xÎ(AÈB) Ç (AÈC).
2. Предположим, что некоторый элемент x принадлежит правой части тождества, т.е. xÎ (AÈB) Ç (AÈC), и докажем, что x принадлежит левой части, т.е. xÎ AÈ (BÇC) .
Действительно, пусть xÎ (AÈB) Ç (AÈC). Тогда xÎAÈB, и одновременно xÎ AÈC. Если xÎ AÈB, то либо xÎ A, либо xÎ B, если .xÎ AÈC, то либо xÎ A, либо xÎ C. Пусть xÎ A, Тогда xÎ AÈ (BÇC) и утверждение доказано. Если xÏ A, то одновременно должны выполняться условия xÎ B и xÎ C, т.е. xÎ BÇC. Но тогда xÎ BÇC и xÎ AÈ (BÇC), что также доказывает наше утверждение.
Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.
Основные тождества алгебры множеств можно использовать для доказательства других тождеств.
Пример 1.14.
Доказать тождество (AÈB) \ В = A Ç .
Преобразуем левую часть тождества, используя тождество 11:
(AÈB) \ В = (AÈB) Ç .
Затем используем закон дистрибутивности (тождество 3б):
(AÈB) Ç = A Ç ÈB Ç .
Используем закон исключенного третьего (тождество 9):
B Ç = Æ.
Получим
A Ç ÈB Ç = A Ç È Æ.
Используем свойство пустого множества (тождество 10б):
A Ç È Æ = A Ç .
Тождество доказано.
Пример 1.15.
Доказать тождество:
A \ (В \ C) = (A \ В)È (A Ç C).
Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.2).
Рис. 1.2
Рис. 1.2б) и рис. 1.2д) иллюстрируют равенство множеств A \ (В \ C) и (A \ В)È (A Ç C).
Докажем тождество из нашего примера, воспользовавшись тождествами:
А \ В = A Ç , = È , 
= A, AÇ(BÈC) = (AÇB)È(AÇC).
Получим:
A \ (В \ C) = A Ç 
= A Ç 
= A Ç ( 
È 
) = A Ç ( ÈC) = (A Ç ) È (A Ç C) = (A \ В)È (A Ç C).
Основные тождества алгебры множеств можно также использовать для упрощения формул алгебры логики.
Пример 1.16.
Упростить выражение:
(AÈB) Ç ( ÈB) Ç (AÈ ).
Используя закон коммутативности (тождество 1б), поменяем местами вторую и третью скобки:
(AÈB) Ç ( ÈB) Ç (AÈ ) = (AÈB) Ç (AÈ ) Ç ( ÈB).
Применим закон расщепления (тождество 7а) для первой и второй скобок:
(AÈB) Ç (AÈ ) Ç ( ÈB) = A Ç ( ÈB).
Воспользуемся законом дистрибутивности (тождество 3б):
A Ç ( ÈB) = A Ç ÈA Ç B.
Используем закон исключенного третьего (тождество 9):
A Ç = Æ.
Получим
A Ç ÈA Ç B = Æ ÈA Ç B.
Используем свойство пустого множества (тождество 10б):
Æ ÈA Ç B = A Ç B.
Итак,
(AÈB) Ç ( ÈB) Ç (AÈ ) = A Ç B.