Теорема
1. Пусть А
и В – конечные непересекающиеся множества (т. е.
), тогда
. (1)
Теорема
2 (следствие предыдущей) Пусть А, В – конечные множества, тогда
(2)
Теорема
3 (правило включения-исключения)
Пусть
– конечные множества,
тогда
(3)
В правой части формулы (3), называемой формулой
включения-исключения, стоят с чередующимися знаками скобки, содержащие
всевозможные попарные пересечения множеств
, пересечения троек множеств и т. д.
Теорема
4 (правило суммы) Если
– конечное попарно
непересекающиеся множества (т. е.
), то
(4)
Ясно, что это тривиальное следствие из предыдущей
теоремы.
Определение
1. Декартовым произведением
множеств
и
называется множество,
обозначаемое
, элементами которого являются упорядоченные пары
, где
,
. Равенство упорядоченных пар понимается в следующем
смысле:
пусть
и
,
,
.
Теорема 5. Если
и
– конечные
множества, то
– конечное множество и
(5)
Определение
2. Пусть
– множество и
. Определим декартовы степени множества
следующим:
;
;
…
.
Теорема
6. Если
– конечное множество,
то
(6)
Ясно, что теорема 6 – следствие теоремы 5.
Задача
1. Из города А
в город В ведет три дороги, а из города В в город С –
4 дороги. Сколькими способами можно
добраться из А в С через В?
Под способом попасть
из А в С через В понимать упорядоченную пару (дорога,
по которой перемещаемся из А в В; дорога, по которой
перемещаемся из В в С), то решение задачи можно
получить, используя понятие декартова произведения. Обозначим:
АВ – множество дорог, ведущих из А
в В;
ВС – множество дорог, ведущих из В
в С.
Тогда математическая задача, к которой свелась
исходная задача, выглядит так: «Найти число элементов в декартовом произведении
АВ
ВС».
Ясно, что
│ АВ
ВС│=│АВ│•│ ВС│=3•4=12.
Ответ: 12 способов. ![]()
Задача
2. Из города А в город В ведет
три дороги, а из города В в город С – 4 дороги;
имеется также 5 дорог из А в С, не проходящих через В. Сколькими способами можно добраться из А в С, используя
указанные дороги?
Множество всех способов добраться из А в С разобьем на
непересекающиеся подмножества I и II, отнеся к первому способы добраться из А в С через В,
а ко второму – способы добраться из А в С, минуя В. Тогда по правилу суммы
«число способов попасть из А в С»=│ I│+│ II│= │АВ
ВС│+│II│=
3•4+5=17.
Ответ: 17 способов.
![]()