Пусть A и B - произвольные множества. Тогда мощность их объединения может быть определена по формуле:
| A È B | = | A | + | B | -| A Ç B |. (1)
Если рассмотреть объединение трех множеств A, B и С, то справедлива следующая формула:
| A È B È С |=| A |+| B |+| С |-| A Ç B |-| A Ç C |-| B Ç C |+| A Ç B Ç C |. (2)
Справедливость каждой их приведенных формул легко может быть проверена с помощью диаграмм Венна для произвольных двух и трех множеств. Для этого достаточно посчитать, сколько раз учитывается в правой и левой части каждого равенства всякий элемент объединения.
Применение приведенных формул при решении конкретных задач может быть оправдано, если нахождение каждого значения в правой части соответствующей формулы проще нахождения всего значения ее левой части.
Считается, что в общем случае объединения множеств устроены сложнее, чем пересечения множеств. Например, множество A È B È С в общем случае может рассматриваться как более разнородное, чем каждое из входящих в него множеств A, B и С, поскольку содержать элементы обладающие и не обладающие свойствами элементов множеств A, B и С, в разных комбинациях, в которых достаточно выполнимости лишь одного из свойств элементов этих множеств.
Действительно, в A È B È С могут содержаться элементы, обладающие только свойством элементов множества A. Там же могут содержаться элементы не из A, но обладающие свойствами элементов множеств B или C.
Множества, мощности которых используются в правых частях формул (1) и (2), образованы пересечениями отдельных множеств и поэтому более однородны, поскольку все их элементы обладают одним и тем же свойством, представляемым конъюнкцией свойств элементов множеств входящих в пересечение.
Приведенные формулы (1) и (2) могут быть обобщены на случай объединения произвольного конечного числа множеств так, чтобы свести задачу нахождения мощности объединения множеств к серии задач, связанных с нахождением мощностей нескольких пересечений множеств.
Пусть заданы конечные множества A 1,..., A k и такое число i, что 0 £ i £ k. Обозначим как ni сумму мощностей всех возможных пересечений по i таких множеств.
Заметим, что ni является суммой слагаемых, так как существует ровно столько различных пересечений по i множеств из k.
ТЕОРЕМА 2.1
| Ai | = n1 +... + (- 1) i- 1 ni +... + (- 1) k- 1 nk. (1)
Доказательство
Пусть a - это произвольный элемент, входящий в Ai.
Покажем, что в левой и правой частях равенства (1) этот элемент множества A учитывается ровно один раз.
Для левой части (1) очевидно, что это так.
Рассмотрим правую часть доказываемого равенства. Предположим, что a содержится в r разных множествах из множеств A 1,..., A k. Тогда:
- в n 1 элемент a учтен раз;
- в n 2 элемент a учтен раз;
...
- в n r элемент a учтен раз.
В последующих слагаемых правой части (1) элемент a не учитывается ни разу.
Поэтому в выражении:
n 1 +... + (- 1) i- 1 n i +...+(- 1) k- 1 nk
элемент a учтен ровно
+... + (- 1) i- 1 +... + (- 1) r- 1 раз.
Докажем равенство:
+... + (- 1) i- 1 +... + (- 1) r- 1 = 1. (2)
Перенесем все члены этого равенства в правую часть и с учетом того, что = 1, получим:
0 = - +... + (- 1) i +... + (- 1) r . (3)
Воспользуемся формулой бинома Ньютона:
(1 - x) r = - x +... + (- 1) i xi +...+(- 1) r xr.
Очевидно, что формула (3) - частный случай бинома Ньютона для x = 1.
Значит, равенство (2) является справедливым. Поэтому элемент a учитывается в правой части формулы (1) ровно один раз.