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

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

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

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

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

Законы:

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.

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