Задача. Пусть даны подмножества $ A_1,A_2,\dots,A_{\mathfrak r} $ (необязательно различные) некоторого конечного множества. Найти мощность (число элементов) их объединения $$ \operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r}) \ . $$ В качестве первого приближения искомого числа можно принять значение $$ \operatorname{Card}(A_1) + \operatorname{Card}(A_2) + \dots + \operatorname{Card}( A_{\mathfrak r}) \ , $$ однако это число в общем случае слишком большое, так как если $ A_{j} \cap A_k \ne \varnothing $, то элементы этого пересечения учитываются в последней сумме дважды. Для исправления ситуации, вычтем «лишнее»: $$ \operatorname{Card}(A_1) + \operatorname{Card}(A_2) + \dots + \operatorname{Card}( A_{\mathfrak r}) - \sum_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) \ . $$ Эта формула оказывается точной, если только отсутствуют тройки подмножеств $ A_j, A_k, A_{\ell} $ со свойством $ A_j \cap A_k \cap A_{\ell} \ne \varnothing $. В последнем случае формулу придется снова корректировать «в сторону увеличения»:

При наличии большего числа множеств процедуру приходится продолжать.

Теорема. Справедлива формула включений-исключений: $$ \operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r}) = $$ $$ =\sum_{j=1}^{\mathfrak r} \operatorname{Card}(A_j) - \sum_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) + $$ $$ + \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) - \dots + $$ $$ *(-1)^{\mathfrak r-1} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r}) \ . $$

Доказательство. Применим индукцию по числу подмножеств $ \mathfrak r_{} $. При $ \mathfrak r_{}=2 $ формула, очевидно, справедлива. Предположим, что формула справедлива для произвольных подмножеств $ A_1,A_2,\dots,A_{\mathfrak r-1} $: $$ \operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1}) = $$ $$ =\sum_{j=1}^{\mathfrak r-1} \operatorname{Card}(A_j) - \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2}) + \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) - \dots + $$ $$ +(-1)^{\mathfrak r-2} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1}) \ . $$ Применим эту формулу к сумме $$ (A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1}) \cap A_{\mathfrak r} = (A_1 \cap A_{\mathfrak r}) \cup (A_2 \cap A_{\mathfrak r}) \cup \dots \cup (A_{\mathfrak r-1} \cap A_{\mathfrak r}) \ , $$ получаем: $$ \operatorname{Card} \left( (A_1 \cap A_{\mathfrak r}) \cup (A_2 \cap A_{\mathfrak r}) \cup \dots \cup (A_{\mathfrak r-1} \cap A_{\mathfrak r}) \right)= $$ $$ \sum_{j=1}^{\mathfrak r-1} \operatorname{Card}(A_j \cap A_{\mathfrak r}) - \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{\mathfrak r}) + \dots + $$ $$ + (-1)^{\mathfrak r-2} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1} \cap A_{\mathfrak r}) \ . $$ Отсюда имеем: $$ \operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r}) = $$ (применяем формулу включений-исключений для случая двух подмножеств) $$ =\operatorname{Card} \left( (A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1}) \cap A_{\mathfrak r} \right)= $$ $$=\operatorname{Card} \left( A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1} \right) + \operatorname{Card} (A_{\mathfrak r}) - \operatorname{Card} \left( (A_1 \cap A_{\mathfrak r}) \cup (A_2 \cap A_{\mathfrak r}) \cup \dots \cup (A_{\mathfrak r-1} \cap A_{\mathfrak r}) \right) = $$ (применяем индукционное предположение и выведенную из него предыдущую формулу): $$ \begin{array}{lllll} = \displaystyle \sum_{j=1}^{\mathfrak r-1} \operatorname{Card} (A_j) & - \displaystyle \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2}) & + \displaystyle \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) & - \dots + & (-1)^{\mathfrak r-2} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1}) \\ + \displaystyle \operatorname{Card} (A_{\mathfrak r}) &- \displaystyle \sum_{j=1}^{\mathfrak r-1} \operatorname{Card} (A_j \cap A_{\mathfrak r}) & + \displaystyle \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{\mathfrak r}) & - \dots & + (-1)^{\mathfrak r-1} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1} \cap A_{\mathfrak r}) = \\ = \displaystyle \sum_{j=1}^{\mathfrak r} \operatorname{Card}(A_j) & - \displaystyle \sum_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) & + \displaystyle \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) & - \dots & + (-1)^{\mathfrak r-1} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r}) \ . \end{array} $$ ♦

Результат теоремы можно переформулировать на языке формальной логики:

Теорема. Пусть даны $ N_{} $ произвольных объектов. Пусть

• $ N_1 $ — число тех из них, которые обладают некоторым свойством $ \alpha_1 $;
• $ N_{2} $ — число тех, которые обладают свойством $ \alpha_2 $;
• …;
• $ N_{\mathfrak r} $ — число тех, которые обладают свойством $ \alpha_{\mathfrak r} $.

Аналогично пусть

• $ N_{1,2} $ — число тех из этих объектов, которые обладают одновременно свойствами $ \alpha_1 $ и $ \alpha_2 $;
• $ N_{1,3} $ — число тех из этих объектов, которые обладают одновременно свойствами $ \alpha_1 $ и $ \alpha_3 $;
• …
• $ N_{1,2,3} $ — свойствами $ \alpha_1,\alpha_2 $ и $ \alpha_3 $;
• …
• $ N_{1,2,3 \dots,\mathfrak r} $ — свойствами $ \alpha_1,\alpha_2, \alpha_3 , \dots, \alpha_{\mathfrak r} $.

Тогда число объектов, которые не обладают ни одним из свойств $ \alpha_1,\alpha_2, \alpha_3, \dots , \alpha_{\mathfrak r} $ равно $$N-\sum_{1\le j \le {\mathfrak r}} N_{j} + \sum_{1\le j_1 < j_2 \le {\mathfrak r}} N_{j_1,j_2} - \sum_{1\le j_1 < j_2 < j_3 \le {\mathfrak r}} N_{j_1,j_2,j_3} +\dots +(-1)^{\mathfrak r} N_{1,2,3,\dots,\mathfrak r} \ . $$

После прихода Гитлера к власти, в Германии появился анекдот:

«Такие человеческие качества как ум, честность и членство в NSDAP могут существовать только попарно.»

Пусть в группе из $ 100 $ человек $ 50 $ человек — умных, $ 40 $ — честных, $ 35 $ — партийных, $ 10_{} $ — умных и честных, $ 20 $ — умных и партийных, $ 15 $ — честных и партийных, $ 5 $ — умных, честных и партийных. Определить количество беспартийных и нечестных дураков в группе.

[1]. Липский В. Комбинаторика для программистов. М.Мир. 1988