Все формулы РФ

Математика / Графы, логика

Формула включений и исключений для двух множеств

Формула включений и исключений для двух множеств считает размер объединения A и B: складывает мощности множеств и один раз вычитает их пересечение. Она нужна, когда объект может иметь оба признака сразу, поэтому простая сумма дает двойной счет.

Опубликовано: Обновлено:

Дискретная математикаКомбинаторикаЕсть историческая справкаСтраницы с задачами и решениями

Формула

$$|A\cup B|=|A|+|B|-|A\cap B|$$

Обозначения

$A$
первое конечное множество или первый признак в общем универсуме, элемент
$B$
второе конечное множество или второй признак в том же универсуме, элемент
$A∩B$
пересечение двух множеств, то есть элементы с обоими признаками, элемент

Условия применения

  • Множества A и B должны быть конечными подмножествами одного и того же универсума.
  • Пересечение A∩B считают по тем же объектам, что и сами множества, без смены критерия учета.
  • Формула дает число элементов хотя бы в одном из двух множеств, а не число элементов ровно с одним признаком.

Ограничения

  • Если нужно найти число элементов вне A и B, дополнительно требуется размер всего универсума.
  • Для подсчета элементов ровно с одним признаком используют другую комбинацию: |A|+|B|-2|A∩B|.
  • В вероятностных задачах та же идея работает для событий, но значения должны быть согласованы как вероятности, а не смешаны с абсолютными численностями.

Подробное объяснение

Формула |A∪B|=|A|+|B|-|A∩B| исправляет двойной счет при объединении двух конечных множеств. Если объект принадлежит только A, он появляется в сумме |A|+|B| один раз. Если объект принадлежит только B, он тоже появляется один раз. Но объект из пересечения A∩B входит сразу в оба слагаемых, поэтому без вычитания был бы учтен дважды.

Смысл формулы удобно видеть через диаграмму Венна или таблицу из трех областей: только A, только B и одновременно A и B. Объединение состоит из всех трех областей, а сумма |A|+|B| считает центральную область два раза. Вычитание |A∩B| оставляет каждый элемент ровно в одном экземпляре.

Эта запись отвечает на вопрос «сколько объектов имеют хотя бы один из двух признаков». Она не отвечает напрямую на вопрос «сколько объектов имеют ровно один признак» и не показывает, сколько объектов не имеют ни одного признака. Для этих задач нужны дополнительные преобразования и, во втором случае, размер всего универсума.

В вероятностных задачах действует та же логика: вероятность объединения двух событий равна сумме вероятностей событий минус вероятность их совместного наступления. Важно не смешивать абсолютные количества и вероятности в одной подстановке; сначала выбирают единый язык счета.

От правила суммы формула отличается наличием пересечения. Если A и B несовместны, то |A∩B|=0 и выражение превращается в обычное сложение. Если пересечение не пусто, именно оно показывает, где простая сумма перестает работать.

Как пользоваться формулой

  1. Задайте общий универсум и два множества A и B.
  2. Найдите |A|, |B| и число элементов в A∩B.
  3. Сложите мощности двух множеств.
  4. Вычтите мощность пересечения, чтобы убрать двойной счет.
  5. Проверьте ответ разбиением на области только A, только B и A∩B.

Историческая справка

Идея вычитать общий пересчет появилась естественно в задачах о конечных множествах и вероятностях. Уже ранняя теория вероятностей XVII-XVIII веков работала с объединениями событий: если два события могут произойти одновременно, простое сложение их шансов завышает результат. В такой форме правило связано с развитием комбинаторики и вероятностного счета у Паскаля, Ферма, Бернулли, де Муавра и последующих авторов.

Современная запись через мощности множеств стала привычной позже, когда в XIX-XX веках закрепились язык множеств, диаграммы пересечений и обозначения объединения и пересечения. В учебных курсах формула для двух множеств стала первым примером принципа включений и исключений: она показывает всю идею на минимальном случае, где достаточно одного вычитания.

Пример

Задача: в группе 40 студентов 18 изучают Python, 15 изучают SQL, а 7 записаны на оба курса. Сколько студентов изучают хотя бы один из двух курсов? Обозначим через A множество изучающих Python, через B - множество изучающих SQL. Тогда |A|=18, |B|=15, |A∩B|=7. Подставляем в формулу: |A∪B|=18+15-7=26. Ответ: хотя бы один курс изучают 26 студентов. Проверка: только Python изучают 18-7=11, только SQL - 15-7=8, оба курса - 7. Сумма трех непересекающихся групп равна 11+8+7=26; оставшиеся 14 студентов из 40 не входят в объединение.

Частая ошибка

В формуле для двух множеств нельзя просто сложить |A| и |B|, если есть элементы с обоими признаками: они будут посчитаны дважды. Пересечение |A∩B| должно описывать ровно те же объекты и тот же универсум, что A и B. Частая путаница - принимать |A∪B| за число элементов ровно с одним признаком; для такого подсчета нужно отдельно вычесть двойное пересечение из каждого множества или использовать |A|+|B|-2|A∩B|.

Практика

Задачи с решением

Найти объединение двух кружков

Условие. В шахматный кружок ходят 12 человек, в математический - 10, в оба кружка - 4.

Решение. Складываем размеры двух множеств и вычитаем пересечение: 12+10-4=18.

Ответ. Хотя бы один из двух кружков посещают 18 человек.

Проверить непересекающиеся множества

Условие. Пусть |A|=9, |B|=6, а A∩B пусто.

Решение. Подставляем |A∩B|=0, получаем |A∪B|=9+6-0=15.

Ответ. При пустом пересечении формула совпадает с правилом суммы.

Дополнительные источники

  • Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics
  • Rosen K. H. Discrete Mathematics and Its Applications
  • van Lint J. H., Wilson R. M. A Course in Combinatorics

Связанные формулы

Математика

Правило суммы в комбинаторике

$N=m_1+m_2+\cdots+m_k$

Формула описывает прием «сложение несовместных случаев» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число размещений без повторений

$A_n^k=\frac{n!}{(n-k)!}$

Формула описывает прием «упорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.