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

1. Коммутативность: А п В = В п А.

Обосновать это свойство очень просто. Любой элемент, принадлежащий общей части множеств А и В, т. е. А п В, принадлежит общей части множеств В и А, т. е. В п А, и наоборот.

2. Ассоциативность: А п (В п С) = (А п В) п С.

Докажем это свойство. Нам нужно доказать, что множество в левой части равенства равно множеству в правой части равенства. По определению равенства множеств нужно показать, что А п (В п С) с (А п В) n С, т. е. любой элемент х, принадлежащий А п (В п С), принадлежит и множеству (А п В) п С, а также, что (А п В) п С с А п (В n С), т. е. любой элемент у, принадлежащий (А п В) n С, принадлежит А п (В п С).

• 1) Пусть х — произвольный элемент из множества А п (В п С), т. е. х е е А п (В n С). По определению пересечения множествхе, А ихе В п С, а значит, хе А, ихе В, ихе С, т. е. х принадлежит общей части трех множеств А, В и С. Это значит, что х е, А п В ихе С, т. е. х е (Л п В) п С.
• 2) Пусть у — произвольный элемент множества (Ап В) п С, т. е. уе (Ап пВ) пС. По определению пересечения у е АпВ и у е С, т. е. у е А, и у е В, и у е С. Следовательно, у е А и у е (В п С), т. е. у е А п (В п С). Свойство доказано.

Это свойство можно проиллюстрировать с помощью диаграммы Эйлера — Венна (рис. 2.6).

Рис. 2.6. Иллюстрация доказательства свойства ассоциативности.

• 3. А п U = A.
• 4. Идемпотентность пересечения А пА = А.

Объединение. Следующая операция над множествами называется объединением.

Определение 2.4. Объединением множеств, А и В называется новое множество, которое обозначается А и В и состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В, т. е. ЛиВ = {ххе А или х е В).

Например, если А = {1, 2, 3}, В = {1, 3, 4}, то А и В = {1, 2, 3, А).

Покажем объединение двух множеств на диаграмме Эйлера — Венна (рис. 2.7).

Рис. 2.7. Объединение множеств.

п

Объединение п множеств записывают так: УД = Д и А₂ и… и Д_г

/=1.

Разность. Кроме операций пересечения и объединения над множествами можно выполнять еще одну операцию — нахождение разности.

Определение 2.5. Разностью множеств, А и В называется новое множество, которое обозначается А В и состоит из всех элементов множества А_у не принадлежащих множеству В, т. е. А В = {х х е А и х ? В).

Например, если А = {1, 2, 3}, В = {1, 3, 4}, то А В = {2}.

Па рис. 2.8 показана разность множеств с использованием диаграммы Эйлера — Война.

Рис. 2.8. Разность множеств.

Упражнение 2.1.

Найдите разность множеств ВА, если А = {1,2,3}, В = {1,3,4}. Равны ли разности.

АВиВА?

С разностью связано такое понятие, как дополнение одного множества до другого.

Определение 2.6. Дополнением множества, А до множества В, если Лей, называется множество, которое обозначается А (В) и состоит из всех элементов В, не принадлежащих А. Очевидно, что А (В) = В А, при условии что А с В.

Говоря о дополнении множества Л, часто имеют в виду дополнение его до универсального множества, т. е. A (U) = U А. Иногда для обозначения дополнения множества до универсального используют значок А.

Кстати, изображать универсальное множество принято в виде прямоугольника.

Перечисленные выше операции используются при решении задач. Рассмотрим такую задачу.

Пример 2.4.

Пусть в студенческой группе, насчитывающей 25 человек, 20 человек занимаются легкой атлетикой, 18 человек — волейболом и нет ни одного человека, кто бы не занимался другим видом спорта или ни одним из видов спорта. Есть ли в этой группе студенты, занимающиеся и легкой атлетикой, и волейболом? Сколько студентов этой группы занимаются только волейболом?

Решение

