Множества и операции над ними: объединение, пересечение, дополнение

У вас 200 друзей во «Вконтакте», 150 в Telegram, и 60 из них сидят в обоих местах. Сколько всего у вас знакомых? Мозг мгновенно отвечает «350» — и ошибается. Правильный ответ 290, потому что 60 человек посчитаны дважды. Чутьё, которое только что сработало, — это самая первая формула дискретной математики, а весь язык, на котором она записана, называется теорией множеств. Это алфавит всего предмета: графы, отношения, автоматы дальше по курсу будут определяться через множества.

Множество: коробка, в которой каждый элемент либо есть, либо нет#

Множество — это набор различных объектов, мыслимый как единое целое. Объекты внутри называют элементами. Ключевая особенность: элемент либо принадлежит множеству, либо нет — третьего не дано. Пишут $x\in A$ («икс лежит в A») и $x\notin A$ («не лежит»). Задать множество можно перечислением, как $A=\{1,2,3\}$, или правилом: $B=\{n\in \mathbb{N}:n$ — чётное$\}$.

Порядок и повторы внутри множества ничего не значат. Списки $\{1,2,3\}$, $\{3,1,2\}$ и $\{1,1,2,3\}$ — это одно и то же множество. Отсюда забавное следствие: у списка из трёх покупок в чеке может быть всего два различных товара.

• $\varnothing$ — пустое множество, в котором нет ни одного элемента (вилка в спальне из списка обязательной мебели)
• $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ — натуральные, целые, рациональные и действительные числа: знакомые бесконечные множества
• $\{-2,0,7\}$ — конечное множество из трёх элементов; говорят, его мощность $|A|=3$
• $\{x\in \mathbb{R}:x^2<0\}$ — так аккуратно записывается пустое множество через правило: ни одно число не даёт отрицательный квадрат

Множество $A$ называется подмножеством множества $B$, если каждый элемент из $A$ лежит и в $B$. Обозначение $A\subseteq B$. Равенство множеств проверяется с двух сторон: $A=B$, когда $A\subseteq B$ и $B\subseteq A$. На практике это удобно: доказать, что два «разных на вид» множества совпадают, значит взять произвольный элемент из каждого и показать, что он лежит в другом.

Операции: объединение, пересечение и компания#

Из двух множеств можно собирать новые. Представьте два круга на листе бумаги (диаграммы Эйлера-Венна, которые вы наверняка рисовали в школе) — каждая операция красит свою часть листа.

Про разность студенты спотыкаются меньше всего, а вот дополнение требует одной оговорки. Дополнение не определено без универсума: если $A$ — множество блондинов, то «всё, что не $A$» — это и камни, и звёзды, и числа? На практике фиксируют универсум $U$ — весь мир задачи (например, все студенты курса), и дополнение берут внутри него: $\overline{A}=U\setminus A$.

Проверьте сами: $A△A=\varnothing$, а $A\cup \varnothing =A$. Симметрическая разность отвечает на вопрос «у кого есть ровно один из двух признаков» — так считают клиентов, купивших в первом магазине, но не во втором.

Считаем элементы: включения-исключения#

Вот та самая формула из вступления. Формула включений и исключений для двух множеств:

Каждый символ здесь расшифровывается так: $|A|$ — мощность (число элементов) множества $A$; $|B|$ — мощность $B$; $|A\cap B|$ — число элементов в пересечении, которые при простом сложении попали в сумму два раза. Пример с числами: в группе 30 человек ходят на матан ($|A|=30$), 25 на физику ($|B|=25$), и 10 успевают оба ($|A\cap B|=10$). Тогда $|A\cup B|=30+25-10=45$ человек посещают хотя бы один предмет.

Для трёх множеств формула растёт, но логика та же: прибавляем одиночные множества, вычитаем все парные пересечения (мы дважды вычли то, что лежит в двух), возвращаем тройное (его вычли слишком усердно — трижды, а надо посчитать один раз):

Числовой прогон: $|A|=18$, $|B|=13$, $|C|=16$, пары: $7,8,5$, тройка $2$. Считаем: $18+13+16=47$; $47-7-8-5=27$; $27+2=29$. Ровно 29 человек охвачены хотя бы одним множеством.

Алгебра множеств и декартово произведение#

Операции над множествами подчиняются законам, которые выглядят подозрительно знакомо — те же законы будут у логических операций. Коммутативность: $A\cup B=B\cup A$. Ассоциативность: скобки в $A\cup B\cup C$ не важны. Дистрибутивность — причём дважды: $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ и зеркальная $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.

Главные законы — де Моргана: дополнение переворачивает операцию. $\overline{A\cup B}=\overline{A}\cap \overline{B}$: «не (A или B)» значит «не A и не B». Проверка на пальцах: $A=\{1,2\}$, $B=\{2,3\}$, $U=\{1,2,3,4\}$. Тогда $\overline{A\cup B}=\overline{\{1,2,3\}}=\{4\}$, а $\overline{A}\cap \overline{B}=\{3,4\}\cap \{1,4\}=\{4\}$. Совпало.

Отдельная операция — декартово произведение $A\times B$: множество всех упорядоченных пар $(a,b)$, где $a\in A$, $b\in B$. Порядок и повторы тут важны — в отличие от самого множества. Мощность считается элементарно: $|A\times B|=|A|\cdot |B|$. Меню из 4 супов и 5 салатов даёт $20$ комбинаций «суп + салат». На парах $(a,b)$ строятся отношения и соответствия — следующий урок этого курса.

Куда всё это ведёт? Множества — сырьё для всей дискретки: граф — это множество вершин и множество рёбер (см. словарную статью граф), вероятностные события — тоже множества, а подсчёт комбинаций продолжается в тренажёре комбинаторики. Уверенно оперируйте значками $\cup ,\cap ,\setminus$ — и остальной курс пойдёт легче.

Обратная постановка — самый коварный вариант задачи: дано объединение, а ищут пересечение. В классе 20 человек, 12 из них любят математику, 15 — физику, и каждый увлекается хотя бы чем-то одним. Сколько увлекаются обоими предметами сразу? Интуиция молчит, а формула щёлкает: раз каждый любит хоть что-то, то $|A\cup B|=20$, и тогда $|A\cap B|=12+15-20=7$. Семь человек сидят в обоих списках.

1. 1
   Записали любителей матана списком — 12 фамилий, любителей физики — 15 фамилий.
2. 2
   Сложили списки: получилось 27 записей, а людей в классе всего 20.
3. 3
   Каждый «дважды записанный» человек дал лишнюю запись: $27-20=7$ дублей.
4. 4
   Вывод: $|A\cap B|=7$. Формула включений-исключений читается и справа налево.

• $\cup$ — «или», $\cap$ — «и», черта сверху — «не»: алфавит множеств переводится в логику слово в слово.
• Объединение — не меньше каждого слагаемого, пересечение — не больше меньшего.
• Включения-исключения: нечётные пересечения с плюсом, чётные с минусом (для трёх множеств: одиночные +, пары −, тройка +).
• Ответ «сколько не попало никуда» — всегда дополнение: $N$ минус объединение.
• Сомневаетесь в законе — проверьте на крошечных множествах $\{1,2\}$ и $\{2,3\}$: быстрее, чем перечитывать конспект.

Операции над множествами проще всего почувствовать на диаграммах Венна: добавьте элементы в зоны кликом и посмотрите, какие области высвечивает каждая операция.