"Алгебра", Мерзляк А.Г., Поляков В.М. / Под ред. Подольского В.Е.
Формула включения-исключения помогает посчитать элементы, которые принадлежат хотя бы одному из нескольких множеств, не считая общие элементы повторно. Для двух множеств достаточно вычесть их пересечение, а для трёх нужно также прибавить общее пересечение. Другой инструмент — взаимно однозначное соответствие: оно показывает, что конечные множества имеют одинаковое число элементов, даже если пересчитать их напрямую трудно.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Конечное множество — множество, в котором можно сосчитать все элементы и получить определённое число. Это число называют мощностью множества A и обозначают |A|. Например, если A = {2, 4, 6}, то |A| = 3. Мощность нужна, чтобы точно сравнивать множества и применять формулы подсчёта.
Объединение множеств A и B — множество элементов, которые принадлежат хотя бы одному из них; его обозначают A ∪ B. Формула включения-исключения для двух множеств записывается так: |A ∪ B| = |A| + |B| − |A ∩ B|. Здесь пересечение A ∩ B содержит общие элементы, а его мощность вычитают, чтобы не посчитать их дважды.
Для трёх множеств формула имеет вид: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Сначала складывают мощности отдельных множеств, затем вычитают попарные пересечения. Общее пересечение трёх множеств прибавляют, чтобы исправить повторный вычет.
Взаимно однозначное соответствие — правило, при котором каждому элементу одного множества сопоставлен ровно один элемент другого, причём каждый элемент второго множества сопоставлен ровно один раз. Такое соответствие можно представить как пары элементов без пропусков и повторов. Для конечных множеств оно показывает, что их мощности равны, даже если сами множества состоят из разных объектов.
При подсчёте объединения двух множеств складывают число элементов в каждом из них. Но элемент, принадлежащий обоим множествам, оказывается в первой части суммы и во второй, то есть учитывается дважды. В объединении он должен встретиться один раз, поэтому всю мощность пересечения вычитают один раз.
Для трёх множеств сначала складывают три мощности, и каждый элемент, входящий в несколько множеств, повторяется в сумме. Вычитание попарных пересечений исправляет повторы у элементов, принадлежащих двум множествам, но элемент общего пересечения попадает во все три пары и оказывается вычтен лишний раз. Поэтому мощность общего пересечения прибавляют: итоговый коэффициент для такого элемента становится равен единице.
Перед подстановкой чисел в формулу нужно перевести условие задачи на язык множеств. Каждое множество связывают с одним признаком, например «изучают английский», а пересечение — с одновременным выполнением двух признаков. Затем проверяют, что данные о пересечениях относятся именно к указанным множествам и что искомое количество означает объединение, то есть выполнение хотя бы одного условия.
Взаимно однозначное соответствие связывает элементы двух множеств попарно, не оставляя пропусков и повторов. Если такое правило построено, можно сравнить множества по парам: на каждый элемент первого приходится ровно один элемент второго и наоборот. Значит, число элементов в конечных множествах одинаково, хотя прямой пересчёт может быть неудобен.
Чтобы доказать равенство мощностей, достаточно предложить правило сопоставления и проверить его свойства. Удобно показать, что правило не отправляет разные элементы первого множества к одному элементу второго, а также что для каждого элемента второго можно найти соответствующий элемент первого. Например, для чисел n от 1 до заданной границы формула может сразу задавать пару и помогать проверить, что ни один элемент не пропущен.
| Случай | Формула | Как учитываются пересечения |
|---|---|---|
| Два конечных множества A и B | |A ∪ B| = |A| + |B| − |A ∩ B| | Пересечение вычитают один раз, чтобы общие элементы не считались дважды. |
| Три конечных множества A, B и C | |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| | Попарные пересечения вычитают, общее пересечение прибавляют. |
| Равенство мощностей через взаимно однозначное соответствие | |A| = |B| | Каждому элементу A соответствует ровно один элемент B, и все элементы B используются. |
Сначала выберите строку по числу множеств или по тому, что требуется доказать. Затем подставьте данные из условия, внимательно сопоставив каждое число с нужным множеством или пересечением. Если используется соответствие, вместо вычислений проверьте, что правило охватывает оба множества без повторов.
Задача 1. В классе 18 учеников изучают английский язык, 12 — немецкий, а 5 изучают оба языка. Сколько учеников изучают хотя бы один из этих языков? «Хотя бы один» означает объединение двух множеств. Общих учеников нельзя считать дважды.
Ответ: 25 учеников изучают хотя бы один язык.
Задача 2. В группе 20 человек знают французский, 17 — испанский, 14 — итальянский; французский и испанский знают 6, французский и итальянский — 5, испанский и итальянский — 4, все три языка — 2 человека. Сколько человек знают хотя бы один язык? Обозначим соответствующие множества буквами A, B и C. Искомое число — мощность их объединения.
Ответ: 38 человек знают хотя бы один из трёх языков.
Задача 3. Докажите, что множество целых чисел от 1 до n и множество нечётных чисел от 1 до 2n имеют одинаковую мощность. Прямое сопоставление удобно задать одной формулой. Проверим, что она создаёт пары без пропусков и повторов.
Ответ: соответствие взаимно однозначное, поэтому мощности множеств равны.
Сложить мощности двух множеств без вычитания пересечения. Так делают, если забывают, что общие элементы уже попали в обе части суммы. Проверьте, не посчитали ли вы кого-то дважды; если пересечение непустое, его мощность нужно вычесть.
Не прибавить общее пересечение в формуле для трёх множеств. При вычитании всех попарных пересечений элементы, входящие во все три множества, вычитаются три раза. Их нужно прибавить, иначе итоговое число будет меньше правильного; полезно отдельно проследить подсчёт одного такого элемента.
Перепутать пересечение и объединение. Пересечение — только общие элементы, а объединение — элементы хотя бы одного множества. Ошибка возникает, когда слова «и» и «или» не соотносят с условием задачи; проверьте, требуется ли выполнение всех признаков или хотя бы одного.
Проверить только, что разным элементам первого множества соответствуют разные элементы второго. Это исключает совпадения, но не гарантирует, что во втором множестве не осталось элементов без пары. Чтобы соответствие было взаимно однозначным, докажите также, что каждый элемент второго множества получен ровно один раз.
Для работы с формулами нужно знать, что такое конечное множество, объединение и пересечение, и уметь считать элементы. Эти понятия помогают перевести условие задачи в точную запись. Если смысл множеств и их общих элементов определён неверно, даже правильная формула даст неправильный ответ.
Формула включения-исключения применяется в задачах, где объекты могут удовлетворять нескольким условиям одновременно. Она помогает найти число объектов, подходящих хотя бы под одно условие, например языки, предметы или признаки. Сложность обычно состоит в том, чтобы правильно определить пересечения.
Взаимно однозначное соответствие позволяет сравнивать мощности множеств и становится полезным в комбинаторном подсчёте. Вместо непосредственного перечисления элементов можно найти правило, которое связывает их попарно. Это особенно удобно, когда множества заданы по-разному, но между их элементами легко установить пары.
Почему при объединении двух множеств нужно вычитать пересечение?
При сложении мощностей множеств каждый элемент пересечения попадает в сумму дважды. В объединении его нужно учесть один раз, поэтому мощность пересечения вычитают.
Почему в формуле для трёх множеств общее пересечение прибавляют?
Элементы общего пересечения сначала посчитаны трижды, а затем трижды вычтены как элементы попарных пересечений. Чтобы в итоге учесть каждый такой элемент один раз, общее пересечение прибавляют.
Чем объединение множеств отличается от их пересечения?
Объединение содержит элементы, которые принадлежат хотя бы одному из множеств. Пересечение содержит только элементы, общие для всех рассматриваемых множеств.
Как проверить, что соответствие является взаимно однозначным?
Проверьте, что каждому элементу первого множества поставлен в соответствие ровно один элемент второго и разные элементы первого не ведут к одному и тому же элементу второго. Затем убедитесь, что каждый элемент второго множества получен.
Как с помощью взаимно однозначного соответствия доказать, что множества имеют одинаковую мощность?
Задайте правило, которое сопоставляет элементам первого множества элементы второго. Докажите, что правило работает в обе стороны: каждый элемент первого имеет ровно одну пару, и каждый элемент второго соответствует ровно одному элементу первого.
§ 3. Формула включения-исключения. Взаимно однозначное соответствие