В данной задаче в качестве универсального множества следует рассматривать множество всех студентов группы (их 25). Кроме того, в него входят два подмножества: множество студентов группы, занимающихся легкой атлетикой (их 20); множество студентов группы, занимающихся волейболом (их 18). Общее количество занимающихся двумя видами спорта — 38 (20 + 18) — больше, чем студентов в группе. Происходит это потому, что студентов, которые занимаются обоими видами спорта, мы учли дважды — они входят и в первое, и во второе подмножества, т. е. в их пересечение. Их количество равно 13 (38 — 25). Из этого следует, что только волейболом занимаются 5(18- 13) студентов группы.

На диаграмме это решение будет выглядеть так (рис. 2.9).

В приведенном примере нас интересовали не только множества и их связи (например, наличие пересечения и объединения множеств), но и количество элементов в них, так как все рассматриваемые множества являются конечными. Количество элементов конечного множества А называют мощностью множества и обозначают т (А)^[.

При решении этого примера мы воспользовались принципом включения-исключения, который выражается некоторой формулой. Приведем ее для случая двух конечных множеств А_х и А₂:

т (А_х и А₂) = т (А_{) + т{А₂) — т (А_х п А₂).

В случае если А_х п А₂ — 0, последний член формулы будет равен нулю.

Этот принцип позволяет определить мощность объединения конечного числа конечных множеств, которые могут пересекаться друг с другом.

В общем случае формула включения-исключения выглядит следующим образом:

Пример 2.5.

Рис. 2.9. К примеру 2.4.

На первом курсе по одной из образовательных программ обучаются 34 студента. Каждый из них пользуется хотя бы одним из видов городского транспорта для поездки к месту учебы: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 5 студентов, метро и автобусом — 13 студентов, метро и троллейбусом — 14 студентов, троллейбусом и автобусом — 9 студентов. Сколько студентов пользуются только одним видом транспорта?

Решение

Такого вида задачи чаще всего решаются с использованием диаграмм Эйлера — Венна. Обозначим А — рассматриваемое множество студентов, которые добираются до места учебы на метро; В — множество студентов, которые пользуются автобусом; С — множество студентов, пользующихся троллейбусом.

Учитывая условие задачи, их можно изобразить следующим образом.

По условию, объединение этих множеств содержит 34 элемента. В области, где все три множества пересекаются, находятся 5 элементов. В пересечении множеств А и В должно находиться 13 элементов, но 5 из них уже учтены. Это означает, что в области, изображающей множество студентов, которые пользуются только метро и автобусом, находятся 13−5 = 8 элементов. Таким же образом, расставим числовые дан-^[1]

ные в те области, где это возможно. Найдем их сумму: 8 + 4 + 5 + 9 = 26. Это число характеризует число студентов, которые пользуются двумя и тремя видами транспорта, чтобы доехать до места учебы.

Рис. 2.10. К примеру 2.5.

Незаполненными числами окажутся области, которые изображают множество студентов, пользующихся только одним видом транспорта (либо метро, либо автобусом, либо троллейбусом). Их число равно 34 — 26 = 8. Это и есть ответ задачи.

Объясните, можно ли по данному условию задачи определить, сколько студентов пользуются каждым видом транспорта.

Определение 2.7. Декартовым произведением множеств, А и В называется новое множество, обозначаемое Ах В, элементами которого являются всевозможные пары (а, 6), где а е А, b е В, т. е. Ах В = {(а, Ь) а е Л, be В}.

Например, если А = {1, 2, 3}, В = {1, 3, 4}, то Ах В = {(1, 1), (1, 3), (1, 4), (2,1), (2, 3), (2,4), (3,1), (3, 3), (3,4)}.

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

Кстати, с декартовым произведением связано понятие координатной плоскости. Ведь если рассматривать множество координат точек координатной плоскости, то оно является декартовым произведением R х R, где первое множество действительных чисел R — координаты точек оси X, а второе R — координаты точек оси У.

• [1] О мощности бесконечного множества мы поговорим позже.