Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 49 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

1.2.4 Ме тод вклю че ния и ис клю че ния
1) На хо ж де ние чис ла эле мен тов сум мы мно жеств A и B.
Обо зна чим N(A) — ко ли че ст во эле мен тов мно же ст ва A. N(B) —
ко ли че ст во эле мен тов мно же ст ва B, то гда оче вид но:
N A B N A N B N A B( ) ( ) ( ) ( )È = + - Ç
,
так как об щие эле мен ты
( )A BÇ
бу дут пе ре чис ле ны два ж ды.
Для чис ла эле мен тов сум мы трех мно жеств:
{ }
{ }
N A B C N A B C N A N B C
N A B A C N A N
( ) ( ) ( ) ( )
( ) ( ) ( )
È È = È È = + È -
- Ç È Ç = +
[ ]
{ }
( ) ( ) ( )
( ) ( ) ( ) (
( )
B N C N B C
N A B N A C N A B A C
N A N
+ - Ç -
- Ç + Ç - Ç Ç Ç =
= + ( ) ( ) ( ) ( )
( ) ( ).
B N C N A B N A C
N B C N A B C
+ - Ç - Ç -
- Ç + Ç Ç
При мер. Ка ж дый сту дент груп пы — ли бо де вуш ка (А), ли бо блон -
дин (В), ли бо лю бит ма те ма ти ку (С). Пусть в груп пе — 20 де ву шек(А),
из них 12 блон ди нок и од на лю бит ма те ма ти ку. Все го в груп пе 24 блон ди -
на (В), ма те ма ти ку из них лю бят 12, а все го сту ден тов (де ву шек и юно -
шей), ко то рые лю бят ма те ма ти ку (С) — 17, из них 6 де ву шек. Сколь ко
сту ден тов в дан ной груп пе?
Ре ше ние: А — мно же ст во де ву шек, В — блон ди нов, С — лю бят ма -
те ма ти ку. То гда на до най ти
N A B C( )È È
.
A BÇ
— мно же ст во блон ди нок;
A CÇ
— мно же ст во де ву шек, ко -
то рые лю бят ма те ма ти ку;
B CÇ
— мно же ст во всех блон ди нов, ко то рые лю бят ма те ма ти ку;
A B CÇ Ç
— мно же ст во блон ди нок, ко то рые лю бят ма те ма ти ку,
то гда:
N A B C( )È È
= 20 + 24 + 17 – (12 + 6 + 12) + 1 = 32.
Об щая фор му ла:
N A A N A N A
N A A N A A N A
n n
n
( ) ( ) ( )
( ) ( ) (
1 1
1
2
1
3
È È = + + -
- Ç + Ç + +
K K
K
{ }
{ }
-
Ç +
+ Ç Ç + Ç Ç + + Ç Ç -
1
1
2 3
1
2 4 2
1
A
N A A A N A A A N A A A
n
n
n
n
)
( ) ( ) ( )
—
—
K K
K K+ - Ç Ç
-
( ) ( ),1
1
1
n
n
N A A
49
      1.2.4 Метод включения и исключения

     1) Нахождение числа элементов суммы множеств A и B.
     Обозначим N(A) — количество элементов множества A. N(B) —
количество элементов множества B, тогда очевидно:
                     N ( A È B) = N ( A) + N (B) - N ( A Ç B),
так как общие элементы ( A Ç B) будут перечислены дважды.
      Для числа элементов суммы трех множеств:
  N ( A È B È C ) = N { A È (B È C )} = N ( A) + N (B È C ) -
                 - N {( A Ç B) È ( A Ç C )} = N ( A) + N (B) + N (C ) - N (B Ç C ) -
                 -{N ( A Ç B) + N ( A Ç C ) - N [( A Ç B) Ç ( A Ç C ]} =
                 = N ( A) + N (B) + N (C ) - N ( A Ç B) - N ( A Ç C ) -
                 - N (B Ç C ) + N ( A Ç B Ç C ).

       Пример. Каждый студент группы — либо девушка (А), либо блон-
дин (В), либо любит математику (С). Пусть в группе — 20 девушек(А),
из них 12 блондинок и одна любит математику. Всего в группе 24 блонди-
на (В), математику из них любят 12, а всего студентов (девушек и юно-
шей), которые любят математику (С) — 17, из них 6 девушек. Сколько
студентов в данной группе?
       Решение: А — множество девушек, В — блондинов, С — любят ма-
тематику. Тогда надо найти N ( A È B È C ).
       A Ç B — множество блондинок; A Ç C — множество девушек, ко-
торые любят математику;
       B Ç C — множество всех блондинов, которые любят математику;
       A Ç B Ç C — множество блондинок, которые любят математику,
тогда:
       N ( A È B È C ) = 20 + 24 + 17 – (12 + 6 + 12) + 1 = 32.
       Общая формула:
  N ( A1 È K È An ) = N ( A1 ) + K + N ( An ) -
  - {N ( A1 Ç A2 ) + N ( A1 Ç A3 ) + K + N ( An -1 Ç An )} +
  +{N ( A1 Ç A2 Ç A3 ) + N ( A1 Ç A2 Ç A4 ) + K + N ( An — 2 Ç An —1 Ç An )} - K
  K + (-1) n -1 N ( A1 Ç K Ç An ),

                                                                                   49

Страницы