СВ в 14:13, 24 октября 2026

2026-10-24T14:13:55Z

← Предыдущая		Версия 14:13, 24 октября 2026
Строка 34:		Строка 34:
	Перенесем все слагаемые, кроме первого, за знак равенства и получим искомое утверждение.		Перенесем все слагаемые, кроме первого, за знак равенства и получим искомое утверждение.
	}}		}}

			[[Файл:p31-01-union-cardinality.svg\|frame\|none\|900px\|alt=Три пересекающихся множества с числами по областям; формула 17−7+1=11\|Рис. 1. Сумма мощностей <math>6+4+7=17</math> считает парные пересечения дважды, а тройное — трижды; вычитаем пары <math>2+3+2=7</math> и прибавляем тройное <math>1</math>. Получаем <math>\|A\cup B\cup C\|=17-7+1=11</math>.]]

	Конспект: [[Дискретная математика]]		Конспект: [[Дискретная математика]]

	[[Категория:Дискретная математика]]		[[Категория:Дискретная математика]]

СВ: Новая страница: «{{Пример |content=Пусть $A_1$, $A_2$, ..., $A_k$ {{---}} конечные множества. Пусть $A = A_1\cup A_2\cup ...\cup A_k$. Требу...»

2026-10-11T10:10:23Z

Новая страница: «{{Пример |content=Пусть $A_1$, $A_2$, ..., $A_k$ {{---}} конечные множества. Пусть $A = A_1\cup A_2\cup ...\cup A_k$. Требу...»

Новая страница

{{Пример
|content=Пусть $A_1$, $A_2$, ..., $A_k$ {{---}} конечные множества.
Пусть $A = A_1\cup A_2\cup ...\cup A_k$.
Требуется найти мощность $A$, если известны $|A_i|$, $i=\overline{1,k}$, и
$|\bigcap_{i\in I} A_i|$, $I\subseteq \{1,2,...,k\}$.
}}

Пусть $S = \{1,2,...,k\}$ и $T\subseteq S$.
Будем говорить, что $x\in A$ обладает свойством $i$, если $x\in A_i$.

Обозначим $f_=(T)$ {{---}} число элементов из $A$, обладающих всеми свойствами из $T$
и не обладающих другими свойствами из $S$;

$f_\geq(T)$ {{---}} число элементов из $A$, обладающих всеми свойствами из $T$.

Очевидно, $f_\geq (T) = |\bigcap_{i\in T} A_i|$, если $T$ не пусто и $f_\geq (\varnothing) = |A|$

Тогда можно использовать формулу включения-исключения.
{{Утверждение
|statement=<math>|A_1\cup A_2\cup ...\cup A_k| =
\sum_{i=1}^{k}|A_i| - \sum_{1\leq i_1 \lt i_2\leq k} |A_{i_1}\cap A_{i_2}| +
+ \sum_{1\leq i_1 \lt i_2 \lt i_3\leq k} |A_{i_1}\cap A_{i_2}\cap A_{i_3}|
- \cdots + (-1)^{k+1}|A_1\cap A_2\cap ... \cap A_k|.
</math>
|proof=Поскольку каждый элемент из $A$ обладает хотя бы одним свойством из $S$, то $f_=(\varnothing) = 0$.
С другой стороны, из формулы включения-исключения получаем
<math>
0 = f_=(\varnothing)= \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y) =
|A| + \sum_{\substack{Y\subseteq S,\\|Y|\geq 1}} (-1)^{|Y|} |\bigcap_{i\in Y} A_i| =
</math>
<math>=|A|- \sum_{i=1}^{k}|A_i| + \sum_{1\leq i_1 \lt i_2\leq k} |A_{i_1}\cap A_{i_2}| -
\sum_{1\leq i_1 \lt i_2 \lt i_3\leq k} |A_{i_1}\cap A_{i_2}\cap A_{i_3}| + \cdots + (-1)^{k}|A_1\cap A_2\cap ... \cap A_k|.
</math>
Перенесем все слагаемые, кроме первого, за знак равенства и получим искомое утверждение.
}}

Конспект: [[Дискретная математика]]

[[Категория:Дискретная математика]]

Мощность объединения множеств - История изменений

СВ в 14:13, 24 октября 2026

СВ: Новая страница: «{{Пример |content=Пусть $A_1$, $A_2$, ..., $A_k$ {{---}} конечные множества. Пусть $A = A_1\cup A_2\cup ...\cup A_k$. Требу...»