Как решать задание 15 ЕГЭ по информатике — логика и множества

О чём задание 15

Задание 15 КЕГЭ проверяет, как ты оперируешь логическими выражениями с кванторами. Формально в условии всегда дана формула вида

(P(x)) → (Q(x) ∨ R(x))

или с большим числом частей, и требуется выполнение этой формулы для всех x из некоторого множества. Множества бывают двух типов:

• Числовая прямая — x пробегает все действительные числа, условия задаются отрезками/лучами/интервалами.
• Натуральные числа с делимостью — x пробегает натуральные, условия задаются множествами кратных числам.

Задание стоит 1 первичный балл, уровень повышенный. Тайминг — 8-10 минут. В КЕГЭ 2026 у тебя 235 минут на 27 заданий, и задание 15 — одно из тех, где разумно сразу подключать Python. Полный обзор КЕГЭ 2026 — в статье ЕГЭ по информатике 2026 — что изменилось.

Теория: минимум, который решает задачу

Импликация и её раскрытие

Импликация A → B ложна только в одном случае: A = истина, B = ложь. Во всех остальных случаях истинна. Формальное переписывание:

A → B   ≡   ¬A ∨ B

В задачах множеств это превращается в подмножество: утверждение ∀x (x ∈ A → x ∈ B) означает ровно A ⊆ B. Если x лежит в A — должен лежать и в B.

Конъюнкция, дизъюнкция и множества

В логике переведи операции на язык множеств:

Логика	Множества
A ∧ B (И)	Пересечение A ∩ B
A ∨ B (ИЛИ)	Объединение A ∪ B
¬A (НЕ)	Дополнение Ā
A → B	Ā ∪ B

Часто в задаче стоит (x ∈ A) → ((x ∈ P) ∧ (x ∈ Q)). Это значит: A ⊆ P ∩ Q. То есть A должно лежать внутри пересечения P и Q. Максимальная A, удовлетворяющая условию, — это и есть само P ∩ Q.

Отрицание отрезка — это два луча

Один из самых частых ходов на числовой прямой:

¬(x ∈ [a, b])  ≡  x < a ∨ x > b

То есть отрицание отрезка — это объединение двух лучей наружу. Лучи направлены в противоположные стороны от отрезка. Это нужно, когда в формуле встречается ¬(x ∈ A) или раскрытие A → B как ¬A ∨ B.

Квантор «для всех»

∀x P(x) — формула верна для любого x. Чтобы опровергнуть — достаточно одного контрпримера. В задании 15 часто начинают с поиска такого x, на котором условие ломается, и через это сужают параметр.

Не путай с ∃x P(x) — «существует x, для которого P(x) верно». Этот квантор в задании 15 не используется, но важен в общем материале — аналогия поможет не запутаться.

Тип 1: числовая прямая

Общий шаблон условия

Даны отрезки P и Q (например, P = [15, 40], Q = [25, 60]). Требуется найти наибольшую длину такого отрезка A, что для любого x верна формула

(x ∈ A) → ((x ∈ P) ∧ (x ∈ Q))

Алгоритм решения

1. Переведи формулу в утверждение о подмножестве. Для нашего примера: A ⊆ P ∩ Q.
2. Найди пересечение P и Q. [15, 40] ∩ [25, 60] = [25, 40].
3. Максимальный A — это сам пересечение. Его длина = 40 - 25 = 15.

Если формула сложнее, например (x ∈ A) → ((x ∈ P) → (x ∈ Q)), то раскрой внутреннюю импликацию и приведи к стандартному виду. Получится условие на дополнение.

Пример 1 (числовая прямая)

Условие. Даны отрезки P = [10, 40] и Q = [30, 70]. Найди наибольшую длину отрезка A, такого что формула (x ∈ A) → ((x ∈ P) ∨ (x ∈ Q)) истинна при любом значении x.

Решение руками.

Шаг 1. Формула (x ∈ A) → ((x ∈ P) ∨ (x ∈ Q)) означает A ⊆ P ∪ Q.

Шаг 2. P ∪ Q = [10, 40] ∪ [30, 70] = [10, 70] (отрезки пересекаются по [30, 40], поэтому объединение — один отрезок).

Шаг 3. Максимальный A — это [10, 70] с длиной 60.

Ответ: 60.

Решение на Python (дискретный перебор для проверки):

def in_set(x, segs):
    return any(a <= x <= b for a, b in segs)

P = [(10, 40)]
Q = [(30, 70)]

# Кандидаты на границы A — только точки смены поведения: 10, 30, 40, 70
# Но для надёжности пройдём плотной сеткой по целым
best = 0
for a in range(0, 101):
    for b in range(a, 101):
        ok = True
        for x in range(0, 101):      # по целым; для надёжности можно мельче
            if a <= x <= b:          # x в A
                if not (in_set(x, P) or in_set(x, Q)):
                    ok = False
                    break
        if ok and b - a > best:
            best = b - a
print(best)    # -> 60

Важная тонкость: перебор по целым даёт правильный ответ только если границы в условии целые и шаги между ними целые. В общем случае анализ должен быть аналитическим, а Python — проверкой.

Тип 2: натуральные числа и делимость

Общий шаблон условия

Задача формулируется так: найди наибольшее натуральное число A, такое что формула

(x не делится на A) → ((x не делится на B) ∨ (x не делится на C))

истинна для любого натурального x. Тут B и C — заданные числа (например, 18 и 21).

Переформулировка через множества

Обозначь Dₖ = {x : x делится на k} — множество чисел, кратных k.

• x делится на A ≡ x ∈ D_A
• x не делится на A ≡ x ∉ D_A

Для импликации используем A → B ≡ ¬A ∨ B:

