Контрольные вопросы и задания

1. Доказать, что нестрогое включение обладает свойством рефлексивности: A  A.

2. Показать, что {{1,2}, {2,3}}  {1, 2, 3}.

3. Доказать, что для любых множеств A₁, A₂, . . . , A_n если справедливы включения A₁  A₂  ...  A_n  A₁, то A₁ = A₂ = ... =A_n.

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

Определим следующие операции.

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

2. Пересечение. Пересечением множеств А и В называется множество С, состоящее из элементов, одновременно принадлежащих А и В. Обозначается так: C = A  B.

3. Разность. Разность множеств А и В – это множество С (С = А \ В), состоящее из элементов множества А, не принадлежащих множеству В. Если В  А, то разность С = А \ В называется дополнением В до А.

Считается, что все множества включены в некоторое множество U, которое называют универсальным множеством. В этом случае дополнение какого-либо множества А до U обозначается С(А) или .

4. Симметричная разность. По определению симметричная разность двух множеств А и В – это множество

С = А  В = (А \ В)  (В \ А).

Основные свойства операций.

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

А  В = В  А; А  В = В  А.

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

(А  В)  С = А  (В  С) = А  В  С;

(А  B)  С = А  (В  С) = А  В  С.

Свойствами коммутативности и ассоциативности обладают многие операции. Чтобы не создалось впечатления, что коммутативность и ассоциативность являются общими свойствами всех операций приведем пример неассоциативной операции – возведение в степень: (2³)² = 8² = 64; = 2⁸ = 512. Некоммутативной операцией является операция умножения матриц (АВ  ВА).

3. Взаимная дистрибутивность:

а) (А  В)  С = (А  С)  (В  С);

б) (А  B)  С = (А  С)  (В  С).

Для вещественных чисел выполняется свойство дистрибутивности операции умножения относительно сложения a(b + с) = = аb + ас. Операции  и  множеств – взаимно дистрибутивны:

Докажем равенство а).

Предположим, что x(А  В)  С, тогда xС и xА или xВ. Рассмотрим первый случай xС и xА. Тогда хА  С, а значит, по определению объединения, х(А  С)  (В  С).

Во втором случае, т.е. при xС и xВ получаем, что x (В  С)  (А  С). Таким образом, мы доказали включение

[(А  В)  С]  [(А  С)  (В  С)].

Докажем обратное включение. Пусть х(А  С)  (В  С), тогда хА  С или хВ  С. В первом случае хА и хС. Во втором случае хВ и xС. В обоих случаях получаем, что хС и хА или хВ. Следовательно, х(А  В)  С. Тем самым доказано включение (А  С)  (В  С)  (А  В)  С.

Таким образом, (А  В)  С = (А  С)  (ВС), что и требовалось доказать.

4. Идемпотентность:

A  A = A; A  A = A.

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

(A  B)  A = A; (A  B)  A = A.

6. Свойства нуля:

A   =A; A   = .

7. Свойства единицы:

A  U =U; A  U = A.

8. Инволютивность:

.

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

; .

9. Свойства дополнения:

; .

Законы де Моргана можно обобщить на произвольное количество множеств. Пусть А₁, А₂, . . . – некоторые множества и пусть все они включены в S (А₁, А₂, . . .  S). Тогда выполняются следующие соотношения.

11. – дополнение объединения множеств равно пересечению их дополнений.

12. – дополнение пересечения множеств равно объединению их дополнений.

Докажем свойство 11. Пусть х, тогда  х, значит, x не принадлежит ни одному из множеств A_k (k,хА_k), следовательно, по определению дополнения, хS \А_k для любого k. Отсюда вытекает, что х.

Обратно, пусть х. Тогда этот элемент принадлежит каждому из множеств S \ A_k (k, хS\ A_k). Следовательно, хA_k для любого k, а, значит, хи поэтому х, что и требовалось доказать.