Главная | Обратная связь

Основные тождества алгебры множеств

Для любых множеств 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, нужно доказать следующие факты:

1) если xÎ А, то xÎВ;

2) если xÎВ, то xÎ А.

Построив цепочку равносильностей A Û В₁Û В₂ Û …Û В_n ÛB можно установить требуемое равенство. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а): AÈ (BÇC) = (AÈB) Ç (AÈC).

Пусть некоторый элемент x принадлежит левой части тождества, т.е. xÎ AÈ (BÇC), и докажем, что x принадлежит правой части, т.е. xÎ(AÈB) Ç (AÈC). Для этого будем использовать основные тождества алгебры множеств и алгебры высказываний.

xÎ AÈ (BÇC) Û xÎ A Ú xÎ BÇCÛ xÎ A Ú (xÎB Ù xÎ C)Û (xÎ A Ú xÎB) Ù( xÎ AÚ xÎ C)Û xÎ(AÈB) Ù xÎ (AÈC)Û xÎ(AÈB) Ç (AÈC)

Построенная цепочка равносильностей доказывает факты 1 и 2.

Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.

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

Пример.

Доказать тождество (AÈB) \ В = A Ç .

Пусть некоторый элемент x принадлежит левой части тождества, т.е. xÎ(AÈB) \ В. Покажем, что x принадлежит правой части, т.е. xÎ A Ç .

xÎ(AÈB) \ В Û xÎ (AÈB) Ç Û xÎ (AÇ ) Ù xÎ (BÇ )Û xÎ (AÇ ).

Тождество доказано.

Пример.

Доказать тождество:

A \ (В \ C) = (A \ В)È (A Ç C).

Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.2).

Рисунок 2

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

xÎA \ (В \ C) Û xÎA Ç ÛxÎA Ç ÛxÎA Ç ( È ) ÛxÎA Ç ( ÈC) ÛxÎ (A Ç ) È (A Ç C) ÛxÎ (A \ В)È (A Ç C).