(x ∉ D_A) → ((x ∉ D_B) ∨ (x ∉ D_C))
= (x ∈ D_A) ∨ (x ∉ D_B) ∨ (x ∉ D_C)
= (x ∈ D_A) ∨ ¬(x ∈ D_B ∩ D_C)

Условие истинности для всех x: если x делится и на B, и на C, то x делится на A. То есть

D_B ∩ D_C ⊆ D_A

А пересечение множеств кратных — это множество кратных НОК(B, C). Значит, задача сводится к тому, что A делит НОК(B, C). Максимальное такое A — это сам НОК(B, C).

Алгоритм решения

1. Раскрой импликации и отрицания, сведи к утверждению о подмножестве множеств D_k.
2. Замени пересечения D_B ∩ D_C на D_{НОК(B,C)} и объединения на отношения делимости.
3. Получи условие вида «A делит N» или «N делит A» и найди искомое число.

Пример 2 (делимость)

Условие. Найди наименьшее натуральное число A, такое что формула (x делится на A) → ((x делится на 12) ∧ (x делится на 18)) истинна при любом натуральном x.

Решение руками.

Шаг 1. Формула ∀x ( x ∈ D_A → x ∈ D_{12} ∩ D_{18} ) эквивалентна D_A ⊆ D_{12} ∩ D_{18}.

Шаг 2. Пересечение D_{12} ∩ D_{18} = D_{НОК(12, 18)} = D_{36}.

Шаг 3. Условие D_A ⊆ D_{36} означает, что каждое кратное A должно быть кратно 36. Это возможно тогда и только тогда, когда 36 делит A (т.е. A = 36, 72, 108, ...).

Шаг 4. Минимальное натуральное A = 36.

Решение на Python (самопроверка):

from math import gcd

def lcm(a, b): return a * b // gcd(a, b)

# Ищем минимальное A, при котором формула верна для любого x от 1 до 10_000
for A in range(1, 1001):
    ok = all(
        (x % A != 0) or (x % 12 == 0 and x % 18 == 0)
        for x in range(1, 10_000)
    )
    if ok:
        print(A)   # -> 36
        break

Главное при переводе в Python — импликация A → B пишется как (not A) or B. Перебор по x от 1 до 10_000 надёжен: обычно хватает даже до 2 · НОК, но с запасом спокойнее.

Вариант с «наибольшим A»

Если формула содержит дизъюнкцию и отрицания (например, (x делится на A) → ((x не делится на 12) ∨ (x не делится на 18))), ответ — наибольшее A, и сводится он к условию «A не делится на 36». Максимальное A, не кратное 36, в рамках задачи обычно ищется среди делителей заданного числа или ограничивается верхней границей из условия. Python-перебор решает и этот случай — меняются только условия внутри all(...).

Типичные ошибки

1. Забыл квантор. Решил «существует такой x» вместо «для всех x». Это совершенно разные задачи: в задании 15 всегда «для всех».
2. Неверное отрицание отрезка. Написал ¬(x ∈ [a, b]) = x ∈ [a, b] наоборот. Правильно — два луча наружу: x < a ∨ x > b.
3. Путаница с импликацией. A → B это НЕ A ∧ B и НЕ A ∨ B. Это ¬A ∨ B. На Python — (not A) or B.
4. Неправильный НОК или НОД. Пересечение множеств кратных — НОК, а не НОД. Объединение — сложнее, не всегда сводится к одному D_k.
5. Ошибка в границах перебора. Если ищешь A на числовой прямой, а перебираешь только по целым — можешь пропустить оптимум. Всегда проверяй точки смены поведения (концы отрезков).
6. Недостаточный диапазон x при Python-переборе. Для натуральных с делимостью обычно хватает range(1, 10_000), но в задачах с большими НОК может потребоваться больше. Ориентируйся на НОК входных чисел и проверяй минимум до 2 · НОК.

О других распространённых ловушках — в материале Частые ошибки на ЕГЭ по информатике.

Тайминг и стратегия

Ориентир — 8-10 минут на задание 15. Структура времени:

• 1-2 минуты на чтение условия и классификацию типа (прямая или делимость).
• 3-4 минуты на аналитику (подмножества, отрицания, НОК).
• 3-4 минуты на Python-перебор для проверки ответа.

Если за 12 минут ты не близко к ответу — переходи дальше, возвращайся в конце. Задание 15 стоит 1 балл, и терять время в ущерб заданию 27 (2 балла) нелогично.

Что тренировать

• Раскрытие импликации A → B = ¬A ∨ B — делай это автоматически, без задумывания.
• Отрицание отрезка — лучи, не отрезок.
• Сведение к подмножеству — выработай рефлекс: «для всех x ... → ...» = «подмножество».
• НОК, НОД, делители — знай math.gcd и lcm на Python.
• Python-шаблон перебора — выпиши его на бумаге и перепиши 5 раз, пока не запомнится.
• Разбор 15-20 задач из банка ФИПИ — оба типа: и прямая, и делимость.

Более широкий план подготовки — в материалах План подготовки за 6 месяцев и Как набрать 90+ баллов.

Итог

Задание 15 — 1 балл повышенной сложности на логику с кванторами. Два типа: числовая прямая (отрезки) и натуральные числа (делимость). Ключ — аккуратный перевод логики в множества: импликация — подмножество, И — пересечение, ИЛИ — объединение, НЕ — дополнение. Python-перебор — твой страховочный трос: написал функцию, пробежал по кандидатам, выдал ответ. Тайминг 8-10 минут, стратегия — аналитика + проверка. Прокачав эти шаблоны, ты перестанешь бояться одного из самых нелюбимых заданий КЕГЭ.