Формулы включений и исключений

Пусть известно число объектов, лежащих в множестве А ив множестве В. Если множества А и В не пересекаются, то, сложив эти числа, получим число объектов, лежащих в объединении множеств А и В.

Предположим теперь, что существуют объекты, лежащие одновременно в двух множествах. Нетрудно понять, что, сложив числа А и |/?|, объекты, лежащие и в А, и в В, будут сосчитаны дважды. Поэтому, чтобы получить правильный ответ (в котором каждый объект должен быть учтен один раз), нужно исключить из найденной суммы объекты, лежащие одновременно ив А, и в В.

Таким образом, для двух множеств А и В имеет место формула:

Эту формулу можно получить из правила сложения. Действительно, множество AjB может быть разбито на классы АВ, АВ, А В, множество А — на классы АВ и АВ, множество В — на классы А В и АВ (знак пересечения опускаем). Поэтому правую часть равенства можно расписать следующим образом:

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

Пример 9.4.1. Определим, сколько существует двузначных чисел, в записи которых имеется хотя бы одна четная цифра.

Первый способ. Пусть А — множество двузначных чисел, у которых первая цифра четна, В — множество двузначных чисел, у которых вторая цифра четна. Имеем |Л| =4−10 = 40, так как первую цифру можно выбрать четырьмя способами (из множества {2,4,6,8}), а вторую цифру — любым из 10 способов (всего 10 цифр, учитывая цифру 0). Аналогично |/?| = 9−5=45, гак как первая цифра может быть любой, кроме 0, а вторая цифра — любая четная.

Однако правило сложения применить нельзя, поскольку есть числа, входящие и в множество А, и в множество В, — это числа, обе цифры которых четные. Таких чисел АгВ = 4−5 = 20.

По формуле (1) получаем: AjB = 40 + 45 — 20 = 65.

Второй способ. Разобьем множество всех требуемых чисел на три класса. Первый класс — это числа, первая цифра которых четна, а вторая нечетна. Таких чисел 4−5 = 20. Второй класс — числа, первая цифра которых нечетна, а вторая цифра четна. Таких чисел 5−5 = 25. Третий класс — числа, цифры которых четны. Этих чисел 4−5 = 20. Тогда общее количество чисел равно 20+25+20 = 65.

Заметим, что можно было разбить множество таких чисел на два класса: множество чисел, первая цифра которых четная, а вторая — любая (их 4−10 = 40), и множество чисел, первая цифра которых нечетная, а вторая четная (их 5−5 = 25). В сумме снова получаем 65.

Третий способ. Всего двузначных чисел 9−10 = 90. Из них чисел, обе цифры в которых нечетные, 5−5 = 25. Тогда двузначных чисел, в которых имеется хотя бы одна четная цифра, равно 90−25 = 65. •.

Для трех множеств имеет место следующая формула:

Для обоснования можно использовать один из двух способов. Можно представить объединение трех множеств в виде (AkjB)kjC и применить формулу (1). Можно рассмотреть множества, на которые разбиваются множества, присутствующие в формуле (2), и применить принцип сложения.

Пример 9.4.2. Студент пришел в библиотеку в поисках книги, которая содержит одновременно материал по химии, по физике и по математике. Библиотекарь заявила, что существует всего 30 книг, имеющих хотя бы одно из перечисленных свойств, причем книг с материалом по химии всего 23 штуки, книг по физике 21 штука и книг по математике 17. Можно ли наверняка утверждать, что нужная студенту книга имеется в библиотеке?

Рассмотрим три множества: А — множество книг, содержащих материал по химии, В — множество книг с материалом по физике, С — множество книг с материалом по математике. По условию |/!|=23, |#|=21, |С|=17, |Ли/?иС|=30.

Допустим, что нужная студенту книга отсутствует. Ото означает, что Ип#пС|=0.

Снова для краткости будем опускать знак пересечения и писать АВ вместо АгВ. По формуле (2) имеем:

Отсюда АВ + АС + ВС = 31 (*).

Множества АВ и АС не пересекаются, так как пересечение (ЛпЯ)п (ЛпО пусто. Значит, по правилу сложения число элементов объединения множеств АВ и АС равно сумме АВ + АС. Но АВиАС — это множество книг, содержащих материал по химии и, вместе с этим, материал по физике или математике, то есть ABjAC — это подмножество множества А. Поэтому число элементов этого множества не превосходит число элементов, лежащих в А. Итак, АВ + АС < 23.

Рассуждая аналогично, получаем, что АВ + ВС <21 и АС + ВС < 17. Складывая почленно три неравенства, имеем:

откуда получаем, что сумма АВ + АС + ВС не превосходит 30,5. А это противоречит равенству (*).

Следовательно, если библиотекарь сказала правду, то нужная студенту книга существует. •.