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

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 T x_A)(x_B*x_C) º x_A_(B_C).Что и требовалось доказать.

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