Как найти мощность множества: пошаговое решение

Дано: в группе 30 студентов; 18 знают Python, 15 знают C++, 12 знают Java; 9 знают Python и C++, 7 знают Python и Java, 6 знают C++ и Java, 4 знают все три языка. Найти: мощность множества студентов, знающих хотя бы один язык, и мощность булеана этого множества.

Мощность конечного множества - это число его элементов, а мощность объединения считается по формуле включений и исключений: сложить одиночные мощности, вычесть попарные пересечения, прибавить тройное. Ответ: хотя бы один язык знают 27 студентов, ни одного не знают 3, а у множества из 27 элементов ровно 134 217 728 подмножеств. Калькулятор сверху пересчитает все области под твои числа, ниже - решение по шагам.

Решение по шагам

Дано. Универсум $U$ - группа из 30 человек, $|U| = 30$. Обозначим множества знающих языки:

Найти: $|A \cup B \cup C|$, число студентов вне объединения и мощность булеана объединения.

Шаг 1. Записываем формулу включений и исключений для трёх множеств.

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

Шаг 2. Подставляем числа. Сначала сумма одиночных мощностей, затем сумма попарных пересечений:

$$\begin{aligned} |A| + |B| + |C| &= 18 + 15 + 12 = 45, \\ |A \cap B| + |A \cap C| + |B \cap C| &= 9 + 7 + 6 = 22. \end{aligned}$$

Собираем всё вместе, не забыв вернуть тройное пересечение со знаком плюс:

$$|A \cup B \cup C| = 45 - 22 + 4 = 27.$$

Шаг 3. Считаем тех, кто не знает ни одного языка. Это дополнение объединения до универсума:

$$|\overline{A \cup B \cup C}| = |U| - |A \cup B \cup C| = 30 - 27 = 3.$$

Шаг 4. Раскладываем объединение на непересекающиеся области. Это главная проверка ответа: семь областей диаграммы Венна не пересекаются, поэтому их мощности обязаны дать в сумме мощность объединения. Область «только $A$» получается вычитанием обоих пересечений с возвратом тройного, которое вычли дважды:

$$\begin{aligned} |A \setminus (B \cup C)| &= 18 - 9 - 7 + 4 = 6, \\ |B \setminus (A \cup C)| &= 15 - 9 - 6 + 4 = 4, \\ |C \setminus (A \cup B)| &= 12 - 7 - 6 + 4 = 3. \end{aligned}$$

Области «ровно два языка» - это попарные пересечения без тройного: $9 - 4 = 5$ человек знают только Python и C++, $7 - 4 = 3$ только Python и Java, $6 - 4 = 2$ только C++ и Java. Плюс 4 человека со всеми тремя языками.

Сумма первых семи строк: $6 + 4 + 3 + 5 + 3 + 2 + 4 = 27$ - совпало с формулой, расчёт согласован. Все области неотрицательны, значит исходные данные задачи непротиворечивы.

Шаг 5. Мощность булеана. Булеан $\mathcal{P}(X)$ - множество всех подмножеств $X$, его мощность равна $2^{|X|}$. Для объединения из 27 элементов:

$$|\mathcal{P}(A \cup B \cup C)| = 2^{27} = 134\,217\,728.$$

Ответ. Хотя бы один язык знают 27 студентов, ни одного - 3 студента, мощность булеана объединения равна $2^{27} = 134\,217\,728$.

Формула включений и исключений: откуда она берётся

Для двух множеств всё видно на диаграмме Венна. Складывая $|A|$ и $|B|$, элементы пересечения считают дважды - один раз в составе $A$, другой раз в составе $B$. Чтобы каждый элемент был учтён ровно один раз, лишнюю копию вычитают:

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

Для трёх множеств поправка сложнее. Вычитая три попарных пересечения, элементы центральной области убирают трижды, хотя прибавлены они тоже были трижды, - в итоге они исчезают из подсчёта полностью. Поэтому тройное пересечение возвращают со знаком плюс. Дальше знаки чередуются: для $n$ множеств складывают одиночные мощности, вычитают пересечения по два, прибавляют по три и так далее. Общий вид формулы и разбор задач на делимость есть в статье про принцип включения-исключения, здесь она нужна только как рабочий инструмент.

Важно, что формула работает с любыми конечными множествами: студенты, числа, детали на складе. Единственное требование - корректно заданные входные данные. Если какая-то область при разложении вышла отрицательной, значит условие противоречиво: например, при $|A| = 10$, $|A \cap B| = 8$ и $|A \cap C| = 7$ без достаточного тройного пересечения элементов $A$ просто не хватает. Разложение по областям такую ошибку в условии ловит сразу, а голая формула объединения - нет.

Мощность булеана: почему подмножеств 2 в степени n

Булеан не про подсчёт элементов, а про подсчёт подмножеств, и тут работает правило произведения. Каждое подмножество однозначно задаётся ответами на $n$ независимых вопросов «входит ли элемент в подмножество»: да или нет. Вариантов ответа два, вопросов $n$, значит всего подмножеств

$$|\mathcal{P}(X)| = 2^{|X|}.$$

