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

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

Р(U) следующие операции определяются так:

а) объединение (сумма) (обозначается , +): А В = {x| x А или x В}; б) пересечение (произведение) ( , ): А В = {x| x А и x В};

в) разность (А \ В; А – В): А \ В = {x| x А и x В};

г) симметрическая разность или кольцевая сумма ( , , +): А В=

=(А \ В) (В \ А) = {x| (x А и x В) или (x В и x А)};

д)дополнение множестваА ( ): ={x|x и x А}= U \ A. Иллюстрация

операций над множествами диаграммами Эйлера-Венна на рисунке 1.1.2.

А В A B

А \ В А В

Рисунок 1.1.2

Операции объединения и пересечения допускают обобщения:

A₁ A₂ … A_n = , A₁ A₂ … A_n = .

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

Т а б л и ц а 1.1.1

1 Идемпотентность А А=А А А=А

2 Коммутативность А В= В А А В=В А

3 Дистрибутивность А (В С)=(А В) (А С) А (В С)=(А В) (А С)

4 Ассоциативность А (В С)=(А В) С А (В С)=(А В) С

5 Свойство поглощения А (В А)=А А (В А)=А

6 Свойства нуля и единицы (констант) А Ø=А А Ø= Ø А U=U А U= A

7 Закон де Моргана = =

8 Закон двойного отрицания (двойного дополнения или инволютивности) =A

9 Свойство дополнения A =U A = Ø

Доказать эти свойства можно либо с помощью диаграмм Эйлера-Венна, либо формальными рассуждениями, опирающимися на определение операций, например, докажем = .

1 Доказательство с помощью диаграмм:

а)

А В

в)

Рисунок 1.1.3

На последних рисунках в пунктах а) и в) отмечена одна и та же область, что доказывает тождество.

2 Докажем = формальными рассуждениями.ем

В формальных рассуждениях исходят из того, что А=В А В и

В А, а последнее имеет место по определению отношения включения: А В (x A x B) и В А (x B x A), поэтому:

а) x x А В x A и x B x и x x ;

б) x x и x x A и x B x А В .

Теорема. Для любых множеств А и В следующие условия эквивалентны:

а) А В;

б) А В=А;

в) А В =В;

г) А \ В = Ø;

д) В =U.

В примере 1.1.2 свойства операций использованы для упрощения выражения.

Пример 1.1.2 - .

Дата добавления: 2014-12-27