Главная / Темы / Количество элементов в объединении множеств

Количество элементов в объединении множеств

Задача. Даны два КОНЕЧНЫХ множества A и B. Как связаны количество элементов (синонимы: размер, мощность) множеств A и B и количество элементов в объединении A B?
Обозначение. Мощность (т.е. количество элементов) множества X обозначается |X|.

Решение (см. рисунок, взят из Википедии).Venn_A_intersect_B.svg

Первое, что приходит в голову – это сложить мощности множеств A и B. Но ответ |A B|= |A|+|B| неправильный! Потому, что элементы, лежащие в пересечении AB множеств (фиолетовая область на рисунке) будут подсчитаны два раза. Чтобы не сделать эту ошибку, нужно из суммы мощностей множеств A  и B  вычесть мощность их пересечения. Тогда все элементы объединения окажутся подсчитанными ровно один раз - что нам и нужно.  Правильный ответ:

|A B|= |A|+|B| - |AB|

Эту же формулу можно записать и по-другому:

|A B| + |AB| = |A|+|B|

|A|+|B| = |AB| + |AB|

Пример. Пусть A – это множество четных чисел, не превосходящих 25, B - множество чисел, не превосходящих 25, и делящихся на 5.

Тогда A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}; B = {5, 10, 15, 20, 25}

A B = {2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 22, 24, 25};

AB = {10, 20}

Понятно, что |A| = 12; |B| = 5. Однако, |A B| равно не 12+5 = 17, а

12+5-|AB| = 12+5-2=15,

Потому, что при объединении множеств 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. Точно также (то есть, сложением мощностей) находится мощность объединения нескольких непересекающихся множеств.

Чтобы показать, что объединяются непересекающиеся множества используют знак ⊕. Сказанное выше можно записать так:

|M1M2| = |M1| + |M2|                        (для объединения двух непересекающихся множеств)

|M1M2 M3| = |M1| + |M2| + |M3| (для объединения трех непересекающихся множеств)

Venn_A_intersect_B.svgТеперь рассмотрим общий случай (см. рисунок). Множество A B можно представить как объединение трех непересекающихся множеств. Первое множество состоит из элементов, которые лежат в A, но не лежат в B. На рисунке оно показано синим и расположено слева. Это множество обозначается A - B. Второе множество состоит из элементов, которые лежат в B, но не лежат в A. На рисунке оно показано розовым и расположено справа. Это множество обозначается B - A. Третье множество состоит из элементов, которые лежат и в A, и в B. Это – пересечение множеств A и B, оно, как известно, обозначается AB. На рисунке оно показано фиолетовым и расположено в середине. Множества A, B и A B можно представить в виде объединения этих непересекающихся множеств:

A = (A-B) (AB);                   B = (B-A) (AB);

A B = (A-B) (AB) (B-A)

Поэтому

|A| = |(A-B)|+|(AB)|;                  |B| = |(B-A)|+|(AB)|;

|A B| = |(A-B)|+ |(AB)| +|(B-A)|

Отсюда:                 |(A-B)| = |A| - |(AB)|;                    |(B-A)|= |B| - |(AB)|;

|A B| =( |A| - |(AB)|) + |(AB)| + (|B| - |(AB)|) =

= |A| - |(AB)| + |(AB)| + |B| - |(AB)| =

= |A| + |B| - |(AB)|.

Замечание. Если кому-то удобнее, можно записать и так. Обозначим мощность множества A через x, мощность множества B через y, мощность пересечения AB через 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| - |(AB)|.

 

Пример (продолжение). Пусть, как и раньше, A – это множество четных чисел, не превосходящих 25, B - множество чисел, не превосходящих 25, и делящихся на 5.

Тогда A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 20, 22}; B = {5, 10, 15, 20, 25}

A B = {2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 22, 24, 25};

AB = {10, 20}

Наши разбиения на непересекающиеся множества будут выглядеть так:

A - B = {2, 4, 6, 8, 12, 14, 16, 18, 22, 24} – десять элементов; из множества A исключены элементы пересечения 10 и 20;

B - A = {5, 15, 25} – три элемента; из множества B исключены элементы пересечения 10 и 20;

A B = {2, 4, 6, 8, 12, 14, 16, 18, 22, 24}  {5, 15, 25}  {10, 20} .

Это составляет 10+3+2 = (10+2) + (3+2)-2 = 15 элементов.

 

 
 

0 Comments

Оставьте коммент первым.

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика