Подготовка к проверочной 26 сентября. Множества, тождества, включения-исключения

Разбор пяти типовых задач к проверочной по теории множеств. Каждая задача — отдельный навык из лекции 1 и лекции 3: вычислить множество и выписать его булеан, доказать тождество, упростить выражение, записать формулу по картинке и посчитать людей по кругам Эйлера. Ниже — решение каждой задачи с оформлением, которое можно переносить в работу, и разбор мест, где легко потерять балл.

1. Множество по условию и его булеан

Задача 1. Найти $A$, $|A|$, $\mathcal{P}(A)$ и $|\mathcal{P}(A)|$, если

$A = \{x \mid x \in \mathbb{N},\ -1 \le x \le 4\} \cap \{y \mid y \in \mathbb{Z},\ 2 < y < 5\} \cup \{\{0\}\}.$

1.1. Вычисляем по частям

Пронумеруем множества и выпишем каждое перечислением.

1. $\{x \in \mathbb{N} \mid -1 \le x \le 4\} = \{0, 1, 2, 3, 4\}$. В курсе $\mathbb{N}$ начинается с нуля, а $-1 \notin \mathbb{N}$, поэтому нижняя граница ничего не добавляет.
2. $\{y \in \mathbb{Z} \mid 2 < y < 5\} = \{3, 4\}$: неравенства строгие, концы $2$ и $5$ не входят.
3. $(1) \cap (2) = \{3, 4\}$.
4. $A = \{3, 4\} \cup \{\{0\}\} = \{3, 4, \{0\}\}$.

Итак, $A = \{3, 4, \{0\}\}$ и $|A| = 3$. Третий элемент — не число $0$, а множество $\{0\}$ целиком: объединяем с $\{\{0\}\}$, а у него единственный элемент $\{0\}$.

То, что в первом множестве есть $0$ (или нет, если считать $\mathbb{N}$ с единицы), на ответ не влияет: после пересечения с $\{3, 4\}$ он всё равно пропадает. Но выписывать множество стоит правильно — за $\{1, 2, 3, 4\}$ вместо $\{0, 1, 2, 3, 4\}$ могут снять балл.

1.2. Булеан

По утверждению о мощности булеана $|\mathcal{P}(A)| = 2^{|A|} = 2^3 = 8$. Выписываем по размеру подмножества — так ничего не пропустить:

$\mathcal{P}(A) = \big\{\varnothing,\ \{3\},\ \{4\},\ \{\{0\}\},\ \{3, 4\},\ \{3, \{0\}\},\ \{4, \{0\}\},\ \{3, 4, \{0\}\}\big\}.$

Проверка: $1 + 3 + 3 + 1 = 8$ — это строка $3$ треугольника Паскаля, $C_3^0 + C_3^1 + C_3^2 + C_3^3$.

1.3. Принадлежность и включение для этого множества

Типичный дополнительный вопрос — расставить $\in$ и $\subseteq$. Правило из лекции 1: $x \in A$ — «$x$ есть в списке элементов $A$», $X \subseteq A$ — «каждый элемент $X$ есть в списке элементов $A$».

2. Доказательство тождества

Задача 2. Доказать, что $A \cap (B \setminus C) = (A \cap B) \setminus (A \cap C)$.

Смысл тождества: пересечение с $A$ можно «внести» в разность. Обе части описывают одну и ту же область — точки из $A$ и $B$, но не из $C$.

2.1. Способ первый: обе части к одному условию

Доказываем, что $x$ лежит в левой части тогда и только тогда, когда $x \in A$, $x \in B$ и $x \notin C$, и то же для правой. Тогда по экстенсиональности части равны.

Левая часть. Пусть $x \in A \cap (B \setminus C)$. По определению пересечения $x \in A$ и $x \in B \setminus C$, а по определению разности $x \in B$ и $x \notin C$. Итого:

$x \in A \cap (B \setminus C) \iff x \in A \wedge x \in B \wedge x \notin C.$

