Задание 8. Поисковые запросы: И, ИЛИ и круги Эйлера
В этом задании нужно определить количество страниц, найденных по поисковому запросу. Разберём смысл операций, научимся читать диаграммы и решим задачи несколькими способами.
1. Что означают И и ИЛИ
Представим, что каждая точка — отдельная страница. Круг A содержит все страницы со словом «Кот», а круг B — все страницы со словом «Пёс». Если на странице встречаются оба слова, её точка находится в общей части кругов.
И — нужны оба слова
Кот & Пёс
Страница подходит, только если на ней есть и «Кот», и «Пёс».
На диаграмме: закрашиваем только пересечение кругов — их общую часть. Боковые области не подходят: там есть лишь одно из двух слов.
ИЛИ — достаточно хотя бы одного
Кот | Пёс
Подходит страница со словом «Кот», со словом «Пёс» или с обоими словами сразу.
На диаграмме: закрашиваем оба круга целиком, включая пересечение. Такое множество называют объединением.
ИЛИ включает случай «оба слова». Страница с двумя словами подходит и для И, и для ИЛИ. Но в результате каждого отдельного запроса она учитывается только один раз.
| Что есть на странице |
Кот & Пёс |
Кот | Пёс |
| Только «Кот» |
Не подходит |
Подходит |
| Только «Пёс» |
Не подходит |
Подходит |
| Оба слова |
Подходит |
Подходит |
| Ни одного из этих слов |
Не подходит |
Не подходит |
Вне обоих кругов находятся страницы, на которых нет ни «Кот», ни «Пёс». Они не входят ни в один из двух результатов, показанных выше.
Будем обозначать через N(A) количество страниц в множестве A, через N(A & B) — количество страниц в пересечении, через N(A | B) — в объединении.
Считаем страницы, а не число повторений слова. Размеры кругов и областей на рисунках условные: по их площади нельзя определять количество страниц.
2. Два слова: одна задача — четыре способа
Все количества в этой задаче указаны в тысячах страниц.
| Запрос |
Найдено, тыс. страниц |
| Кот |
700 |
| Пёс |
500 |
| Кот | Пёс |
900 |
Сколько тысяч страниц найдётся по запросу Кот & Пёс?
Способ 1. Найти отдельные части
В объединении 900 тысяч страниц. Уберём все страницы со словом «Кот». Останутся страницы только со словом «Пёс»:
900 − 700 = 200.
Всего страниц со словом «Пёс» — 500 тысяч. Уберём из них найденную часть «только Пёс»:
500 − 200 = 300.
Оставшиеся страницы содержат оба слова.
Способ 2. Убрать двойной счёт
Сложим результаты двух отдельных запросов:
700 + 500 = 1200.
Страницы с обоими словами попали в эту сумму дважды: один раз как страницы про кота, второй — как страницы про пса. В объединении каждая страница учтена один раз.
1200 − 900 = 300.
Разница и есть количество страниц в общей части.
Способ 3. Составить уравнение
Пусть x — количество тысяч страниц с обоими словами. Тогда только «Кот» — 700 − x, только «Пёс» — 500 − x.
Объединение состоит из трёх отдельных частей:
(700 − x) + x + (500 − x) = 900
1200 − x = 900
x = 300.
Способ 4. Пронумеровать области диаграммы
Разделим рисунок на три непересекающиеся области и присвоим каждой номер:
| Область |
Какие страницы находятся внутри |
| 1 |
Есть «Кот», нет «Пёс». |
| 2 |
Есть оба слова. |
| 3 |
Есть «Пёс», нет «Кот». |
Обозначим через N₁, N₂, N₃ количества тысяч страниц в этих областях. Теперь каждый запрос можно записать как сумму:
| Запрос |
Номера областей |
Равенство |
| Кот |
1, 2 |
N₁ + N₂ = 700 |
| Пёс |
2, 3 |
N₂ + N₃ = 500 |
| Кот | Пёс |
1, 2, 3 |
N₁ + N₂ + N₃ = 900 |
| Кот & Пёс |
2 |
Нужно найти N₂ |
Из объединения вычтем весь круг A:
N₃ = 900 − 700 = 200.
Теперь из всего круга B вычтем область 3:
N₂ = 500 − 200 = 300.
При желании найдём и область 1: N₁ = 700 − 300 = 400. Получилась полностью заполненная диаграмма:
Проверка: круг A — 400 + 300 = 700; круг B — 300 + 200 = 500; объединение — 400 + 300 + 200 = 900.
1, 2, 3 — номера областей, а не количества страниц. Поэтому пишем N₁ + N₂ = 700. Запись «1 + 2 = 700» была бы неверной арифметической записью.
Ответ: 300. Во всех четырёх способах мы нашли одну и ту же общую часть кругов.
3. Формулы, которые теперь легко понять
Формулы следуют из того, как круги разбиваются на отдельные области. В примерах ниже N(A) = 700, N(B) = 500, N(A & B) = 300.
| Что ищем |
Формула |
Пример |
| Хотя бы одно слово |
N(A | B) = N(A) + N(B) − N(A & B) |
700 + 500 − 300 = 900 |
| Оба слова |
N(A & B) = N(A) + N(B) − N(A | B) |
700 + 500 − 900 = 300 |
| Только A |
N(A) − N(A & B) |
700 − 300 = 400 |
| Только B |
N(B) − N(A & B) |
500 − 300 = 200 |
| Ровно одно из двух слов |
N(A) + N(B) − 2 · N(A & B) |
700 + 500 − 2 · 300 = 600 |
Почему в последней строке вычитаем пересечение дважды? В сумме N(A) + N(B) общие страницы учтены два раза, а в результате «ровно одно слово» их не должно быть совсем.
Чтобы найти страницы, не содержащие ни A, ни B, нужно знать общее количество страниц в рассматриваемой совокупности. Тогда из него вычитают N(A | B).
4. Скобки: как читать сложный запрос
A & (B | C)
Слово A обязательно. Кроме него, должно быть хотя бы одно из слов B и C. Оба слова B и C одновременно тоже разрешены.
Страница только со словом C не подходит.
(A & B) | C
Подойдёт страница, на которой есть одновременно A и B, или любая страница со словом C.
Страница только со словом C подходит.
Если скобок нет, сначала выполняется И, затем ИЛИ. Поэтому A & B | C читается как (A & B) | C.
Полезное преобразование:
A & (B | C) = (A & B) | (A & C)
Слева: A и хотя бы одно из B, C. Справа: либо пара A и B, либо пара A и C. Это один и тот же набор страниц.
5. Три слова: подробный разбор тремя способами
Рассмотрим пример с запросами «Динамо», «Зенит» и «Спартак». Количество страниц указано в тысячах. Во время выполнения запросов состав страниц не менялся.
| Запрос |
Найдено, тыс. страниц |
| Динамо & (Зенит | Спартак) |
840 |
| Динамо & Зенит |
530 |
| Динамо & Зенит & Спартак |
130 |
Нужно найти количество тысяч страниц по запросу Динамо & Спартак.
Сначала переведём условие на обычный язык
840: есть «Динамо» и хотя бы одно из слов «Зенит», «Спартак».
530: есть «Динамо» и «Зенит». Слово «Спартак» на части этих страниц тоже может встречаться.
130: есть все три слова одновременно.
Ищем: страницы с «Динамо» и «Спартак», в том числе страницы, на которых есть ещё и «Зенит».
Способ 1. Вычесть известную часть
Из 840 уберём все 530 страниц с парой «Динамо» и «Зенит». Останутся страницы с «Динамо» и «Спартак», на которых нет «Зенита»:
840 − 530 = 310.
Но в искомый запрос входят и страницы со всеми тремя словами. При вычитании мы их убрали, поэтому возвращаем:
310 + 130 = 440.
Способ 2. Объединение двух множеств
Обозначим X — страницы с «Динамо» и «Зенит», Y — страницы с «Динамо» и «Спартак».
Тогда N(X) = 530; N(Y) = x; N(X | Y) = 840. Общая часть X и Y — страницы со всеми тремя словами, их 130.
840 = 530 + x − 130
x = 840 − 530 + 130 = 440.
На этой схеме круги обозначают уже пары слов: X — «Динамо и Зенит», Y — «Динамо и Спартак». Поэтому правая отдельная область 310 — это «Динамо и Спартак без Зенита».
Способ 3. Через семь пронумерованных областей
Шаг 1. Построим три круга по отдельным словам: A — «Динамо», B — «Зенит», C — «Спартак». Пронумеруем семь непересекающихся областей внутри кругов.
Закрашенная часть — искомое пересечение A и C. Оно состоит из областей 4 и 5.
| Область |
Слова на странице |
| 1 |
Только «Динамо». |
| 2 |
«Динамо» и «Зенит», без «Спартака». |
| 3 |
Только «Зенит». |
| 4 |
Все три слова. |
| 5 |
«Динамо» и «Спартак», без «Зенита». |
| 6 |
«Зенит» и «Спартак», без «Динамо». |
| 7 |
Только «Спартак». |
Здесь «только» относится к трём рассматриваемым словам. Любые другие слова на странице могут быть. Вне кругов остаются страницы без всех трёх слов; для этой задачи они не нужны.
Шаг 2. Переведём каждый запрос в набор областей. Пусть Nᵢ — количество тысяч страниц в области с номером i.
| Запрос |
Области |
Равенство |
| Динамо & (Зенит | Спартак) |
2, 4, 5 |
N₂ + N₄ + N₅ = 840 |
| Динамо & Зенит |
2, 4 |
N₂ + N₄ = 530 |
| Динамо & Зенит & Спартак |
4 |
N₄ = 130 |
| Динамо & Спартак |
4, 5 |
Ищем N₄ + N₅ |
Как прочитать первую строку на рисунке? Сначала внутри B или C выбираем всё, что относится хотя бы к одному из этих кругов. Затем оставляем только часть внутри A. Получаются области 2, 4 и 5. Область 1 не подходит: в ней нет ни B, ни C.
Шаг 3. Вычтем вторую строку из первой. Области 2 и 4 входят в оба запроса, поэтому исчезнут при вычитании. Останется область 5:
(N₂ + N₄ + N₅) − (N₂ + N₄) = 840 − 530
N₅ = 310.
Шаг 4. Соберём искомый запрос из областей 4 и 5:
N₄ + N₅ = 130 + 310 = 440.
Можно найти и область 2: N₂ = 530 − 130 = 400. Проверка первой строки: 400 + 130 + 310 = 840.
Все семь областей вычислять не требуется. Для ответа достаточно областей 4 и 5. Количества страниц в областях 1, 3, 6, 7 неизвестны — это не означает, что они равны нулю.
Проверка общей формулой: 530 + 440 − 130 = 840.
Ответ: 440. Вопрос задан в тысячах страниц, поэтому записываем 440, а не 440 000.
6. Если нужно заполнить все области трёх кругов
В более сложной задаче могут быть известны количества страниц для каждого слова и для всех пересечений. Например, все значения даны в тысячах:
| Множество или пересечение |
Количество |
| A; B; C |
60; 50; 40 |
| A & B; A & C; B & C |
20; 15; 10 |
| A & B & C |
5 |
Начинаем с центра и движемся к краям. Это помогает не посчитать одну страницу несколько раз.
Шаг 1. Все три слова
В центр вписываем известное тройное пересечение:
5.
Шаг 2. Ровно два слова
Из каждого парного пересечения убираем центр:
A и B без C: 20 − 5 = 15
A и C без B: 15 − 5 = 10
B и C без A: 10 − 5 = 5
Шаг 3. Только одно слово
Из целого круга убираем все уже заполненные части этого круга:
Только A: 60 − 15 − 10 − 5 = 30
Только B: 50 − 15 − 5 − 5 = 25
Только C: 40 − 10 − 5 − 5 = 20
На этом рисунке подписаны количества тысяч страниц, а не номера областей. Любой запрос теперь можно собрать из нужных частей:
| Что требуется |
Какие части складываем |
Результат |
| Хотя бы одно из трёх слов |
30 + 15 + 25 + 5 + 10 + 5 + 20 |
110 |
| Ровно одно слово |
30 + 25 + 20 |
75 |
| Ровно два слова |
15 + 10 + 5 |
30 |
| Не менее двух слов |
15 + 10 + 5 + 5 |
35 |
Другой способ найти объединение: формула для трёх множеств
N(A | B | C) = N(A) + N(B) + N(C)
− N(A & B) − N(A & C) − N(B & C)
+ N(A & B & C)
60 + 50 + 40 − 20 − 15 − 10 + 5 = 110.
Почему тройное пересечение прибавляем в конце? При сложении трёх кругов центральная область учтена три раза. Затем при вычитании трёх парных пересечений она вычтена тоже три раза. Получается ноль учётов, а нужен один — поэтому добавляем её обратно.
7. Как выбрать способ и проверить себя
| Ситуация |
Удобное действие |
| Два слова, известны оба отдельных запроса и объединение |
Найти пересечение по формуле или через три области. |
| Сложный запрос со скобками |
Сначала прочитать его словами и отметить нужные области. |
| Три слова, несколько условий |
Пронумеровать области и записать для каждого запроса сумму Nᵢ. |
| Нужна только часть диаграммы |
Найти нужные области; остальные можно не вычислять. |
| Нужно заполнить все семь областей |
Начать с тройного пересечения, затем найти ровно два слова, затем ровно одно. |
Частые ошибки
- ИЛИ не исключает общую часть. Страницы с обоими словами тоже подходят.
- A & B не означает «без C». Тройное пересечение входит в парное.
- N(A) относится ко всему кругу A. Это не только его отдельная боковая область.
- Символы & и | задают логические условия. Чтобы перейти к арифметике, считаем страницы в выбранных областях.
- Все величины должны быть в одинаковых единицах. Если вопрос задан в тысячах, ответ тоже даём в тысячах.
- Количество страниц в области не может быть отрицательным. Отрицательное значение — повод проверить чтение условия и вычисления.
Быстрая проверка:
N(A & B) ≤ N(A) ≤ N(A | B).
То же верно для B. Пересечение не больше каждого отдельного множества; объединение не меньше каждого из них. Равенство возможно. А вот сравнить N(A) и N(B) без дополнительных данных нельзя.
8. Проверь себя
Сначала реши самостоятельно. Во всех четырёх заданиях количества указаны в тысячах страниц.
Задача 1. Найти пересечение
Луна — 900; Марс — 600; Луна | Марс — 1200. Сколько страниц найдётся по запросу Луна & Марс?
Проверить ответ и решение
Ответ: 300.
900 + 600 − 1200 = 300.
Через области: только Марс — 1200 − 900 = 300; общая часть — 600 − 300 = 300.
Задача 2. Ровно одно слово
Робот — 650; Дрон — 450; Робот & Дрон — 150. Сколько страниц содержит ровно одно из этих двух слов?
Проверить ответ и решение
Ответ: 800.
Только Робот: 650 − 150 = 500. Только Дрон: 450 − 150 = 300. Сумма: 500 + 300 = 800.
По формуле: 650 + 450 − 2 · 150 = 800. Для сравнения: объединение равно 950, потому что в него входят и общие 150.
Задача 3. Запрос со скобками
Лес & (Сосна | Берёза) — 560;
Лес & Сосна — 350;
Лес & Сосна & Берёза — 90.
Найди результат запроса Лес & Берёза.
Проверить ответ и решение
Ответ: 300.
Без слова «Сосна»: 560 − 350 = 210. Возвращаем страницы со всеми тремя словами: 210 + 90 = 300.
Если взять нумерацию из пункта 5 и обозначить A — Лес, B — Сосна, C — Берёза, то N₅ = 210, N₄ = 90, ответ N₄ + N₅ = 300.
Задача 4. Ровно два из трёх
A & B — 12; A & C — 10; B & C — 9; A & B & C — 4. Сколько страниц содержит ровно два из трёх слов?
Проверить ответ и решение
Ответ: 19.
Из каждого парного пересечения вычитаем тройное:
(12 − 4) + (10 − 4) + (9 − 4) = 19.
Если бы требовалось «не менее двух», нужно было бы добавить центр один раз: 19 + 4 = 23.