logo
Линейная Алгебра от 2 октября 2013

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

Свойства операций объединения, пересечения и дополнения иногда называют законами алгебры множеств. Перечислим основные свойства операций над множествами. Пусть задано универсальное множество U. Тогда ( A, B, C) A, B, C  U выполняются следующие свойства:

1. идемпотентность:A  A = A, A  A = A;

2. коммутативность: A  B = B  A, A  B = B  A;

3. ассоциативность: A  (B  C) = (A  B)  C,

A  (B  C) = (A  B)  C;

4. дистрибутивность:

A  (B  C) = (A  B)  (A  C) (дистрибутивность  относительно ),

A  (B  C) = (A  B)  (A  C) (дистрибутивность  относительно );

5. свойства нуля: A   = A, A   = ;

6. свойства единицы: A  U = U, A  U = A;

7. поглощение: (A  B)  A = A, (A  B)  A = A;

8. инволютивность (свойство двойного дополнения):  = A;

9. законы де Моргана4: , ;

10. закон включения: А  B    ;

11. свойства дополнения: А   = U, А   = ;

12. выражение для разности: А \ В = А  .

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

Справедливость каждого из этих свойств можно доказать, используя утверждение 1.1 и замечание 1.3. В качестве примера приведем доказательство дистрибутивности объединения относительно пересечения: A  (B  C) = (A  B)  (A  C).

Пусть X = A  (B  C), Y = (A  B)  (A  C). Надо доказать, что множества X и Y равны, то есть XY и YX. Множество X  Y, если каждый элемент множества X принадлежит множеству Y. Пусть x  X  (x  A) или (x  B  C) тогда

Из произвольности элемента x следует, что X  Y.

Предложим теперь, что y  Y; то есть y  (A  B)  (A  C), тогда y  A  B и y  A  C. Возможны два случая:

Из произвольности элемента y вытекает, что Y X.

Таким образом, получили равенство множеств X = Y.