Теория
Поисковая система хранит для каждого слова список страниц, на которых оно встречается. Обозначим \(N(A)\) — число страниц, найденных по запросу A, а \(N\) — общее число страниц в индексе. Тогда логические связки описываются формулами включений-исключений: запрос «A или B» (\(A \vee B\)) находит страницы хотя бы с одним из слов, запрос «A и B» (\(A \wedge B\)) — только страницы, где есть оба слова, а запрос «не A» (\(\neg A\)) — всё, где слова A нет.
Для двух запросов \(N(A \vee B) = N(A) + N(B) - N(A \wedge B)\): складывая N(A) и N(B), мы дважды посчитали общие страницы, поэтому пересечение вычитаем один раз. Для трёх запросов формула длиннее: \(N(A \vee B \vee C) = N(A) + N(B) + N(C) - N(A \wedge B) - N(A \wedge C) - N(B \wedge C) + N(A \wedge B \wedge C)\) — тройное пересечение вычиталось трижды, поэтому его возвращают обратно. Отрицание дополняет множество до всего индекса: \(N(\neg A) = N - N(A)\).
Важно: ответ не может быть отрицательным или больше \(N\), а пересечение не может быть больше любого из своих множеств. Если числа противоречат друг другу, задача решения не имеет — это и есть проверка «данные противоречивы».
Пример с решением
- Условие. В поисковом индексе N = 1000 страниц; по запросу A найдено 500 страниц, по запросу B — 400, по обоим сразу — 100. Найти \(N(A \vee B)\).
- Формула. \(N(A \vee B) = N(A) + N(B) - N(A \wedge B)\).
- Подстановка. \(N(A \vee B) = 500 + 400 - 100\).
- Вычисление. \(N(A \vee B) = 800\) страниц.
- Проверка. Пересечение \(100 \le 500\) и \(100 \le 400\), ответ \(800 \le 1000\) — данные согласованы, противоречий нет.
- Ответ. Калькулятор в режиме «N(A ∨ B) по N(A), N(B) и N(A ∧ B)» вернёт 800 страниц и покажет подстановку чисел по шагам.
Главное
- «Или» расширяет ответ: \(N(A \vee B) = N(A) + N(B) - N(A \wedge B)\).
- «И» сужает ответ: \(N(A \wedge B) = N(A) + N(B) - N(A \vee B)\).
- «Не» дополняет множество до всего индекса: \(N(\neg A) = N - N(A)\).
- Противоречие — это не ошибка счёта: пересечение не больше множества, а ответ не больше \(N\).