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

Чтобы записывать и преобразовывать теоретико-множественные

выражения, необходимо знать свойства операций над множествами.

Основные из этих свойств следующие.

I. Коммутативность

A È B = B È A; A Ç B = B Ç A.

2. Ассоциативность

A È(B È C)=(A È B)È A; A Ç(B Ç C)=(A Ç B)Ç A.

3. Дистрибутивность

А È (В Ç С)

А Ç (В È С)

= (А È В) Ç (A È C);

= (А Ç В) È (A Ç C).

4. Законы де Моргана

A È B = A Ç B; A Ç B = A È B.

5. Идемпотентность

A È A = A

6. Законы поглощения

A È(A Ç B)= A; A Ç(A È B)= A.

7. Закон двойного дополнения:

A = A.

8. Операции с универсальным и пустым множествами: A È U = U; A ÇÆ =Æ; A ÈÆ = A;

A Ç U = A; A È A = U; A Ç A =Æ.

Если внимательно рассмотреть свойства теоретико-множествен-ных операций, то можно сформулировать правило, известное как принцип двойственности.

Теоретико-множественное выражение, содержащее операции объ-

единения, пересечения, дополнения, а также универсальное множество U и пустое множество Æ, останется справедливым, если в нем произвести следующие замены

È® Ç; Ç®È; Æ ® U; U ®Æ; Ì®É.

Все перечисленные выше свойства могут быть доказаны по одной

схеме. Суть ее в следующем.

Пусть требуется доказать теоретико-множественное равенство M = N, где M и N есть некоторые множества.

Первая часть доказательства будет состоять в том, чтобы показать, что если некоторый элемент принадлежит множеству M, то он также

принадлежит множеству N. Этим будет доказана справедливость со-отношения M Ì N.

Вторая часть доказательства состоит в необходимости показать, что если некоторый элемент принадлежит множеству N, то он также принадлежит множеству M. Этим будет доказана справедливость со-отношения N Ì M.

Из соотношений M Ì N и N Ì M следует, что M = N.

Пример. Пусть требуется доказать, что

А È (В Ç С) = (А È В) Ç (A È C).

Очевидно, что здесь M = A È(B Ç C)и N = (А È В)Ç (A È C).

1. Проводим доказательство «слева направо» (=>).

Пусть имеется элемент х такой, что x Î M. Тогда из определения

операции объединения следует, что этот элемент принадлежит мно-жеству A (x Î A) или(здесьимеемнеисключающее«или»)множеству

B Ç C (x Î B Ç C).

Рассмотрим каждый из этих случаев.

а)Если(x Î A),то,поопределениюоперацииобъединения,имеем x Î A È B и x Î A È C.

Следовательно, этот элемент будет общим для этих множеств, то есть x Î(А È В)Ç (A È C).

Иначе говоря, для данного случая доказано, что M Ì N.

б) Если x Î B Ç C, то элемент x является общим для каждого из множеств В и С, то есть x Î B и x Î C. Но тогда будем иметь, что

x Î A и A È C. Следовательно, x Î(А È В)Ç (A È C). Другими сло-вами, и для данного случая M Ì N.

2. Проведем теперь доказательство «справа налево» (<=). Пусть x Î N. Тогда, по определению операции пересечения, можно записать, что x Î A È B и x Î A È C.

Рассмотрим два случая.

а)Предположим,что x Î A. Тогдаочевидно,что x Î A È(B Ç C).Следовательно, x Î M и мы имеем в этом случае N Ì M.

б) Предположим, что x Î A. В этом случае из выражения для N за-

ключаем, что элемент х является общим для множеств В и С, то есть x Î B Ç C. Нотогда x Î A È(B Ç C),такимобразомивэтомслучае N Ì M.

Так как мы доказали, что M Ì N и N Ì M N, то это может быть только тогда, когда M = N.

Лекция 3

Дата добавления: 2015-11-16