Количество элементов в объединении множеств
Задача. Даны два КОНЕЧНЫХ множества A и B. Как связаны количество элементов (синонимы: размер, мощность) множеств A и B и количество элементов в объединении A∪ B? Обозначение. Мощность (т.е. количество элементов) множества X обозначается |X|.
Решение (см. рисунок, взят из Википедии).
Первое, что приходит в голову – это сложить мощности множеств A и B. Но ответ |A∪ B|= |A|+|B| неправильный! Потому, что элементы, лежащие в пересечении A∩B множеств (фиолетовая область на рисунке) будут подсчитаны два раза. Чтобы не сделать эту ошибку, нужно из суммы мощностей множеств A и B вычесть мощность их пересечения. Тогда все элементы объединения окажутся подсчитанными ровно один раз - что нам и нужно. Правильный ответ:
Эту же формулу можно записать и по-другому:
Пример. Пусть A – это множество четных чисел, не превосходящих 25, B - множество чисел, не превосходящих 25, и делящихся на 5.
A∪ B = ;
Потому, что при объединении множеств A и B в множество A добавляются только числа 5, 15 и 25. Числа 10 и 20 - элементы пересечения A∩ B множеств A и B добавлять не нужно – они и так принадлежат множеству A.
Еще одно решение. Начнём с простого случая. Если множества M1 и M2 не пересекаются, то мощность их объединения равна сумме их мощностей: |M1∪ M2| = |M1|+|M2|. Мы просто пересчитываем сначала элементы множества M1, а потом – элементы множества M2 . Так как у множеств M1 и M2 нет общих элементов, такой пересчет даст нам общее количество элементов в объединении M1∪ M2. Точно также (то есть, сложением мощностей) находится мощность объединения нескольких непересекающихся множеств.
Чтобы показать, что объединяются непересекающиеся множества используют знак ⊕. Сказанное выше можно записать так:
|M1 ⊕ M2| = |M1| + |M2| (для объединения двух непересекающихся множеств)
|M1 ⊕ M2 ⊕ M3| = |M1| + |M2| + |M3| (для объединения трех непересекающихся множеств)
Теперь рассмотрим общий случай (см. рисунок). Множество A∪ B можно представить как объединение трех непересекающихся множеств. Первое множество состоит из элементов, которые лежат в A, но не лежат в B. На рисунке оно показано синим и расположено слева. Это множество обозначается A - B. Второе множество состоит из элементов, которые лежат в B, но не лежат в A. На рисунке оно показано розовым и расположено справа. Это множество обозначается B - A. Третье множество состоит из элементов, которые лежат и в A, и в B. Это – пересечение множеств A и B, оно, как известно, обозначается A∩B. На рисунке оно показано фиолетовым и расположено в середине. Множества A, B и A∪ B можно представить в виде объединения этих непересекающихся множеств:
A = (A-B) ⊕ (A∩B); B = (B-A) ⊕ (A∩B);
A∪ B = (A-B) ⊕ (A∩B) ⊕ (B-A)
|A| = |(A-B)|+|(A∩B)|; |B| = |(B-A)|+|(A∩B)|;
|A∪ B| = |(A-B)|+ |(A∩B)| +|(B-A)|
Отсюда: |(A-B)| = |A| - |(A∩B)|; |(B-A)|= |B| - |(A∩B)|;
|A∪ B| =( |A| - |(A∩B)|) + |(A∩B)| + (|B| - |(A∩B)|) =
= |A| - |(A∩B)| + |(A∩B)| + |B| - |(A∩B)| =
= |A| + |B| - |(A∩B)|.
Замечание. Если кому-то удобнее, можно записать и так. Обозначим мощность множества A через x, мощность множества B через y, мощность пересечения A∩B через p. Тогда
|A| = x+p; |B| = y+p;
|A∪ B| = x+y+p =
= x+y+p+(p-p) = x+y + p + p – p = x+ p + y + p – p =
= (x+p) + (y+p) – p =
= |A| + |B| - |(A∩B)|.
Пример (продолжение). Пусть, как и раньше, A – это множество четных чисел, не превосходящих 25, B - множество чисел, не превосходящих 25, и делящихся на 5.
Наши разбиения на непересекающиеся множества будут выглядеть так:
A - B = – десять элементов; из множества A исключены элементы пересечения 10 и 20;
B - A = – три элемента; из множества B исключены элементы пересечения 10 и 20;