Дискретная математика

ПОЛУЧИМ: 104 Рассмотрим теперь случай, когда АпВ ^ 0. Докажем, что в этом случае п(АиВ) ~ п(А)-г п(В) - п(АпВ). (4.2) Очевидно, имеем: А=(АпВ)и(АпВ) и (АпВ)п (Аг\В)= 0; В=(ЛпВ)и(Аг\В)\1(Аг^)п(Аг\В)= 0. { ® Тогда, используя правило суммы, получим следующее: п(А) = п(А Г\В)+п(Агл В): п(В) =п(Аг\В) + п(Агл В); п(А) + п(В) = п(А пВ) + п(АпВ) + п(А глВ)+ п(А п В) п(АиВ) следовательно, п(АиВ)^п(А)+п(В)-п(АпВ), что и требовалось доказать, Для трех множеств можно получить: n (AuBLJZ )=n (A )+n (B )+n (C )-n (AnB )-n (AnC )-n (BnC )+n (AhBnC). В общем случае по индукции можно получить следующую формулу (правило); n(AiuA2U...uAi)=n(Ai)+n(A2)+••.+n(A|^- -n(AlnA2)-n(AlnAi)-...-n(A^.,nA^+ (4.3) +n(AinA2nAs) +... + n(Aii.2nAk.inAiJ + . +(-])'^''n(AiriA2D...rtAiJ. которое называется обобщенным правилом суммы. § 2. Правило произведения для конечных множеств Рассмотрим пример. Из Казани в Самару можно добраться (летом) пароходом, поездом и самолетом, т.е. тремя способами. Из Самары до Тольятти можно доехать на автобусе или такси. Сколькими способами можно добраться из Казани до Тольятти, используя указанные возможности? Очевидно, что 3x2=6 способами. Пусть даны произвольные конечные множества А и В. Выясним сколько элементов содержит их декартово произведение АхВ. Напомним, что декартовым произведением непустых множеств А и В называется множество упорядоченных пар: АхВ={(х,у): (х £ Л)&(уеВ)}. Для к множеств Ai,A2,...,Ak их декартово произведение определяется как множество упорядоченных к элементов: AixA2x...xAk={(X),X2,...,Xt): (x, €Ai)&(X2eAi)A ...&(Xk£A0}.