Задание 8 класс
1. Записать в тетрадь тему урока.
2. Ознакомиться с теоретическим материалом.
3. Записать в тетрадь формулу включения – исключения
4. Рассмотреть решение задачи с помощью формулы включения – исключения.
5. Выполнить в тетради задачу для самостоятельного решения.
Множества. Круги Эйлера
Множество - это набор объектов, объединенных каким-то признаком. Например, множество квадратных объектов, множество предметов, изучаемых в 9 классе и пр.
Рассмотрим множество объектов оранжевого цвета. В него входят рыжий кот, спасательный жилет, апельсин, осенний кленовый лист, и много других объектов оранжевого цвета. На рисунке изобразим круг и будем предполагать, что все оранжевые предметы находятся внутри него:
Множество оранжевых объектов
Теперь возьмем множество животных кошачьего семейства. Здесь будут домашние кошки, тигры, львы, гепарды и остальные представители данного семейства.
Множество представителей семейства кошачьих
Пересечение множеств
Заметим, что рыжий кот входит в оба множества. Поэтому, если мы изобразим эти множества рядом, должны будем расположить их следующим образом:
Множества будут располагаться "внахлест", так как есть объекты, которые одновременно входят в оба множества (рыжий кот).
Область, в которой сидит рыжий кот, называется пересечением множеств.
Множества принято обозначать заглавными латинскими буквами: A, B, C, ...
Пересечение обозначают символом &: A & B, читается как "пересечение множеств A и B".
В общем случае произвольные два множества располагаются именно так: есть элементы, входящие в оба множества (то есть пересечение множеств непустое), а есть элементы, которые не входят только в одно из множеств.
Объединение
В гости к Пете едет его любимая бабушка. Она поинтересовалась у внука, что можно купить ему в подарок. Он сказал, что любит книжки и машины. В магазине бабушка увидела разные игрушки, и в блокноте изобразила круги Эйлера - один с множеством машин, второй - с множеством книжек. В пересечение этих кругов попала книга о машинах. Вне кругов расположились шарик, вертолет, матрешка и медвежонок - они не входят в множество предполагаемых подарков для Пети:
Область, похожая на перевернутую восьмерку, иллюстрирует множество машинок и книжек - подходящих подарков. Такое множество называется объединением. В него входят все элементы изначальных множеств, причем те, которые находятся на пересечении, входят только один раз:
Мощность множеств
Мощность множества - это количество элементов в нем. Обозначается так: |A|. Мощность множества может быть равна нулю (пустое множество), конечному числу (мощность множества десятичных цифр равна 10) или равна бесконечности (мощность множества натуральных чисел).
Формула включения/исключения для двух областей
Вернемся к примеру с бабушкой и Петей. Пусть бабушка хочет посчитать, сколько вариантов выбрать один подарок у нее есть. Она знает мощность множества А - подарков на "машинную" тематику, мощность множества книг В и мощность их пересечения A&B.
То, что хочет найти бабушка, называется мощностью объединения множеств A | B. Логично предположить, что для его поиска нужно сложить мощности множеств A и B: 4 "машинковых" подарка + 3 книги = 7 подарков. Но на картинке видно, что всего подарков 6! Дело в том, что при суммировании мощностей множеств A и B элемент, находящийся на их пересечении, мы посчитали два раза. Тогда его нужно один раз отнять. Итого формула нахождения мощности множества объединения двух множеств такова:
|A | B| = |A| + |B| - |A & B|
Ее называют формулой включения - исключения.
Задание. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:
Сколько страниц будет найдено по запросу шахматы?
Решение: обозначим множество страниц, которое находится по запросу шахматы как Ш, а по запросу теннис как Т. Тогда формула включения-исключения примет вид:
|Ш | Т| = |Ш| + |Т| - |Ш & Т|
Подставим в нее известные величины:
7770 = |Ш| + 5500 - 1000
И выразим неизвестную:
|Ш| = 7770 - 5500 + 1000 = 3270
Ответ: 3270.
Задача для самостоятельного решения:
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» - символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Какое количество страниц (в тысячах) будет найдено по запросу Пушкин & Лермонтов? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
