Принцип включения и исключения. Теорема о числе элементов, не обладающих ни одним из указанных свойств (вес каждого элемента равен единице). Доказательство. — КиберПедия 

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

Принцип включения и исключения. Теорема о числе элементов, не обладающих ни одним из указанных свойств (вес каждого элемента равен единице). Доказательство.

2017-11-27 641
Принцип включения и исключения. Теорема о числе элементов, не обладающих ни одним из указанных свойств (вес каждого элемента равен единице). Доказательство. 0.00 из 5.00 0 оценок
Заказать работу

Пусть дано n -множество элементов S и N- множество свойств p 1,…, pN. Элементы множества S могут как обладать, так и не обладать любым из свойств pi. Количество элементов, обладающих теми или иными свойствами и их комбинациями, известно.

Требуется найти число элементов, не обладающих ни одним из свойств.

Обозначим:

1) через некоторую i -ю выборку свойств, а через – число элементов, каждый из которых обладает всеми этими r выбранными свойствами.

2) через – отсутствие у элемента свойства pi. Тогда, например, – число элементов, обладающих свойствами p 1 и p3 и не обладающих свойствами p2 и p4.

 

Рассмотрим два частных случая.

1. Имеется лишь одно свойство p. Тогда очевидно, что число элементов, не обладающих свойством p, равно общему числу элементов минус число элементов, обладающих свойством p. .

2. Имеется конечное множество свойств p 1,…, pN, но они не совместимы (т.е. ни один из элементов не может обладать более чем одним свойством). Тогда число элементов, не обладающих ни одним из свойств, равно общему числу элементов минус число элементов, обладающих свойством p 1, минус число элементов, обладающих свойством p 2 и т.д.

.

Общий случай – элементы могут обладать комбинацией совместимых свойств.

Теорема. Если даны n -множество элементов S и N свойств pi , то число элементов, не обладающих ни одним из свойств, равно (формула решета):

 

n n (p 1) n (p2)     n (p3)

Рассмотрим доказательство при N =3.

Обозначим кругами подмножества элементов, обладающих хотя бы свойством p 1, хотя бы свойством p 2 и хотя бы свойством p 3. Тогда пересечения двух кругов будут давать подмножество элементов, обладающих хотя бы двумя свойствами одновременно, а пересечение всех трех кругов дает подмножество элементов, обладающих всеми тремя свойствами. Прямоугольник, в котором расположены круги, обозначает все множество S, содержащее n элементов. Нужно найти количество элементов, не обладающие ни одним из трёх свойств (за пределами кругов).

Чтобы найти это число, нужно из n -множества исключить элементы, обладающие свойством p 1, затем обладающие свойством p2, затем – p3, т.е. вычесть . Однако при этом элементы, обладающие двумя свойствами (например, p 1 и p2), окажутся исключёнными дважды (сначала как элементы, обладающие свойством p 1, затем как обладающие p2). Следовательно, нужно возвратить по одному разу элементы, исключённые дважды, т.е. добавить . Но при этом элементы, обладающие сразу тремя свойствами (p 1, p2, p3), сначала были трижды исключены как элементы, обладающие по отдельности свойствами p 1, p2 или p3, а затем трижды включены как обладающие парами свойств. Поэтому их нужно один раз исключить, т.е. вычесть . Рассуждая подобным образом, получаем алгоритм, который состоит в попеременном включении и отбрасывании подмножеств, дающий приведенную выше формулу решета.

 

Следствие. Характер доказательства таков, что его можно применять к любой комбинации свойств. Например,

.


Поделиться с друзьями:

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.007 с.