Задание 15 ЕГЭ по информатике: математическая логика

Почти в каждой формуле задания 15 главная связка — импликация $A \rightarrow B$ («если А, то Б»). Вся логика задания строится на одном факте — таблице истинности:

Отсюда — стандартный ход решения всего задания 15: вместо того чтобы искать, когда громоздкая формула истинна, ищут когда она ложна (это всегда проще — условие лжи для импликации одно), а затем требуют, чтобы таких $x$ не нашлось ни одного. «Формула тождественно истинна» и «не существует x, при котором формула ложна» — одно и то же утверждение.

1. Импликация через дизъюнкцию

Эта формула превращает импликацию в «или» — с дизъюнкцией проще искать, когда всё выражение ложно (для этого должны быть ложны оба слагаемых).

2. Отрицание импликации

Именно эта формула и есть «условие лжи» из блока выше, записанное символами: импликация не выполняется, когда $A$ истинно, а $B$ ложно.

3. Законы де Моргана

Они нужны, когда после раскрытия импликации внутри формулы остаётся отрицание конъюнкции или дизъюнкции — например, в выражении $\neg(\neg(x \in C) \land \neg(x \in A))$ из примера 2 ниже: по де Моргану это $(x \in C) \lor (x \in A)$, а не что-то более сложное. Частая ошибка — «протащить» отрицание внутрь конъюнкции, не поменяв её на дизъюнкцию: знак связки обязательно переключается.

В этом подтипе предикат — принадлежность отрезку: $x \in D$, $x \in C$, $x \in A$. Формула почти всегда сводится (после раскрытия импликаций и де Моргана по блокам выше) к простому требованию: каждая точка одного отрезка обязана лежать в одном из других. Дальше работает не алгебра, а картинка.

Шаги метода

• нарисуйте числовую прямую и отметьте на ней все заданные отрезки одним слоем ниже другого — так виднее пересечения;
• «закрасьте» (заштрихуйте) отрезок, который формула разрешает не покрывать отрезком $A$ — обычно это тот, что уже упомянут в условии как достаточный (в примере 2 ниже — отрезок $C$);
• незакрашенная часть отрезка, который обязан быть покрыт (например, $D$) — это проблемная зона: именно её должен целиком накрыть отрезок $A$;
• минимальный (или, если спрашивают о наибольшей длине — максимальный при доп. ограничениях) отрезок $A$ — это отрезок ровно по границам проблемной зоны.

Маленький пример целиком

Пусть $D = [2; 10]$, $C = [5; 15]$, и формула требует, чтобы $(x \in D) \rightarrow ((x \in C) \lor (x \in A))$ была истинна при любом $x$. Отрезок $C$ покрывает часть $D$ от 5 до 10, а промежуток $[2; 5)$ остаётся непокрытым — это и есть проблемная зона. Точки, сколь угодно близкие к 5 слева, всё ещё требуют покрытия, поэтому $A$ обязан содержать саму точку 5: минимальный подходящий отрезок — $A = [2; 5]$, длина 3.

Предикат $\text{ДЕЛ}(n, m)$ истинен ровно тогда, когда $n$ кратно $m$, то есть $n \bmod m = 0$. Формулы этого подтипа почти всегда после раскрытия импликации по блоку 1 сводятся к условию вида «каждое $x$, кратное и $p$, и $q$, обязано быть кратно $A$».

Отсюда практический вывод: если вопрос — «наибольшее $A$, при котором каждое кратное $L$ делится на $A$», ответ — это само число $L$ (наибольший делитель числа всегда оно само). НОК считаем через разложение на простые множители:

Например, для $p = 14 = 2 \cdot 7$ и $q = 4 = 2^{2}$ берём максимальную степень каждого простого множителя: $\text{НОК}(14, 4) = 2^{2} \cdot 7 = 28$.

Если же параметр $A$ встречается не в предикате $\text{ДЕЛ}$, а в числовом неравенстве (например, $x + A \ge 100$), делимость нужна только для того, чтобы описать множество «опасных» $x$, а дальше применяется другой приём — переход к худшему случаю: неравенство должно выполняться для всех опасных $x$, а значит — и для самого маленького из них (у неравенства $x + A \ge 100$ требование тем жёстче, чем меньше $x$). Наименьший подходящий $A$ находится подстановкой этого наименьшего опасного $x$ — разбор такого примера смотрите в примере 3 ниже.

На КЕГЭ доступна среда программирования, и полный перебор — законный и самый надёжный способ проверить ручной разбор или решить задачу целиком, если аналитика не складывается. Шаблон для подтипа «делимость» — реализовать формулу дословно и перебрать $A$ и $x$:

def DEL(n, m):
    return n % m == 0

def formula(x, A):
    return DEL(x, A) or (not DEL(x, 14)) or (not DEL(x, 4))

def tozhdestvenno_istinna(A, x_max):
    return all(formula(x, A) for x in range(1, x_max + 1))

best = 0
for A in range(1, 500):
    if tozhdestvenno_istinna(A, x_max=5000):
        best = A
print(best)

Как выбрать границу перебора x_max. Формулы с $\text{ДЕЛ}$ периодичны: значение $\text{ДЕЛ}(x, p)$ повторяется с периодом $p$, а вся формула — с периодом, равным НОК всех делителей, встречающихся в условии. В заданиях банка эти числа не превышают нескольких сотен, поэтому $x_{\text{max}}$ в несколько тысяч (или сразу $10^5$) с большим запасом перекрывает десятки периодов — процессору это стоит долей секунды, а риск «не заметить» контрпример пропадает.

Для подтипа «отрезки» переменная $x$ непрерывна, перебрать все вещественные числа нельзя. Но поскольку границы всех отрезков в условии — целые, истинность формулы может поменяться только в целых точках, а внутри каждого промежутка между соседними целыми она постоянна. Значит достаточно проверить сами целые точки и середины промежутков между ними:

def in_segment(x, a, b):
    return a <= x <= b

def formula(x, a, b):
    D = in_segment(x, 17, 58)
    C = in_segment(x, 29, 80)
    A = in_segment(x, a, b)
    return (not D) or C or A

def tozhdestvenno_istinna(a, b, lo=0, hi=100, step=0.5):
    n = int((hi - lo) / step)
    return all(
        formula(lo + i * step, a, b) for i in range(n + 1)
    )

best = None
for a in range(0, 100):
    for b in range(a, 100):
        if tozhdestvenno_istinna(a, b):
            length = b - a
            if best is None or length < best:
                best = length
print(best)

Шаг перебора $0{,}5$ (половина целого) гарантированно ловит любой промежуток положительной длины между целыми границами, а диапазон $lo..hi$ нужно брать с запасом за пределы всех отрезков из условия. Такой перебор — не «запасной», а основной инструмент самопроверки: расхождение с ручным разбором на 1 почти всегда означает ошибку на границе (открытая/закрытая точка) или ту самую путаницу «длина против количества точек».

День 1–2: выучите таблицу истинности импликации и формулу $A \rightarrow B \equiv \neg A \lor B$ наизусть, потренируйтесь раскрывать отрицание импликации и законы де Моргана на 10–15 коротких формулах без параметра $A$. День 3–5: разберите метод «закрасить числовую прямую» на 5–7 простых отрезках (два-три отрезка в условии, целые границы). День 6–7: разберите приём НОД/НОК на 5–7 задачах делимости, каждый раз проверяя решение перебором в Python.

День 1–3: решайте задания из открытого банка вперемешку — оба подтипа, оба направления («наибольшее» и «наименьшее»), сверяя каждое ручное решение с перебором. День 4–5: отдельно потренируйте пограничные случаи — открытая/закрытая точка на стыке отрезков, наименьший «опасный» $x$ в задачах с неравенством. День 6–7: работайте на время — не больше 3 минут на задание, и проверьте себя в тренажёре на заданиях из банка ФИПИ.