Элементы дискретной математики - 8 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

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

Рубрика: 

8
Решая эту задачу аналогично предыдущей, получим: 47+35+20-23-12-11+5=61.
Используя обозначения, предложенные выше, получаем следующую формулу для
трех свойств:
N(а1или а2 или а3)= N(а1)+N(а2)+N(а3)-N(а1и а2) -N(а1и а3) -N(а2и а3) +N(а1и а2 и а3)
Общий вид формулы включения и исключения
Пусть имеется n предметов, некоторые из которых обладают свойствами а
1
, а
2
, …,
а
n
. Каждый предмет может либо не обладать ни одним из этих свойств, либо обладать одним
или несколькими свойствами одновременно.
Обозначим N(а
i
или a
j
или … или a
k
) количество предметов, обладающих хотя бы
одним из свойств а
i
, a
j
, … a
k
.
Для того чтобы определить количество предметов, обладающих хотя бы одним из
свойств a
1
, a
2
…a
n
, используют формулу:
N(a
1
или а
2
или … или а
n
)=N(a
1
)+N(a
2
)+…+N(a
n
)-N(a
1
и a
2
)-N(a
1
и a
3
)-…-N(a
1
и a
n
)-
…-N(a
n-1
и a
n
)+N(a
1
и a
2
и a
3
)+…N(a
n-2
и a
n-1
и a
n
)+…+(-1)
n-1
N(a
1
и a
2
и … и a
n
).
Доказательство.
Доказательство проведем методом математической индукции по числу свойств.
При одном свойстве формула очевидна. Каждый предмет либо обладает этим
свойством, либо не обладает им. N(a)=N(a)
Предположим, что формула доказана для случая когда число свойств меньше или
равно n-1. Тогда:
N(a
1
или а
2
или … или а
n-1
, или а
n
)= N((a
1
или а
2
или … или а
n-1
) или а
n
) =
=N(a
1
или а
2
или … или а
n-1
)+N(а
n
) – N ((a
1
или а
2
или … или а
n-1
) и а
n
) =
=[N(a
1
)+N(a
2
)+…+N(a
n-1
)-N(a
1
и a
2
) – N (a
1
и a
3
) – … – N (a
1
и a
n-1
) – …– N (a
n-2
и a
n-1
)+
+N(a
1
и a
2
и a
3
)+…+N(a
n-3
и a
n-2
и a
n-1
)+…+ +(-1)
n-2
N(a
1
и a
2
и … и a
n-1
)] +N(а
n
) –
– N((a
1
и а
n
)или (а
2
и а
n
)или … или (а
n-1
и а
n
))=
=[N(a
1
)+N(a
2
)+…+N(a
n-1
)-N(a
1
и a
2
) – N(a
1
и a
3
) – …– N (a
1
и a
n-1
) – …– N (a
n-2
и a
n-1
)+
+N(a
1
и a
2
и a
3
)+…+ +N(a
n-3
и a
n-2
и a
n-1
)+…+ +(-1)
n-2
N(a
1
и a
2
и … и a
n-1
)] +N(а
n
) –
– [N(a
1
и а
n
)+N (а
2
и а
n
)+ … +N(а
n-1
и а
n
) – N (a
1
и а
2
и a
n
) – … N(a
n-2
и а
n-1
и а
n
)+…+
+(-1)
n-2
N(a
1
и a
2
и … и а
n
)]=
=N(a
1
)+N(a
2
)+…+N(a
n
) – N (a
1
и a
2
) – N (a
1
и a
3
) – …– N (a
1
и a
n
) –…– N (a
n-1
и a
n
)+
+N(a
1
и a
2
и a
3
)+…+N(a
n-2
и a
n-1
и a
n
)+…+ (-1)
n-1
N(a
1
и a
2
и … и a
n
)
Что и требовалось доказать.
Задача.

Страницы