Пустое множество и само $X$ в этот счёт входят: им соответствуют наборы из одних «нет» и одних «да». Если в задаче просят собственные подмножества, из ответа вычитают само множество, если непустые - вычитают пустое. Отдельный частый подвопрос - число подмножеств ровно из $k$ элементов: это биномиальный коэффициент $\binom{n}{k}$, а сумма таких коэффициентов по всем $k$ снова даёт $2^n$. Подробный разбор степеней двойки и треугольника Паскаля - в статье про число подмножеств множества из n элементов, а раскрытие $(1 + 1)^n$ как источник этой суммы разобрано в задаче про бином Ньютона.

Вариация: числа от 1 до 1000, не делящиеся на 2, 3 и 5

Ту же формулу применяют к числовым множествам, только мощности считаются делением с округлением вниз. Пусть $A_k$ - множество чисел от 1 до 1000, кратных $k$. Тогда $|A_2| = 500$, $|A_3| = 333$, $|A_5| = 200$, а пересечения - это кратные произведениям: $|A_2 \cap A_3| = |A_6| = 166$, $|A_2 \cap A_5| = |A_{10}| = 100$, $|A_3 \cap A_5| = |A_{15}| = 66$, $|A_2 \cap A_3 \cap A_5| = |A_{30}| = 33$.

$$|A_2 \cup A_3 \cup A_5| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734.$$

Значит, не делится ни на 2, ни на 3, ни на 5 ровно $1000 - 734 = 266$ чисел. Схема решения та же, что и со студентами: объединение по формуле, потом дополнение до универсума. Полезно помнить, что пересечение множеств кратных считается через наименьшее общее кратное, и для взаимно простых делителей оно равно их произведению.

Бесконечные множества: счётные и континуальные

Для бесконечных множеств «число элементов» не определено, и мощность сравнивают биекцией: два множества равномощны, если между ними есть взаимно однозначное соответствие. Множество называют счётным, если его элементы можно занумеровать натуральными числами; его мощность обозначают $\aleph_0$. Счётны целые числа (нумерация зигзагом $0, 1, -1, 2, -2, \ldots$) и, вопреки интуиции, рациональные: их выписывают в таблицу и обходят по диагоналям.

Мощность отрезка и всей числовой прямой больше счётной: это континуум $\mathfrak{c} = 2^{\aleph_0}$. Доказывает это диагональный метод Кантора, он же показывает, что булеан всегда строго мощнее исходного множества даже в бесконечном случае - подробности в статье про теорему Кантора. Практический вывод для экзамена: конечная мощность считается формулой включений и исключений, бесконечная - предъявлением биекции или доказательством её отсутствия. Базовые операции, через которые всё это формулируется, разобраны в материале про объединение, пересечение и разность множеств.

Частые ошибки

• Забывают вернуть тройное пересечение. Ответ $45 - 22 = 23$ вместо 27 - самая массовая ошибка: центральная область при таком счёте пропадает совсем. Знаки в формуле строго чередуются.
• Путают «знают Python и C++» с «знают только Python и C++». В условии обычно дано пересечение целиком (9 человек), и в него входят те, кто знает все три языка. Чтобы получить область «ровно два языка», из 9 вычитают 4.
• Отвечают мощностью объединения на вопрос о дополнении. «Сколько не знает ни одного» - это $|U| - |A \cup B \cup C| = 3$, а не 27. Всегда проверяй, что именно спрашивают.
• Считают элементы вместо подмножеств. Мощность множества из 27 элементов равна 27, а мощность его булеана - $2^{27}$. Это разные вопросы, и путаница даёт расхождение в миллионы раз.
• Исключают пустое множество из булеана. Пустое множество и само множество - полноценные подмножества, они уже учтены в $2^n$; вычитать их нужно только если в условии прямо сказано «непустые» или «собственные».
• Не проверяют непротиворечивость данных. Если при разложении по областям какое-то число получилось отрицательным, ошибка не в арифметике, а в условии или в его прочтении.

FAQ

Чем мощность множества отличается от числа элементов? Для конечных множеств это одно и то же: $|A|$ и есть число элементов. Термин «мощность» шире, потому что он определён и для бесконечных множеств, где считать элементы нельзя, - там мощности сравнивают через биекции.

Как найти мощность объединения, если пересечения неизвестны? Точно найти нельзя, можно только оценить. Снизу мощность объединения не меньше наибольшей из мощностей слагаемых, сверху не превышает их суммы. Равенство сумме достигается ровно тогда, когда множества попарно не пересекаются.

Сколько подмножеств у множества из 5 элементов? Ровно $2^5 = 32$, включая пустое и само множество. Непустых подмножеств 31, собственных (не равных самому множеству) тоже 31, собственных и непустых одновременно - 30.

Могут ли бесконечные множества иметь разную мощность? Да. Натуральные и рациональные числа равномощны (оба счётны), а действительные строго мощнее: их мощность равна континууму $2^{\aleph_0}$. Именно поэтому бесконечность не одна, а образует бесконечную иерархию.

Коротко

1. Мощность конечного множества $|X|$ - число его элементов; для объединения работает формула включений и исключений.
2. Для трёх множеств: сложить одиночные мощности, вычесть три попарных пересечения, прибавить тройное.
3. В примере $18 + 15 + 12 - 9 - 7 - 6 + 4 = 27$ студентов знают хотя бы один язык, значит $30 - 27 = 3$ не знают ни одного.
4. Проверка: семь непересекающихся областей диаграммы Венна дают в сумме 27, все они неотрицательны.
5. Мощность булеана равна $2^{|X|}$: у объединения из 27 элементов $2^{27} = 134\,217\,728$ подмножеств.