Задача: CE3644

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. | **Запрос** | **Найдено страниц** **(в сотнях тысяч)** | | --- | --- | | *Прокофьев* | 87 | | *Апельсин* | 39 | | *Лимон* | 52 | | *Прокофьев | Апельсин | Лимон* | 150 | | *Прокофьев & Апельсин* | 19 | | *Прокофьев & Лимон* | 0 | Какое количество страниц (в сотнях тысяч) будет найдено по запросу *Апельсин & Лимон*? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. --- Номер задачи: CE3644 📚 # Тема 08. Логические выражения в поисковых запросах На ОГЭ эта тема проверяет умение применять формулу включений-исключений для подсчёта количества страниц, найденных поисковой системой по разным запросам. --- ## 1. Операторы поискового запроса | Оператор | Символ | Смысл | Результатов | |----------|--------|-------|-------------| | И | `&` | Страницы, где есть **оба** слова | Меньше | | ИЛИ | `\|` | Страницы, где есть **хотя бы одно** слово | Больше | | НЕ | `-` или `NOT` | Страницы **без** указанного слова | — | > **Совет:** "И" — пересечение (сужает поиск). "ИЛИ" — объединение (расширяет поиск). --- ## 2. Диаграмма Эйлера–Венна Представьте два круга: ``` ┌───────────────────────┐ │ A ╔═══╗ B │ │ только ║ A ║ только│ │ A ║ & ║ B │ │ ║ B ║ │ │ ╚═══╝ │ └───────────────────────┘ ``` - Левая часть (только в A): страницы только с первым словом. - Правая часть (только в B): страницы только со вторым словом. - Пересечение (A & B): страницы с обоими словами. - Всё вместе (A | B): все страницы хотя бы с одним словом. --- ## 3. Формула включений-исключений **Основная формула для двух множеств:** $$N(A \,|\, B) = N(A) + N(B) - N(A \,\&\, B)$$ Где: - $N(A)$ — количество страниц по запросу A - $N(B)$ — количество страниц по запросу B - $N(A \,\&\, B)$ — страницы по запросу "A И B" (пересечение) - $N(A \,|\, B)$ — страницы по запросу "A ИЛИ B" (объединение) **Из этой формулы можно выразить любую переменную:** $$N(A \,\&\, B) = N(A) + N(B) - N(A \,|\, B)$$ $$N(A) = N(A \,|\, B) - N(B) + N(A \,\&\, B)$$ --- ## 4. Типовая задача ОГЭ **Пример:** - По запросу "кот" найдено 800 страниц. - По запросу "мышь" найдено 600 страниц. - По запросу "кот И мышь" найдено 200 страниц. - Сколько страниц найдёт запрос "кот ИЛИ мышь"? **Решение:** $$N(\text{кот} \,|\, \text{мышь}) = 800 + 600 - 200 = \mathbf{1200}$$ --- **Обратный пример:** - По запросу "кот" найдено 800 страниц. - По запросу "мышь" найдено 600 страниц. - По запросу "кот ИЛИ мышь" найдено 1100 страниц. - Сколько страниц найдёт запрос "кот И мышь"? **Решение:** $$N(\text{кот} \,\&\, \text{мышь}) = 800 + 600 - 1100 = \mathbf{300}$$ --- ## 5. Ограничения на значения **Важные неравенства, которые всегда выполняются:** $$N(A \,\&\, B) \leq N(A)$$ $$N(A \,\&\, B) \leq N(B)$$ $$N(A \,|\, B) \geq N(A)$$ $$N(A \,|\, B) \geq N(B)$$ $$N(A \,\&\, B) \geq 0$$ > **Совет:** Если в задаче несколько вариантов ответа — проверьте их на соответствие этим неравенствам. Отрицательное пересечение — невозможно. --- ## 6. Случай с тремя множествами Для трёх запросов A, B, C: $$N(A|B|C) = N(A) + N(B) + N(C) - N(A\&B) - N(A\&C) - N(B\&C) + N(A\&B\&C)$$ На ОГЭ три множества встречаются редко, но знать формулу полезно. --- ## 7. Типичные ошибки - **Перепутать & и |.** "И" → меньше результатов. "ИЛИ" → больше. - **Забыть вычесть пересечение.** При сложении N(A) и N(B) страницы пересечения считаются дважды — надо вычесть один раз. - **Отрицательное пересечение.** Если формула даёт N(A & B) < 0 — в данных ошибка или неверный вариант ответа. - **Думать, что A & B всегда маленькое.** Пересечение может быть равно N(A) (если все страницы A входят в B). --- ## 8. Лайфхаки для ОГЭ > **Совет:** Нарисуйте два пересекающихся круга. Подпишите известные значения. Неизвестное найдите из диаграммы. > **Совет:** Запомните одну формулу: `|A ИЛИ B| = |A| + |B| - |A И B|`. Из неё выводится всё остальное. > **Совет:** Быстрая проверка: N(A & B) не может быть больше ни N(A), ни N(B). Если получилось — ищите ошибку.