Текст выступления:

Формула включения-исключения. Взаимно однозначное соответствие
1. Две важные идеи подсчёта: формула включения-исключения и взаимно однозначное соответствие

Точный подсчёт без ошибок и лишних повторов — это навык, который выручает в задачах, где одно и то же встречается несколько раз. Сегодня разберём две идеи: как аккуратно «чинить» двойной счёт и как доказывать равенство количеств не догадкой, а строгим соответствием.

2. Зачем нужны строгие способы счёта в 8 классе

На этом этапе уже мало просто сложить числа: в задачах появляются пересечения, повторы и скрытые совпадения. Здесь и проявляются два инструмента. Первый — формула включения-исключения: она учитывает общие элементы. Второй — взаимно однозначное соответствие: оно превращает «кажется, что одинаково» в строгое утверждение, подкреплённое построением.

3. Множества, объединение и пересечение

Все начнём с языка, на котором говорят задачи про счёт. Есть множество — набор объектов со своим правилом выбора. Объединение двух множеств отвечает на вопрос: «Что входит хотя бы в одно?» Пересечение — «Что попадает и туда, и туда».

Важно видеть, что пересечение — это не абстракция, а реальная причина ошибок при простом сложении. Когда берут |A| + |B|, они как будто считают все элементы A и все элементы B «по отдельности», не замечая, что некоторые элементы оказались посчитанными дважды — именно те, что лежат в пересечении.

Отсюда практическая мысль: прежде чем считать, стоит мысленно разделить элементы на три части — только из первого множества, только из второго и общие. Тогда станет ясно, почему «объединение» требует особого обращения с пересечением.

4. Схема подсчёта для двух множеств

Представим процесс как последовательность шагов.

Сначала отдельно считаем элементы первого множества и элементы второго множества — это этап «каждое само по себе». Но на таком шаге общие элементы неизбежно попадают два раза: сначала как элементы первого множества, затем как элементы второго.

Поэтому следующий этап — корректировка двойного счёта: вычитаем количество элементов пересечения. Тогда каждый объект окажется учтён ровно один раз — и только тогда объединение будет посчитано правильно.

Именно эта логика лежит в основе формулы включения-исключения для двух множеств: «сложили раздельно, а потом убрали лишнее совпадение».

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

Попробуем увидеть ошибку без сложной алгебры. Если множества пересекаются, то есть объекты, которые относятся и к первому, и ко второму множеству, то при сложении |A| + |B| каждый такой объект учитывается дважды.

Представьте, что в классе есть кружок «рисунок» и секция «шахматы». У кого-то может быть и то, и другое — например, один и тот же ученик. Когда считают «сколько всего», простое сложение превратит таких учеников в «два разных ответа», хотя в реальности это один человек.

Чем больше общих элементов, тем заметнее расходятся результаты. Наивная сумма не распознаёт совпадения, а формула сразу делает исправление: вычитает то, что было посчитано лишний раз.

Вывод здесь почти строгий: если пересечение не пусто, простое сложение завышает число элементов объединения ровно на размер пересечения.

6. Пример из школьной жизни: кружки и секции

В реальной школьной жизни пересечения встречаются постоянно. Допустим, нужно посчитать, сколько учеников посещают хотя бы один из двух кружков: «робототехника» и «программирование».

Если взять только списки и сложить их длины, то ученики, участвующие в обоих направлениях, будут учтены дважды. Поэтому возникает вопрос не «какая цифра больше», а «какие именно ученики входят в объединение».

Чтобы подсчёт был честным, полезно мыслить так: отдельные участники первого кружка, отдельные участники второго и общие — те, кто относится к обоим сразу. Тогда пересечение перестаёт быть туманным словом и превращается в конкретную группу людей.

Этот бытовой пример показывает ту же идею, что и формула: двойной счёт исчезает только тогда, когда пересечение учитывается особым образом.

7. Формулы для двух и трёх множеств

Когда множеств становится больше, проблема усложняется не потому, что меняется математика, а потому, что появляются новые уровни пересечений.

