Алгебра множеств

Диаграммы Эйлера - Венна

Операции над множествами

1. Объединение множеств A и B

A È B = { x | x Î A или x Î B } (или - неисключающее)

2. Пересечение множеств A и B

A Ç B = { x | x Î A и x Î B }

3. Разность множеств A и B

A \ B = { x | x Î A и x Ï B }

4. Симметрическая разность множеств A и B

A D B = { x | (xÎA и xÏB) или (xÏA и xÎB)}=( A \ B ) È ( B \ A )

5. Дополнение множества A

A = { x | x ÏA }

Пример.

Пусть А = {1, 2, 3} и B = {3,4}, тогда

A È B = {1, 2, 3, 4}

A Ç B = {3}

A \ B = {1, 2}

A D B = {1, 2, 4}

А = множество чисел кроме 1, 2, 3.

Диаграммы Эйлера-Венна позволяют представить множества, как множества точек на плоскости, оганиченные замкнутыми кривыми круглой или овальной формы. Прямоугольная рамка ограничивает универсум. Обычно, если не требуется иное, рисуют так называемый общий случай: когда каждое из множеств имеет свои собственные точки и точки, общие с другими множествами.

AÈB – зоны I, II, III.

AÇB – зона III.

A\B - зона I.

A - все, кроме круга А.

ADB - зоны I, III.

Диаграмма для общего случая c тремя множествами будет иметь вид:

Построение диаграммы Эйлера-Венна для общего случая с четырьмя и более множествами можно предложить для самостоятельных развлечений.

Операции над множествами дают в результате новые множества.

Для операций справедлив ряд законов. Приведем наиболее часто используемые.

Для упрощения записи, уменьшения числа скобок, определяющих последовательность операций, можно использовать соглашение о "силе" операций (в порядке убывания): дополнение, пересечение, объединение.

Остальные операции можно выразить через эти три.

Законы:

1. Коммутативный:

A È B = B È A A Ç B = B Ç A

2. Ассоциативный:

A È (B È C) = (A È B) È C = A È BÈ C A Ç(B Ç C) = (A Ç B) Ç C = A Ç B Ç С

3. Дистрибутивный:

A È (B Ç С)= (A È B) Ç (A È C) A Ç (B È С) = (A Ç B) È (A Ç C)

4. Поглощения:

A È (A Ç B) = A A Ç (A È B) = A

5. Идемпотентности:

A È A = A A Ç A = A

6. Исключенного третьего: Противоречия:

A ÈA = U A Ç A = Æ

7. A È Æ = A A Ç Æ = Æ

8. A È U = U A Ç U = A

9. Де Моргана:

____ ___

A È B = A Ç B A Ç B = A È B

10. Æ = U U = Æ

11. Двойного отрицания: A = A

12. A \ B =A Ç B

13. A D B =A Ç B È A Ç B

Пример доказательства варианта дистрибутивного закона:

A È (B Ç С) = (A È B) Ç (A È C)

I. Докажем, что левая часть включена в правую:

A È (B Ç C) Í (A È B) Ç (A È C)

Пусть х Î А È (В Ç С), тогда у х есть две возможности

1. х Î A . Тогда х Î A È B и х Î A È C Þ х Î (A È B) Ç (A È C).

2. х Î B Ç C. Тогда х Î B и х Î C Þ х Î A È B и х Î A È C,

то есть х Î (A È B) Ç (A È C).

II. Докажем, что правая часть включена в левую:

(A È B) Ç (A È C) Í A È B Ç C.

Пусть х Î A È B и х Î A È C. Тогда возможны два варианта:

1. х Î A Þ х Î A È B Ç C

2. х Î B и х Î C Þ х Î B Ç C Þ х Î A È B Ç C.

То есть левое и правое множества равны.