пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Метод включений и исключений.

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

Пусть дано n- множество image321.gifнекоторых элементов и к-множество свойств image323.gif, которыми элементы image321.gifмогут как обладать, так и не обладать. выделим какую-либо r-выборку свойств image325.gif. Число элементов image327.gifобладающих всеми r выбранными свойствами, обозначим через image329.gif. Отсутствие у элемента какого-либо свойства image331.gifбудем обозначать image333.gif.

Найдем число элементов, не обладающих набором определенных свойств, начав с простых случаев:

1. Пусть имеется одно свойство image335.gif, тогда image337.gif.

2. Имеется конечное число свойств image323.gif, несовместимых друг с другом. Тогда image339.gif.

3. Элементы обладают комбинациями различных свойств. Тогда справедлива теорема.

Теорема3. Если даны n- множество элементов и к-множество свойств image331.gif, image341.gif, совместимых между собой, тогда

image343.gif

image345.gif (20)

В левой части формулы может стоять не только image347.gif, но и, например, image349.gif. Теорема формулируется при этом относительно совокупности свойств image351.gifи image353.gifс обязательным выполнением свойств image355.gifи image357.gifследующим образом:

image359.gif (21)

Пример. В комнате несколько человек, знающих хотя бы один из трех языков. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один человек знает все три языка. Сколько человек в комнате. сколько из них знают только английский язык.

Решение. Пусть свойство image361.gif- знать английский язык; image363.gifи image365.gif- свойства, характеризующие знание немецкого и французского языков. По условию задачи общее число людей составляют все, знающие хотя бы один язык; не знающих хотя один язык в задаче нет. Тогда

image367.gif

+7-(4+3+2)+1=19-9+1=11.

Число людей, знающих только английский язык, это image369.gif, по формуле (21) имеем

image369.gif=image371.gif.


15.01.2017; 01:29
хиты: 94
рейтинг:0
Точные науки
математика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь