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

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

Геометрическое моделирование множеств. Диаграммы Венна

Для наглядного представления множеств и отношений между ними используется диаграммы Венна (иногда их называют кругами Эйлера или диаграммами Эйлера – Венна).

Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, – в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга (рис 1.1а)).

С помощью диаграмм Венна удобно иллюстрировать операции над множествами.

Рис.1.1

Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Например, Ç (ВÈC), (А \ В) + C – формулы алгебры множеств.

Для любых множеств 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.