Правая часть. Пусть $x \in (A \cap B) \setminus (A \cap C)$. По определению разности $x \in A \cap B$ и $x \notin A \cap C$. Из первого: $x \in A$ и $x \in B$. Второе по де Моргану означает $x \notin A$ или $x \notin C$. Но $x \in A$ уже известно, поэтому вариант $x \notin A$ невозможен и остаётся $x \notin C$. Итого:

$x \in (A \cap B) \setminus (A \cap C) \iff x \in A \wedge x \in B \wedge x \notin C.$

Обе части задаются одним и тем же условием, значит, равны. $\blacksquare$

2.2. Способ второй: алгебра множеств

Разность выражается через дополнение: $X \setminus Y = X \cap \overline{Y}$. Тогда правая часть:

$$\begin{aligned} (A \cap B) \setminus (A \cap C) &= (A \cap B) \cap \overline{A \cap C} && \text{[разность через дополнение]} \\ &= (A \cap B) \cap (\overline{A} \cup \overline{C}) && \text{[де Морган]} \\ &= (A \cap B \cap \overline{A}) \cup (A \cap B \cap \overline{C}) && \text{[дистрибутивность]} \\ &= \varnothing \cup (A \cap B \cap \overline{C}) && [A \cap \overline{A} = \varnothing] \\ &= A \cap (B \cap \overline{C}) = A \cap (B \setminus C). && \text{[ассоциативность, разность]} \end{aligned}$$

$\blacksquare$

Это та же мысль, что «$x \notin A$ невозможно, раз $x \in A$»: слагаемое $A \cap B \cap \overline{A}$ пусто.

2.3. Проверка кругами Эйлера

Рисунок не доказательство, но быстро ловит ошибку в формулировке. Нарисуйте три круга и закрасьте каждую часть отдельно.

• Левая часть: $B \setminus C$ — часть $B$ вне $C$ (две области), пересечь с $A$ — остаётся одна область: внутри $A$ и $B$, вне $C$.
• Правая часть: $A \cap B$ — «линза» из двух областей, убрать из неё $A \cap C$ — уходит нижняя область линзы (та, что в $C$), остаётся та же одна область.

Закрашено одно и то же — тождество правдоподобно, теперь его можно доказывать.

3. Упрощение выражения

Задача 3. Упростить

$\overline{(\overline{A} \cap B) \cap (\overline{B} \cap C)} \cup \overline{C \cup \overline{A}}.$

3.1. Через законы де Моргана

Раскрываем дополнения снаружи внутрь. Дополнение пересечения — объединение дополнений, двойное дополнение снимается:

$$\begin{aligned} &\overline{(\overline{A} \cap B) \cap (\overline{B} \cap C)} \cup \overline{C \cup \overline{A}} \\ &= \overline{\overline{A} \cap B} \cup \overline{\overline{B} \cap C} \cup (\overline{C} \cap A) && \text{[де Морган для обоих слагаемых]} \\ &= (A \cup \overline{B}) \cup (B \cup \overline{C}) \cup (\overline{C} \cap A) && \text{[де Морган, } \overline{\overline{X}} = X\text{]} \\ &= A \cup (\overline{B} \cup B) \cup \overline{C} \cup (\overline{C} \cap A) && \text{[ассоциативность и коммутативность } \cup\text{]} \\ &= A \cup U \cup \overline{C} \cup (\overline{C} \cap A) = U. && [B \cup \overline{B} = U,\ X \cup U = U] \end{aligned}$$

Ответ: $U$.

3.2. Короткий путь

Внутри первого дополнения стоит пересечение четырёх множеств, среди которых есть $B$ и $\overline{B}$:

$(\overline{A} \cap B) \cap (\overline{B} \cap C) = \overline{A} \cap (B \cap \overline{B}) \cap C = \varnothing.$

Значит, первое слагаемое равно $\overline{\varnothing} = U$, а $U \cup$ что угодно $= U$. Второе слагаемое можно даже не трогать.

4. Формула по закрашенной диаграмме

Задача 4. На диаграмме трёх множеств закрашены: часть $A$ вне $B$ и $C$, часть $B$ вне $A$ и $C$, и центр $A \cap B \cap C$. Записать закрашенное множество $P$ формулой.

4.1. Восемь областей

