Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Формула включений-исключений



Из правила сложения с применением других теоретико-множественных операций может быть выведена формула включений-исключений (или принцип (правило) включений-исключений). Это правило позволяет рассчитать количество элементов в объединении конечных множеств, которые в общем случае могут пересекаться друг с другом. При двух множествах A и B (рис. 5.2) правило имеет вид:

N(AÈB) = N(A) + N(B) – N(AÇB),
где N(A), N(B), N(AÈB), N(AÇB) – числа элементов в исходных множествах А и В, их объединении AÈB и пересечении AÇB.

Рис. 5.2. Объединение двух множеств A и B

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

N(AÈB) = N(A\B) + N(B\A) + N(AÇB),
где A\B – результат вычитания множества B из множества A, B\A – результат вычитания множества A из множества B.

В полученной формуле комбинаторным правилом является объединение, а операции вычитания и пересечения играют вспомогательную роль. При этом расчетная схема принимает стандартный для параллельных вычислений вид (рис. 5.3):

Рис.5.3. Расчетная схема правила включений-исключений для двух множеств

В случае количества множеств s > 2 процесс нахождения количества элементов объединения A1 È A2 È … È As заключается в начальном суммировании чисел всех элементов, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Данный процесс дал название формулы.

Пример 1.На выставке представлено 23 картины, в которых использованы только красный и синий цвета. Из них 8 выполнены только в красном цвете, на 11 одновременно использован и красный и синий цвет. Сколько выставлено картин, в которых использован синий цвет?

Решение. Обозначим множество картин, в которых использован красный цвет (только красный и вместе с синим), через A, а множество картин, в которых есть синий цвет, через В. В условии задано общее число картин: N(A È B) = 23, число картин в разности N(A\B) = 8 и число картин в пересечении N(A Ç B) = 11. Подставляя данные значения в формулу для N(A È B), выраженную через разности множеств, получим вначале число картин, в которых использован только синий цвет:

N(B\A) = N(A È B) – N(A\B) – N(A Ç B) = 23811=4.

Искомое общее число картин, в которых использован синий цвет, равно:

N(B) = N(B\A) + N(A Ç B) = 4+11=15.

Ответ: 15.