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

Рассмотренные операции над множествами позволяют из одних множеств получать другие множества. Эти операции обладают рядом свойств, знание которых зачастую существенно упрощает анализ новых полученных множеств.

Приведем основные свойства операций. Пусть заданы множества A, B и C некоторого универсального множества U. Тогда для этих множеств верны тождества:

1. = , = – коммутативность;

2. – ассоциативность;

3. – дистрибутивность;

4. ,

5.

6.

7. – идемпотентность;

8. – законы де Моргана;

9. – законы поглощения;

10.

11.

12.

13.

Доказательство каждого из приведенных тождеств основано на использовании свойства симметричности отношения включения. Напомним это свойство: А = В, если и .

Доказывая тождество, сначала выбирают любой элемент х, принадлежащий левой части этого тождества. Выполняя преобразования над множествами в соответствии с приведенными операциями, пытаются доказать, что этот элемент принадлежит множеству из правой части этого тождества. Если это удается доказать, то, поскольку выбран произвольный элемент, это будет верно для любого другого элемента. Поэтому делается вывод, что множество из левой части тождества содержится во множестве из правой части.

Если аналогичные рассуждения для правой части тождества приводят к заключению, что правая часть содержится в левой, то тождество доказано.

Докажем тождество 3. Пусть Тогда на основании операции дизъюнкции или а на основании операции конъюнкции и Отсюда ясно, что если то и Отсюда следует Таким образом,

Далее, пусть Тогда и Отсюда следует, что а так как то получаем, что таким образом, и тождество доказано.

Приведем доказательство тождества, содержащего операцию отрицания. Для этого выберем тождество 8 и докажем его.

Пусть Тогда (U – универсальное множество) и Следовательно и поэтому очевидно, что и откуда следует, что Таким образом,

Пусть теперь Отсюда следует и следовательно и а поэтому но тогда Таким образом, и тождество доказано.

Остальные тождества доказываются аналогично. Остается заметить, что справедливость всех этих тождеств можно наглядно проиллюстрировать с помощью кругов Эйлера.