Задание 8: Запросы для поисковых систем с использованием логических выражений

Типовая формулировка звучит так: «В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих искомые слова, не изменялся за время выполнения запросов». Далее идёт таблица из 2–3 строк с известными данными, и вопрос: сколько страниц будет найдено по такому-то запросу.

…

• Символ «|» обозначает логическое «ИЛИ» (объединение множеств страниц, содержащих хотя бы одно из слов).
• Символ «&» обозначает логическое «И» (пересечение множеств страниц, содержащих оба слова одновременно).
• Основная формула — формула включений и исключений для двух множеств: $$N(A \cup B) = N(A) + N(B) - N(A \cap B)$$ где $N(A \cup B)$ — количество страниц по запросу «A | B», $N(A)$ и $N(B)$ — количество страниц по одиночным запросам, $N(A \cap B)$ — количество страниц по запросу «A & B».
• Из этой формулы легко получить две производные: $$N(A \cap B) = N(A) + N(B) - N(A \cup B)$$ $$N(A) = N(A \cup B) - N(B) + N(A \cap B)$$
• Для трёх слов формула усложняется (включение-исключение для трёх множеств): $$N(A \cup B \cup C) = N(A)+N(B)+N(C)-N(A\cap B)-N(A\cap C)-N(B\cap C)+N(A\cap B\cap C)$$
• Условие задачи всегда подчёркивает, что все запросы выполнялись одновременно — это гарантия, что множество страниц с обоими словами не менялось между запросами, и формулы применимы без поправок на время.
• Числа в таблице обычно даны в тысячах — важно сохранять единицы измерения при вычислениях и в ответе.
• Если в задаче есть запрос с двумя словами без операции (просто «слово1 слово2»), по умолчанию в большинстве вариантов это трактуется как «И» — уточняй условие.

1. Выпиши из таблицы все известные запросы и соответствующие им числа, обозначив слова буквами $A$, $B$ (и $C$, если слово третье).
2. Определи, какая величина неизвестна — это и есть искомый запрос в вопросе задачи.
3. Определи тип неизвестной величины: одиночное слово, пересечение («И») или объединение («ИЛИ»).
4. Выбери подходящую формулу включений-исключений (для двух или трёх слов) и подставь известные значения.
5. Выполни арифметику аккуратно, следя за знаками «плюс» и «минус» в формуле.
6. Проверь результат на здравый смысл: пересечение не может быть больше меньшего из одиночных запросов; объединение не может быть меньше большего из одиночных запросов и не может превышать сумму одиночных запросов.
7. Запиши ответ в тех же единицах, что указаны в таблице (обычно тысячи страниц), без указания самой единицы измерения, если требуется только число.