Для двух множеств всё просто: сложили отдельно, затем вычли то, что посчитали дважды. Но если множеств три, то появляются элементы, которые лежат сразу в двух множествах, и элементы, которые лежат во всех трёх. В таком случае не работает один шаг «вычесть пересечение» — исправление нужно сделать аккуратно дважды на разных уровнях.

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

Именно поэтому появляются чередования: добавляем один уровень пересечений, затем вычитаем следующий, и так восстанавливаем точный общий итог.

8. Почему формула работает без ошибок

Формула включения-исключения работает потому, что она не «угадана», а подстроена под то, как элемент может принадлежать множествам.

У каждого объекта есть один из вариантов «на скольких множествах он лежит». Если объект лежит только в одном множестве, то при последовательном подсчёте его вклад появляется один раз и не требует исправлений. Если объект лежит в двух множествах, он попадаёт в счёт дважды — и как раз поэтому возникает вычитание пересечения.

А если объект лежит в трёх и более множествах, то простая схема «вычесть одно пересечение» уже не хватает: он успевает попасть в разные комбинации подсчёта несколько раз. Тогда на помощь приходит поэтапная корректировка.

Так что формула — это метод контроля повторов: каждый элемент проходит свой путь через сложения и вычитания, а итоговый вклад выходит ровно единицей или нулём в зависимости от того, входит ли объект в объединение.

9. Чередование знаков в общей формуле

Чередование знаков удобно воспринимать как «маршрут исправлений». Последовательность действий подсказывает структуру формулы: сначала складываем отдельные множества, затем вычитаем пересечения, потом снова прибавляем пересечения следующего уровня глубины — и так далее.

Здесь важно понимать: знаки — не просто правило «для запоминания». Они отражают, сколько раз объект оказывается посчитанным на каждом этапе.

Когда на некотором уровне пересечений мы видим, что объекты уже были учтены слишком часто, действие становится вычитанием. А когда выясняется, что определённые объекты, наоборот, «исчезли из-за предыдущих исправлений», их возвращают добавлением на следующем шаге.

Итоговый смысл можно сформулировать так: чередование знаков — это способ поэтапно компенсировать лишние совпадения и добиться точного счёта.

10. Какие задачи решаются с помощью включения-исключения

Включение-исключение — универсальный инструмент именно для задач, где есть пересечения и повторный учёт.

Во-первых, это подсчёт «сколько объектов удовлетворяют хотя бы одному условию», когда условия пересекаются. Например: «сколько учеников посещают хотя бы один из кружков», где у некоторых есть несколько занятий.

Во-вторых, это задачи на «сколько объектов удовлетворяют хотя бы двум признакам, но не всем сразу» — когда нужно аккуратно исключить общий слой объектов, который мешает правильному подсчёту.

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

И всегда за этими задачами стоит один и тот же принцип: сначала суммируют раздельные вкладки, а затем исправляют, вычитая или добавляя пересечения так, чтобы каждый объект попал в итог ровно один раз.

11. Взаимно однозначное соответствие: что это такое

Теперь вторая ключевая идея — взаимно однозначное соответствие.

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

Смысл двойной проверки важен. Если каждому элементу слева найдена единственная «пара» справа, то соответствие не размывается: нет ситуации, когда один элемент обслуживает сразу нескольких «клиентов». А если при этом ни один элемент справа не остался без пары, то мы не теряем элементы.

Такое соответствие превращает абстрактное сравнение в конструкцию: вместо «кажется, одинаково» появляется строгий маршрут от элементов к элементам.

12. Проверка взаимно однозначного соответствия

Проверка взаимно однозначного соответствия выглядит как два контроля.

Первый контроль — уникальность: каждой точке слева соответствует одна точка справа. То есть выбор не должен приводить к повторениям пар. Если один и тот же элемент справа соответствует двум разным элементам слева, значит соответствие неверное.

Второй контроль — полнота: нужно убедиться, что среди точек справа нет «потерянных» элементов, которым не нашлось пары. Если такое произошло, значит слева элементов меньше, чем справа, и равное количество не доказано.

Когда выполняются оба условия — и повторов нет, и пропусков нет — тогда соответствие действительно взаимно однозначное.

И тогда равномощность считывается как прямое следствие построения: каждый элемент «нашёл своё место» без разрывов и накладок.

