§3. Операции над множествами.

1. Объединение. Объединением множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В. Обозначается: АВ.

Формально: АÈВ={x| xÎA Ú xÎB}.

Примеры: 1. {1;2} È {2;3} = {1; 2; 3}

2. {x| 1<x<10} È {y| 10£y<11} = {z| 1<z<11}

в математике (1;10) È[10;11) = (1; 11)

3.Легко доказать, что AÌAÈB и BÌAÈB.

2. Пересечение. Пересечением множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат как множеству А, так и множеству В.

Обозначается: АÇВ.

Формально: А Ç В = {x| xÎA Ù xÎB}.

Примеры: 1. {1; 2} Ç {2; 3} = {2}

2. (1; 10) Ç [10; 11) = Æ

3. Z Ç {x| xÎR Ù x>0} = N

4. Легко доказать, что A Ç В Ì A и A Ç В Ì B.

3. Разность двух множеств. Разностью множеств А и В называется множество, элементами которого являются элементы множества А, не принадлежащие множеству В, и только они. Обозначается: А \ В.

Формально: A \ B = {x| xÎA Ù xÏB}.

Примеры: 1. Если A={1; 2; 3} и B={2; 3; 4}, то A \ B={1}, а B\A={4}.

2.Легко доказать, что если A Ç B=Æ , то A \ B = A, а B \ A = B.

4. Симметрическая разность. Эта операция используется нечасто, однако бывает полезной в некоторых приложениях, например в машинной арифметике. Симметрической разностью двух множеств называется множество, которое определяется следующим образом: ADB= (A  B) \ (A Ç B), то есть из объединения выбрасываются общие элементы.

А это значит, что A D B состоит из тех и только тех элементов, которые либо принадлежат А, но не принадлежат В, либо принадлежат В, но не принадлежат А.

Формально: A D B ={x| xÎA\B Ú xÎB\A}.

Примеры: 1. A={1, 2, 3}; B={2, 3, 4}, то A D B={1, 4}.

2. Доказать, что если A Ç B =Æ, то A D B=A È B.

Теорема 1: (свойства операций объединения и пересечения): Для любых множеств А, В и С выполняются следующие законы:

1. А È А = А - идемпотентность объединения.

2. А Ç А = А - идемпотентность пересечения.

3. А È В = В È А - коммутативность объединения.

4. А Ç В = В Ç А - коммутативность пересечения.

5. А È ( В È С ) = ( А È В ) È С - ассоциативность объединения.

6. А Ç ( В Ç С ) = ( А Ç В ) Ç С - ассоциативность пересечения.

7. А È ( В Ç С ) = ( А È В ) Ç ( А È С ) - дистрибутивность объединения относительно пересечения.

8. А Ç ( В È С ) = ( А Ç В )È ( А Ç С ) - дистрибутивность пересечения относительно объединения.

Доказательство:

Докажем, например, свойство 8: пусть xÎ AÇ(BÈC) Þ xÎA и xÎ(BÈC), но второе означает, что xÎB или xÎC; если xÎB, то xÎ(AÇB), а если xÎC, то xÎ(AÇC), но это означает что xÎ(AÇB) или xÎ(AÇC) Þ xÎ(AÇC)È (AÇB). С другой стороны пусть

xÎ(AÇC)È (AÇB) Þ xÎ(AÇB) или xÎ(AÇC). Запишем логически xÎ(AÇB)ÚxÎ(AÇC), по определению пересечения истинно высказывание xÎAÙxÎBÚxÎAÙxÎC º xÎAÙ(xÎBÚxÎC)  xÎAÇ(BÈC).Что и требовалось доказать.

Пример: Предположим, что мы имеем две программы P и Q и что А- множество всех значений данных, доступных P, а В- множество всех данных, доступных Q. Тогда АÇВ- множество всех данных, доступных P и Q; АÈВ- множество всех данных, доступных хотя бы одной из программ; А\В- множество данных, доступных P и недоступных Q; В\А- множество данных, доступных Q и недоступных P; АDВ- множество всех данных, доступных только одной из программ.