Три круга делят универсум на восемь областей. Каждую удобно кодировать тремя битами — лежит ли точка в $A$, в $B$, в $C$, — как подмножества в лекции 1.

4.2. Собираем и упрощаем

Закрашены области $100$, $010$ и $111$. Сразу пишем объединение:

$P = \big(A \setminus (B \cup C)\big) \cup \big(B \setminus (A \cup C)\big) \cup (A \cap B \cap C).$

Это уже правильный ответ. Первые два слагаемых можно объединить: «ровно в одном из $A$, $B$ и не в $C$» — это симметрическая разность без $C$:

$P = \big((A \triangle B) \setminus C\big) \cup (A \cap B \cap C).$

Проверка по кодам: $A \triangle B$ — области, где первые два бита различны: $100$, $101$, $010$, $011$. Убираем $C$ — остаются $100$ и $010$. Добавляем $111$. Сходится.

Если нужен ответ без $\triangle$: $P = \big((A \cup B) \setminus C \setminus (A \cap B)\big) \cup (A \cap B \cap C)$ — тоже верно, но длиннее.

5. Включения-исключения

5.1. Формула

Для двух множеств при сложении $|A| + |B|$ пересечение посчитано дважды, поэтому его вычитают:

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

Для трёх множеств попарные пересечения вычитаются, но тогда центр $A \cap B \cap C$ оказывается вычтен столько же раз, сколько прибавлен, и его возвращают:

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

Проверка для точки из центра: в сумме $|A| + |B| + |C|$ она учтена $3$ раза, в попарных пересечениях вычтена $3$ раза, в тройном добавлена $1$ раз — итого $1$, как и надо.

Полезные следствия для трёх множеств:

• только $A$: $|A| - |A \cap B| - |A \cap C| + |A \cap B \cap C|$;
• ровно в двух: $|A \cap B| + |A \cap C| + |B \cap C| - 3\,|A \cap B \cap C|$;
• ни в одном: $|U| - |A \cup B \cup C|$.

5.2. Разбор задачи

Задача 5. Из $40$ человек в «КБ» бывают $22$, во «Flame» — $20$, в «Завтра» — $18$. В «КБ» и «Flame» — $10$, в «КБ» и «Завтра» — $8$, во «Flame» и «Завтра» — $7$, во всех трёх — $4$. Сколько человек бывают: только в «КБ»; только во «Flame»; только в «Завтра»; ровно в двух местах; хотя бы в одном; ни в одном?

Обозначим $K$, $F$, $Z$. Диаграмму заполняем от центра к краям — это главный приём.

1. Центр: $|K \cap F \cap Z| = 4$.
2. Попарные области без центра: $K \cap F$ без $Z$: $10 - 4 = 6$; $K \cap Z$ без $F$: $8 - 4 = 4$; $F \cap Z$ без $K$: $7 - 4 = 3$.
3. «Только» — из всего круга вычесть всё, что уже вписано внутрь него:
   • только $K$: $22 - 6 - 4 - 4 = 8$;
   • только $F$: $20 - 6 - 4 - 3 = 7$;
   • только $Z$: $18 - 4 - 4 - 3 = 7$.
4. Ровно в двух: $6 + 4 + 3 = 13$.
5. Хотя бы в одном — по формуле: $22 + 20 + 18 - 10 - 8 - 7 + 4 = 39$.
6. Ни в одном: $40 - 39 = 1$.

Проверка суммой всех семи областей внутри кругов: $8 + 7 + 7 + 6 + 4 + 3 + 4 = 39$ — совпадает с пунктом 5.

Если в условии даны не попарные пересечения, а «ровно в двух» и «ровно в трёх», формулу применять нельзя напрямую — сразу вписывайте числа в области диаграммы. Сумма по областям работает всегда.

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

