Логика, множества и поисковые запросы

Логические связки И, ИЛИ, НЕ — это те же самые операции над множествами, и именно поэтому задачи про поисковые запросы решаются кругами Эйлера и одной короткой формулой.

Вы наверняка замечали: когда в поисковике пишут котики & собачки, результатов меньше, а когда котики | собачки — больше. За этим стоит не магия, а строгая логика. Слово «И» сужает, слово «ИЛИ» расширяет. Если научиться видеть за словами множества страниц, то целый класс задач ЕГЭ (задание 8 в части с поисковыми запросами) решается почти устно. Разберёмся, почему так, и доведём навык до формулы.

Главная идея. Каждому слову соответствует множество страниц, где это слово встречается. Тогда логическое И — это пересечение множеств (∩), логическое ИЛИ — объединение (∪), а НЕ — дополнение (всё, что вне множества).

Логика и множества — это одно и то же

Возьмём два высказывания и два множества. Пусть A — множество страниц со словом «крейсер», B — множество страниц со словом «линкор». Запрос «крейсер И линкор» оставляет ровно те страницы, где есть оба слова — это общая часть кругов, то есть пересечение A ∩ B. Запрос «крейсер ИЛИ линкор» оставляет страницы, где есть хотя бы одно слово — это всё, что покрыто хотя бы одним кругом, то есть объединение A ∪ B.

Отсюда сразу важное неравенство, которое мы будем использовать постоянно:

|A ∩ B|  ≤  |A|  ≤  |A ∪ B|

Пересечение никогда не больше каждого из множеств, а объединение — никогда не меньше. Значок |...| читается как «мощность» — количество элементов (здесь — количество страниц).

Круги Эйлера: рисуем, чтобы не запутаться

Круги Эйлера — это диаграмма, где каждое множество изображают кругом. Перекрытие кругов — это пересечение. Вся закрашенная площадь — объединение. Когда в задаче три-четыре запроса, рисунок спасает: вы просто закрашиваете нужные области и считаете.

Запустите код ниже. Он берёт два конкретных множества чисел, считает их мощности через операции Python (& — пересечение, | — объединение — те же значки, что и в поисковых запросах!) и проверяет ключевую формулу, к которой мы идём.

A = {1, 2, 3, 4, 5, 6}   # страницы со словом «крейсер»
B = {4, 5, 6, 7, 8}      # страницы со словом «линкор»

union = A | B            # ИЛИ  -> объединение
inter = A & B            # И    -> пересечение

print("|A|            =", len(A))
print("|B|            =", len(B))
print("|A & B| (общее) =", len(inter))
print("|A | B| (всего) =", len(union))

# Формула включений-исключений:
formula = len(A) + len(B) - len(inter)
print("|A|+|B|-|A&B| =", formula)
print("равно |A | B|? ", formula == len(union))

В выводе вы увидите, что объединение содержит 8 элементов, и формула |A|+|B|-|A&B| даёт ровно те же 8. Это не совпадение, а закон.

|A|            = 6
|B|            = 5
|A & B| (общее) = 3
|A | B| (всего) = 8
|A|+|B|-|A&B| = 8
равно |A | B|?  True

Формула включений-исключений

Если просто сложить мощности двух множеств, общую часть мы посчитаем дважды. Чтобы исправить это, лишнее пересечение вычитают один раз:

|A ∪ B| = |A| + |B| − |A ∩ B|

В наших числах: 6 + 5 = 11, но элементы 4, 5, 6 попали и в A, и в B, то есть посчитаны два раза. Вычитаем |A ∩ B| = 3 и получаем 11 − 3 = 8. Именно так формула «лечит» двойной учёт.

Из этой формулы легко выразить любую из четырёх величин, если три известны. Например:

|B|     = |A ∪ B| − |A| + |A ∩ B|
|A ∩ B| = |A| + |B| − |A ∪ B|

Типовая задача ЕГЭ про поисковые запросы

В задаче дают таблицу: запросы и сколько страниц нашёл по каждому из них поисковый сервер. Нужно найти количество страниц по запросу, которого в таблице нет. Все слова в таких задачах считаются «независимыми» только в логическом смысле — а связь между числами задаёт как раз формула включений-исключений.

Переводим на язык множеств: C — «крейсер», L — «линкор». Тогда строка 1 это |C ∪ L| = 7000, строка 2 это |C| = 4800, строка 3 это |C ∩ L| = 4500. Нужно найти |L|.

Берём формулу и выражаем неизвестное:

|C ∪ L| = |C| + |L| − |C ∩ L|
|L| = |C ∪ L| − |C| + |C ∩ L|
|L| = 7000 − 4800 + 4500 = 6700

Проверьте этот расчёт прямо в коде — заодно убедитесь, что неравенство |C∩L| ≤ |C| ≤ |C∪L| выполняется (иначе условие было бы противоречивым):

CuL = 7000   # Крейсер | Линкор
C   = 4800   # Крейсер
CiL = 4500   # Крейсер & Линкор

L = CuL - C + CiL
print("Линкор =", L)
print("Проверка границ:", CiL <= C <= CuL)

Линкор = 6700
Проверка границ: True

Как упорядочивать запросы по числу результатов

Второй частый тип задания: расставить запросы по возрастанию найденных страниц. Здесь не нужны числа — хватает логики. Запрос с & (пересечение) всегда даёт не больше страниц, чем каждое из слов по отдельности, а запрос с | (объединение) — не меньше. Поэтому для слов «кошки» и «собаки»:

Кошки & Собаки   ≤   Кошки   ≤   Кошки | Собаки
     (самый узкий)              (самый широкий)

Сначала идут все запросы с &, потом одиночные слова, потом запросы с |. Это правило закрывает большинство задач на сортировку без единого вычисления.

Частые ошибки

• Складывают |A| и |B| и забывают вычесть пересечение — получают завышенный ответ. Двойной учёт общей части — ошибка №1.
• Путают значки: & (И, пересечение, меньше результатов) и | (ИЛИ, объединение, больше результатов).
• Считают, что «И» расширяет поиск. Наоборот: «И» требует наличия всех слов сразу, поэтому сужает.
• В формуле |L| = |C∪L| − |C| + |C∩L| теряют знак: вычитают пересечение вместо прибавления. Всегда выражайте переменную аккуратно по шагам.

Коротко

• И = пересечение (∩, значок &), ИЛИ = объединение (∪, значок |), НЕ = дополнение.
• Круги Эйлера: перекрытие — пересечение, вся площадь — объединение.
• Формула включений-исключений: |A ∪ B| = |A| + |B| − |A ∩ B| — вычитаем общую часть, чтобы не посчитать её дважды.
• Неравенство для сортировки запросов: |A ∩ B| ≤ |A| ≤ |A ∪ B|.
• В задачах ЕГЭ переводите слова в множества, подставляйте в формулу и выражайте неизвестное.