Основные свойства операций над множествами.
Операции объединения и пересечения над множествами обладают рядом свойств. Мы рассмотрим основные, наиболее важные свойства этих операций.
ТЕОРЕМА 1.3. Для любых множеств А, В и С имеем:
— идемпотентность объединения;
— идемпотентность пересечения;
— коммутативность объединения;
— коммутативность пересечения,
— ассоциативность объединения,
— ассоциативность пересечения,
— дистрибутивность объединения относительно пересечения,
— дистрибутивность пересечения относительно объединения.
Доказательство. Первые четыре свойства, свойства идемпотентности и коммутативности, легко следуют из определения операций объединения и пересечения. Для того чтобы доказать свойство ассоциативности (5), достаточно заметить, что
есть множество элементов, принадлежащих множеству А, или множеству В, или множеству С, и множество
состоит из тех же элементов. Аналогично доказывается свойство (6).
Докажем свойство (7). Пусть
Надо доказать, что множества D и Е равны, т. е. (а) если
, то
если то
.
Пусть
. Тогда возможны два случая:
В случае
следовательно,
. В случае
так что
; следовательно,
Предположим теперь, что
тогда
При этом если
, то
так что
; следовательно,
. Если
, то
. Из (а) и
следует равенство (5).
Свойство дистрибутивности (8) доказывается аналогично.