Теорема (о мощности объединения n множеств)

Пусть имеется n множеств А₁, А₂, … А_n, вычислить мощность их объединения

|А₁ А₂ … А_n|=|А₁|+|А₂|+…+|А_n|-

-|А₁ А₂|-|А₁ А₃|-|А₂ А₃|-…-|А_n-1 А_n|+

+|А₁ А₂ А₃|+|А₁ А₃ А₄|+…+|А_n-2 А_n-1 А_n|-…+

(-1)^n-1|А₁ А₂ … А_n| (*)

Доказательство:

Для доказательства будем использовать предыдущее утверждение и метод математической индукции.

1. База индукции выполняется по утверждению, n=2

2. Предположим, что формула (*) выполняется для всех k=n-1. Введем следующие обозначения S₁(А₁, А₂, …, А_n), S₂(А₁, А₂, …, А_n), .., S_n(А₁, А₂, …, А_n)

(*)=S₁(А₁, А₂, …, А_n)- S₂(А₁, А₂, …, А_n)+ +(-1)^n-1 S_n(А₁, А₂, …, А_n)

Имеет место формула

|А₁ А₂ … А_n-1|= S₁(А₁, А₂, …, А_n-1)- S₂(А₁, А₂, …, А_n-1)+…+

+(-1)^n-1 S_n-1(А₁, А₂, …, А_n-1) (**)

3. Произведем индукционный переход, т.е. покажем, что формула выполняется для всех k=n, для этого рассмотрим мощность объединения всех n множеств и произведем следующую операцию |А₁ А₂ … А_n|, пользуясь утверждением.

Распишем по утверждению çА₁ Вç=çА₁ç+çВç-çА₁ Вç где В=|А₂ … А_n|

=|А₁|+|А₂ … А_n|-|А₁ А₂| |А₁ А₃| … |А₁ А_n|=|А₁|+ S₁(А₂, …, А_n)-

- S₂(А₂,…,А_n)+…+(-1)^n-2 S_n-1(А₂,…,А_n)- S₁((А₁ А₂),А₁ А₃),…,(А₁ А_n))-

- S₂((А₁ А₂),(А₁ А₃),…,(А₁ А_n))+…+ (-1)^n-2S_n-1((А₁ А₂),(А₁ А₃),…,(А₁ А_n))

Формула (*) выполняется для всех k=n.

Из пунктов 1-3 следует, что по методу математической индукции формула (*) выполняется для всех nÎN\{1}.

Задача: Каждый ученик класса либо девочка, либо блондин, либо любит математику. В классе 20 девочек, из них 12 блондинок и одна блондинка любит математику. Всего в классе 24 ученика блондина, математику из них любят 12. А всего учеников, мальчиков и девочек, которые любят математику – 17, из них 6 девочек. Сколько учеников в классе?

А – девочки

В – блондины

С – любят математику

|А|=20, |В|=24, |С|=17, |А В|=12,|А С|=6, |В С|=12, |А В С|=1

|А В С|=|А|+|В|+|С|-|А В|-|А С|-|В С|+|А В С|=20+24+17-12-6-12+1=32