Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 22 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

22
|А
∪В| = |A| + |B| –|А ∩ В|
(рис. 18).
A
B
Рис. 18
2. Мощность объединения трех множеств:
|А
∪ В ∪ С| = |A| + |B| + |C| –
|А
∩ В| – |А ∩ С| – |В ∩ С| +
|А
∩ В ∩ С| (рис. 18a).
Доказательство:
|А
∪ В ∪ С| = |А ∪ (В ∪ С)| =
= |А| + |В
∪ С)| –|А ∩ (В ∪
С)| =
= |A| + |B| + |C| – |В
∩ С| –
– |(А
∩ В) ∪ (А ∩ С)| =
Рис. 18а = |A| + |B| + |C| – |В ∩ С| – |А ∩ В| –
– |А
∩ С| + |А ∩ В ∩ С|.
3. Мощность объединения n множеств:
Теорема. А
1,
А
2,
....... А
n
– некоторые множества, тогда мощность объ-
единения n множеств определяется по формуле
|

А
1
∪ А
2
∪ .... ∪ A
n
| = |A
1
| + |A
2
| +.......+ |A
n
|–
– [ |

А
1
∩ А
2
| + |

А
1
∩ А
3
| + ...... + |A
n–1
 ∩
A
n
| ] +
+[|


А
1
∩ А
2
∩ А
3
| + |


А
1
∩ А
2
∩ А
4
|
+ ....+
+ |A
n–2
 ∩А
n–1
∩
А
n
|] –
–.......+ (–1)
n-1
|

А
1
∩ А
2
∩....A
n
| .
Правая часть этой формулы является суммой n слагаемых,
k-е по порядку слагаемое имеет вид (–1)
k-1
S
k
(A
1
, ....., A
n
), где S
k
(A
1
, A
2
, .....,
A
B
C
1 
                                                         A               B

 |     А ∪В| = |A| + |B| –|А ∩ В|
(рис. 18).



                                                              Рис. 18




      2. Мощность объединения трех множеств:
                                     |А ∪ В ∪ С| = |A| + |B| + |C| –
      A           B    1      |А ∩ В| – |А ∩ С         | – |В ∩    С| +
                              |        А ∩ В ∩ С| (рис. 18a).
                                                Доказательство:
                                     |А ∪ В ∪ С| = |А ∪ (В ∪ С)| =
              C                  =|         А| + |В ∪           С)| –|А ∩ (В ∪
                              С)| =
                                 = |A| + |B| + |C| – |В ∩ С| –
  – |(А ∩ В) ∪ (А ∩ С)     |=
           Рис. 18а      = |A| + |B| + |C| – |В ∩ С| – |А ∩ В| –
                              – |А ∩      С| + |          А ∩ В ∩ С|.

      3. Мощность объединения n множеств:
      Теорема. А1, А2, ....... Аn – некоторые множества, тогда мощность объ-
единения n множеств определяется по формуле
|        А1 ∪ А2 ∪ .... ∪ An| = |A1| + |A2| +.......+ |An|–
                   –[|          А1 ∩ А2 | + |        А1 ∩ А3 | + ...... + |An–1 ∩
           An| ] +
                   +[|                А1 ∩ А2 ∩ А3 | + |             А1 ∩ А2 ∩ А4 |
           + ....+
                   + |An–2      ∩А n–1 ∩  А n|] –
                   –.......+ (–1)n-1 |        А1 ∩ А2 ∩.... An| .
      Правая часть этой формулы является суммой n слагаемых,
k-е по порядку слагаемое имеет вид (–1)k-1 Sk (A1, ....., An), где Sk(A1, A2, .....,


                                       22

Страницы