13. Как распознают равномощность

Равномощность распознают не только подсчётом, но и подтверждением структуры: удалось ли установить взаимно однозначное соответствие.

Практический принцип такой: если есть способ поставить элементы в пары, причём ни одной стороне не достаётся «лишних» элементов и не остаётся «незапаренных», то количества равны.

Иногда это делают через наглядные соответствия, а иногда — через систематическое построение по правилам. Например, когда объекты можно упорядочить и затем сопоставлять первый с первым, второй со вторым и так далее.

Важная мысль: равномощность — это не «равенство по виду». Даже если множества выглядят по-разному, взаимно однозначное соответствие показывает одинаковую мощность — количество элементов.

14. Примеры биекции в математике

Хороший способ почувствовать биекцию — посмотреть на двоичные строки.

Каждый разряд двоичной строки даёт два выбора: либо 0, либо 1. Если строка длины n, то количество вариантов растёт очень быстро: каждый новый разряд удваивает число строк.

Здесь биекция помогает увидеть закономерность «как точный счёт через выборы», а не как длинный перебор. Закон виден сразу: при добавлении одного разряда количество строк удваивается.

Технически биекция в таких примерах показывает, что разные наборы решений ведут к разным строкам без повторов и без пропусков. Поэтому рост не кажется случайным — он подтверждён соответствием.

Такой учебный сюжет удобен тем, что объединяет два навыка: понимание «выборов» и проверку равенства количеств через построение соответствия.

15. Как две темы связаны между собой

Обе темы на самом деле про одно: про точность учёта.

Формула включения-исключения нужна, когда есть пересечения: она помогает исправить двойной или тройной счёт так, чтобы итоговая сумма стала правильной.

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

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

В результате появляется единая идея: строгий подсчёт — это не только арифметика, но и доказательная логика. Именно поэтому эти темы так хорошо дополняют друг друга в курсе математики.

16. Сравнение двух методов подсчёта

Есть два мощных способа, которые помогают находить количество объектов, но «включаются» они по-разному. Оба дают точный результат, если рассуждать аккуратно, однако один больше подходит для поиска объединений, а другой — для сравнения множеств через равные пары.

Если в задаче речь о том, сколько всего элементов попадает хотя бы в одно множество — например, «какие-то ученики выбрали кружок А или кружок B», — то возникает пересечение: часть учеников попадает в оба кружка сразу. Тогда легко случайно посчитать этих людей дважды. Поэтому включение–исключение и помогает: оно работает как корректировка двойного учёта. Сначала можно суммировать, но затем обязательно «забрать назад» пересечение, а при необходимости — сделать ещё точнее с учётом следующих пересечений.

Если же нужно не «объединение», а сравнить два количества и доказать, что они равны, удобнее другой инструмент — поиск биекции. Биекция означает взаимно однозначное соответствие: каждому объекту из первого множества соответствует ровно один объект из второго, и наоборот. Тогда точность возникает не из вычислений, а из строгого соответствия: сколько объектов в первой группе — столько же в другой.

Итак, в обоих подходах ключ один: проверка. Включение–исключение требует не забыть пересечения, а биекция — не принять частичное совпадение за полное соответствие. Точность рождается там, где условия действительно проверены, а не предполагаются «на глаз».

17. Классический пример биекции: двоичные строки

Хороший способ почувствовать биекцию — посмотреть на простой, но очень наглядный пример с двоичными строками.

Представим два множества:

множество двоичных строк фиксированной длины n;
множество способов выбрать подмножество из множества {1, 2, …, n}.

Как построить соответствие? Для каждой двоичной строки выбирается подмножество индексов, где стоят единицы. Если в строке в позиции i стоит 1, то число i попадает в выбранное подмножество; если 0 — не попадает.

Это уже похоже на «кодирование»: единицы помечают, что именно выбрано. Но важно не просто сопоставить — важно показать, что сопоставление взаимно однозначно.

Обратная дорога такая же короткая: если заранее задано подмножество индексов, то строится двоичная строка, где на местах выбранных индексов стоят 1, а на остальных — 0.

