Как работает формула включений-исключений при решении задач на поиск информации в интернете?

Формула включений-исключений позволяет решать задачи о количестве страниц, найденных по запросу в интернете, где для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&». 13

Формула для двух областей выглядит так: N A | B = N A + N B − N A & B, где N X — количество страниц, которые выдаёт поисковая система по запросу X. 3

Формула для трёх областей имеет вид: N A | B | C = N A + N B + N C − N A & B − N A & C − N B & C + N A & B & C. 3

Пример решения задачи: 4

Есть таблица с запросами и количеством найденных по ним страниц: 4

• «Соболь | Куница» — 6400 страниц; 4
• «Соболь & Куница» — 550 страниц; 4
• «Соболь» — 4300 страниц. 4 Нужно найти, сколько страниц будет найдено по запросу «Куница». 4

Решение: 4

1. Обозначим множества как A и B. 4
2. Применим формулу включений-исключений для двух множеств: (A | B) = (A) + (B) – (A & B). 4
3. Пусть A — запрос «Соболь», B — «Куница». 4
4. Подставим в формулу известные значения: 6400 = 4300 + (B) – 550. 4
5. Решим уравнение: 6400 – 4300 + 550 = B, B = 2650. 4

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. 14