1.4. Дополнение множеств. Формула включений и исключений
В
математической литературе разность множеств В\А иногда называют дополнением множества А до множества В. Если в некоторых рассуждениях участвуют только подмножества
самого большого, универсального множества I, то разность I\А называется дополнением множества А до множества I или просто дополнением
множества А и обозначается (или
, или
). Т.е. в дополнение множества А входят все элементы, не принадлежащие А. Например, если мы рассматриваем множества студентов, описываемых
различными признаками: юноши и девушки, отличники, «двоечники» и т.д., то
универсальным множеством будет множество всех студентов, а дополнением до
множества девушек – множество студентов-юношей.
Если
универсальное множество не указано или оно не ясно из контекста, то говорить о
дополнении множества А недопустимо.
На
диаграммах Эйлера универсальное множество I изображается множеством точек некоторого
прямоугольника, а его подмножества – в виде кругов внутри этого прямоугольника.
Дополнение множества А будет
изображено в таком случае той частью прямоугольника, которая лежит за пределами
круга (заштрихованная часть рис.2.11).
Рис.2.11
Для любых подмножеств А и В
универсального множества I справедливы следующие утверждения:
1)
=А;
2)
= I ,
= Æ;
3)
,
– законы де Моргана;
4)
АÈ(АÇB)=А, АÇ(АÈB)=А – законы
поглощения;
5)
АÇ = Æ, АÈ
= I ;
6) АÈÆ = А, АÇI = А;
1)
АÇÆ = Æ, АÈI = I .
Можно
заметить, что утверждения 2) – 6) обладают замечательным свойством: если в
одном из этих утверждений заменить Æ на I , È
на Ç и наоборот, то в результате получим утверждение
парное ему. Это свойство называется принципом
двойственности. Принцип двойственности помогает значительно упрощать запись
некоторых выражений и применяется во многих математических разделах (например,
в алгебре высказываний, которая будет рассмотрена далее).
Рассмотрим
вопрос относительно числа элементов множества. В случае непустого конечного
множества А мы можем пересчитать
элементы множества, закрепив за каждым элементом соответствующий номер 1, 2, 3,
…, n. Тогда элементы множества предстанут
в занумерованном виде: ,
,
, …,
. Номер последнего элемента и означает число элементов
множества А. Элементы конечного множества,
содержащего более одного элемента, можно занумеровать разными способами. Но
последнему элементу мы всегда поставим в соответствие один и тот же номер n, число элементов множества не зависит от способа
нумерации его элементов. Значит число n, соответствующее
количеству элементов множества А={
,
,
, …,
}, будет количественной характеристикой этого множества.
Число элементов конечного множества будем обозначать через N(A).
Число элементов пустого множества Æ равно нулю: N (Æ)=0.
Пусть
существует два конечных множества А и
В, количество элементов которых N(A) и N(В).
Тогда
N(АÈВ)= N(A)+N(В) –N(АÇВ). (2.4)
Эта
формула называется формулой включений и
исключений и позволяет решать многие задачи теории множеств.
Действительно,
количество элементов, составляющих общую для множеств А и В часть - АÇВ, входит в
сумму N(A)+N(В) дважды и
его необходимо вычесть для получения числа элементов обоих множеств N(АÈВ).
Из
(2.4) следует, что если множества А и
В не пересекаются, то
N(АÈВ)= N(A)+N(В).
Для
пересекающихся множеств А и В
N(АÈВ) < N(A)+N(В).
Для
трех множеств А , В и С
формула включений и исключений выглядит следующим образом:
N(A) + N(В) + N(С) – N(АÇВ) – N(BÇC) – N(АÇC) + N(АÇВÇC).
Для
любых множеств А , В и С:
N(A) + N(В) + N(С).
N(A) + N(В) + N(С) только
если множества А , В и С
попарно не пересекаются.
В том случае, когда универсальное для
рассматриваемых подмножеств множество I также
является конечным, то
N(I) – N(А);
N(I) – N(АÈВ)= N(I) – N(A) – N(В) + N(АÇВ).
Аналогично для трех множеств А , В и С:
N(I) –
N(A) –N(В) –N(С) + N(АÇВ)+ N(BÇC)+ N(АÇC)-N(АÇВÇC).
Пример 2.5.
В 101-й группе – 29 студентов. Каждый из них изучает или английский,
или немецкий язык. 5 студентов изучают и английский, и немецкий одновременно. Сколько
студентов занимаются в английской группе, если в немецкой – 12 студентов?
Обозначим
через А множество студентов,
изучающих английский язык, а через В
– немецкий язык. Количество студентов в немецкой группе – N(В)=12.
Множество студентов, изучающих одновременно и английский, и немецкий – АÇВ, N(АÇВ)=5. Всего
студентов N(АÈВ)=29. Значит
количество студентов в английской группе по формуле (2.4) можно найти так:
N(A) = N(АÈВ)–N(В)+N(АÇВ) = 29–12+5 = 22.
Пример 2.6. Задача Льюиса Кэррола. В одной из повестей Льюиса Кэррола – автора «Алисы в стране чудес», «Алисы в
зазеркалье» и др. – есть такая задача: «В ожесточенном бою 70 из 100 пиратов
потеряли один глаз, 75 – одно ухо, 80 – одну руку и 85 одну ногу. Каково
минимальное количество потерявших одновременно глаз, ухо, руку и ногу?»
Обозначим
через А – множество пиратов,
потерявших один глаз, через В – одно
ухо, через С – одну руку, через D – одну ногу. Тогда множество потерявших и глаз, и ухо, и
руку, и ногу одновременно – АÇВÇСÇD. Универсальное множество I можно представить в виде: I=() È (АÇВÇСÇD). По закону Моргана
=
È
È
È
. (На рис. 2.12 множество АÇВÇСÇD выделено на диаграмме темно-серым цветом, множество
È
È
È
– светло-серым)
Рис. 2.12
Так как множества È
È
È
и АÇВÇСÇD не пересекаются, то N(I)=
N(
È
È
È
)+N(АÇВÇСÇD). Множества
,
,
и
могут попарно
пересекаться. Значит N(
È
È
È
)£N(
)+N(
)+N(
)+N(
). N(
)=N(I) – N(A) = 100 – 70 = 30, N(
)=N(I) – N(В) = 100 – 75 = 25, N(
)=N(I) – N(С) = 100 – 80 = 20, N(
)=N(I) – N(D) = 100 – 85 = 15. Таким образом, N(I) £ N(
)+N(
)+N(
)+N(
)+N(АÇВÇСÇD), а N(АÇВÇСÇD)³N(I)–N(
)–N(
)–N(
)–N(
)=100 – 30 – 25 – 20 – 15=10.
Итак,
N(АÇВÇСÇD)³10, т.е. не менее 10 пиратов
одновременно лишились и глаза, и уха, и руки, и ноги.