Здесь рождается биекция: каждая двоичная строка приводит к ровно одному подмножеству, и каждое подмножество приводит к ровно одной двоичной строке. Значит, эти множества имеют одинаковое количество элементов.

Почему это полезно? Потому что таким образом можно доказывать формулы «не вычисляя», а показывая соответствие. Например, количество двоичных строк длины n равно числу подмножеств множества из n элементов — и это легко переносится на самые разные задачи дискретной математики.

18. Типичные ошибки при решении задач

Когда методы понятны, ловушки всё равно остаются. Типичные ошибки чаще связаны не с математикой «как таковой», а с невнимательной проверкой условий задачи.

Для включения–исключения самая частая проблема — пропустить пересечение. Например, если перечисляют «сколько объектов попадает в А» и «сколько попадает в B», то сумма этих двух чисел почти всегда будет завышать ответ ровно на количество элементов, принадлежащих одновременно обоим множествам. Ошибка может выглядеть почти незаметной: человек вроде бы «знает формулу», но в тексте задачи просто не выделяет пересечение отдельно.

Для задач на биекцию другая проблема: принять частичное соответствие за полное. Бывает, что для части элементов соответствие построено, но не проверено, что у каждого элемента есть ровно один «партнёр» во втором множестве, и что не возникли «лишние» совпадения, когда одному объекту в паре соответствует несколько объектов с другой стороны.

Хорошая привычка — каждый раз явно отмечать:

— пересечения множеств (для включения–исключения); — пары соответствия и проверку «на оба направления» (для биекции); — все элементы, которые относятся к задаче «справа», чтобы не забыть условия.

Такая дисциплина мышления обычно быстрее, чем попытка «угадать» ответ по интуиции, и почти всегда помогает избежать неверного решения.

19. Мини-практика с проверкой результата

Мини-практика полезна тем, что показывает: в задачах на множества проверка результата — это часть математики.

Рассмотрим ситуацию с двумя кружками — например, кружок А и кружок B. Пусть где-то в условии говорится, сколько учеников записалось в каждый кружок отдельно, и нужно понять общее число участников. Тогда естественное первое движение — сложить два числа: «сколько в А» плюс «сколько в B».

Но это движение почти всегда даёт завышение, потому что участники, которые состоят одновременно в обоих кружках, попадают в сумму дважды.

Поэтому в конце обязательно вычитается количество тех, кто находится в пересечении. Тогда ответ перестаёт «раздуваться» и становится верным.

Тот же принцип формально выражается так: учеников удобно проверять через пересечение двух множеств. Проверка пересечения — это способ убедиться, что в объединении нет двойного счёта и итог действительно соответствует условию задачи.

20. Точный счёт и точное соответствие

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

Формула включения–исключения помогает считать объединения так, чтобы убрать двойной счёт и учесть пересечения. Биекция же учит сравнивать множества через равное количество пар: если построено взаимно однозначное соответствие, равенство количеств доказано.

Вместе они формируют важный навык: аккуратно рассуждать, внимательно проверять условия и доверять только тому выводу, который действительно подтверждён. Это тот самый путь, где математика работает надёжно — от первого шага до окончательного ответа.

Источники

Кантор Г. Теория множеств: основы и приложения. Пер. с нем.; научн. коммент. — М.: Либроком, (издание по выбору).

Харди Г. Х., Райт Э. М. Введение в теорию чисел. — М.: Мир, (издание по выбору).

Андреев А. А. Элементы комбинаторики и теории множеств. — М.: Просвещение, (издание по выбору).

Учебное пособие по теме «Включение–исключение. Взаимно однозначное соответствие» для 8 класса: школьный курс алгебры/математики (издание по выбору).

Д. Розен. Дискретная математика и её приложения. Пер. с англ. — М.: Бином, 2014.

Р. Л. Грэм, Д. Э. Кнут, О. Паташник. Конкретная математика. Основания информатики. — М.: Мир, 2000.

Р. Тейлман. Введение в комбинаторику. Учебное пособие. — СПб.: Лань, 2012.

Н. В. Угринович, Е. А. Угринович. Дискретная математика. Учебник для вузов и колледжей. — М.: Академия, 2019.