• Считать $\mathbb{N}$ с единицы в дискретке. В курсе $0 \in \mathbb{N}$; на ответ задачи 1 это не влияет, но само множество должно быть выписано верно.
• Выполнять $\cup$ раньше $\cap$, когда скобок нет. Пересечение связывает сильнее, как $\wedge$ сильнее $\vee$.
• Путать $\{0\}$ и $\{\{0\}\}$ в булеане: одноэлементное подмножество из элемента $\{0\}$ — это $\{\{0\}\}$. Писать $\{\varnothing\}$ вместо $\{0\}$ тоже нельзя: в обычной записи $0$ — число, а не пустое множество.
• Считать, что $\{0\} \subseteq A$, раз $\{0\} \in A$. Для включения нужен элемент $0$ внутри $A$.
• Терять скобки после де Моргана: $\overline{A \cap C} = \overline{A} \cup \overline{C}$ внутри пересечения обязательно в скобках.
• В доказательстве тождества разобрать только одну сторону. Нужны оба направления — или два включения, или цепочка настоящих равносильностей.
• Выдавать диаграмму за доказательство. Круги — проверка, доказательство — логика или алгебра множеств с подписями законов.
• Не проверять формулу по диаграмме: $A \triangle B \triangle C$ выглядит похоже на ответ задачи 4, но закрашивает лишнюю область.
• Вписывать попарные пересечения в диаграмму без вычета центра.

Мини-тренажёр

1. Найдите $A = \{x \in \mathbb{Z} \mid x^2 < 5\} \cap \{x \in \mathbb{N} \mid x \ge 1\} \cup \{\varnothing\}$, $|A|$ и $|\mathcal{P}(A)|$. Верно ли $\varnothing \in A$? $\{\varnothing\} \subseteq A$?
2. Докажите, что $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.
3. Упростите $\overline{A \cup \overline{B}} \cup \overline{\overline{A} \cup \overline{B}}$.
4. Упростите $(A \cap \overline{B} \cap C) \cap \overline{(A \cup C)}$.
5. Запишите формулой множество точек, лежащих ровно в двух из трёх множеств $A$, $B$, $C$.
6. В группе $30$ студентов. Python знают $18$, C++ — $15$, Go — $10$; Python и C++ — $8$, Python и Go — $5$, C++ и Go — $4$, все три языка — $2$. Сколько студентов знают только Python, ровно два языка, ни одного языка?

Ответы

1. $\{x \in \mathbb{Z} \mid x^2 < 5\} = \{-2, -1, 0, 1, 2\}$, пересечение с $\{1, 2, 3, \dots\}$ даёт $\{1, 2\}$, итого $A = \{1, 2, \varnothing\}$, $|A| = 3$, $|\mathcal{P}(A)| = 8$. $\varnothing \in A$ — да, он выписан элементом. $\{\varnothing\} \subseteq A$ — да, его единственный элемент $\varnothing$ лежит в $A$.
2. $x \in A \setminus (B \cap C) \iff x \in A \wedge \neg(x \in B \wedge x \in C) \iff x \in A \wedge (x \notin B \vee x \notin C) \iff (x \in A \wedge x \notin B) \vee (x \in A \wedge x \notin C) \iff x \in (A \setminus B) \cup (A \setminus C)$. Шаги: определения, де Морган, дистрибутивность, определения. $\blacksquare$
3. По де Моргану $\overline{A \cup \overline{B}} = \overline{A} \cap B$ и $\overline{\overline{A} \cup \overline{B}} = A \cap B$. Объединение: $(\overline{A} \cap B) \cup (A \cap B) = (\overline{A} \cup A) \cap B = U \cap B = B$.
4. $\overline{A \cup C} = \overline{A} \cap \overline{C}$, и в пересечении оказываются $A$ и $\overline{A}$. Ответ: $\varnothing$.
5. $\big((A \cap B) \cup (A \cap C) \cup (B \cap C)\big) \setminus (A \cap B \cap C)$ — области $110$, $101$, $011$.
6. Только Python: $18 - 8 - 5 + 2 = 7$. Ровно два: $(8 - 2) + (5 - 2) + (4 - 2) = 11$. Хотя бы один: $18 + 15 + 10 - 8 - 5 - 4 + 2 = 28$, ни одного: $30 - 28 = 2$. Проверка: только C++ $= 15 - 8 - 4 + 2 = 5$, только Go $= 10 - 5 - 4 + 2 = 3$, и $7 + 5 + 3 + 11 + 2 = 28$.

Шпаргалка