Логические задачи ЕГЭ: поиск переменной и отрезки

Учимся решать задание №15 ЕГЭ: преобразуем импликацию, рисуем отрезки на числовой прямой и находим параметр A, а потом проверяем ответ перебором на Python.

Задание 15 ЕГЭ по информатике — это формула с импликацией, которая должна быть истинна при всех значениях переменной x. Внутри спрятан параметр A (число или отрезок), и наша задача — найти его наибольшее или наименьшее значение, при котором формула остаётся тождественно истинной.

Звучит страшно, но за этим скрывается всего один приём: переписать импликацию так, чтобы вместо логики увидеть геометрию — отрезки на числовой прямой. Давайте разберёмся, почему это работает, и набьём руку на двух полностью разобранных задачах.

Зачем вообще преобразовывать импликацию

Импликация P -> Q («если P, то Q») ложна ровно в одном случае: когда посылка P истинна, а следствие Q ложно. Запомните эту единственную «дырку» — именно её мы и будем затыкать.

Отсюда главный вывод для ЕГЭ:

Формула P -> Q истинна при всех x тогда и только тогда, когда всякий раз, когда выполнена посылка P, выполнено и следствие Q. На языке множеств: множество «x, где P истинно» целиком лежит внутри множества «x, где Q истинно».

Если P задаёт отрезок и Q задаёт отрезок, то «P -> Q истинна всегда» превращается в простое «отрезок P вложен в отрезок Q». А вложенность отрезков мы видим глазами на числовой прямой.

Задача 1. Найти наименьшее A

Найдите наименьшее натуральное число A, при котором выражение

(30 ≤ x) И (x ≤ 50)  →  (14 ≤ x) И (x ≤ A)

истинно при любом натуральном x.

Шаг 1. Опознаём отрезки

Посылка (30 ≤ x) И (x ≤ 50) — это «x принадлежит отрезку [30; 50]». Следствие (14 ≤ x) И (x ≤ A) — это «x принадлежит отрезку [14; A]». Параметр A — это правый конец второго отрезка, и мы можем его двигать.

Шаг 2. Переводим в язык вложенности

По правилу импликации формула истинна при всех x ⟺ отрезок посылки [30; 50] целиком лежит внутри отрезка следствия [14; A]. Левый конец уже в порядке: 14 ≤ 30. Осталось разобраться с правым концом.

Шаг 3. Условие на правый конец

Чтобы [30; 50] ⊆ [14; A], правый край A должен дотягиваться хотя бы до 50:

A ≥ 50

Если A = 49, то число x = 50 попадает в посылку (30 ≤ 50 ≤ 50 — истина), но не попадает в следствие (50 ≤ 49 — ложь). Вот та самая «дырка» 1 -> 0, и формула рушится. А при A = 50 эта дырка исчезает.

Шаг 4. Ответ

Нам нужно наименьшее A, удовлетворяющее A ≥ 50. Это A = 50.

Проверяем ответ перебором

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

def F(x, A):
    P = (30 <= x <= 50)        # посылка: x в [30; 50]
    Q = (14 <= x <= A)         # следствие: x в [14; A]
    return (not P) or Q       # импликация P -> Q

def solve():
    good = []
    for A in range(1, 100):
        # формула должна быть истинна при всех x из проверочного диапазона
        if all(F(x, A) for x in range(1, 100)):
            good.append(A)
    return good

res = solve()
print("Подходящие A:", res)
print("Наименьшее A:", min(res))

Программа печатает список, который начинается с 50, и строку Наименьшее A: 50. Наше аналитическое решение подтвердилось. Обратите внимание на трюк (not P) or Q — это и есть импликация, записанная через базовые операции.

Подходящие A: [50, 51, 52, 53, ... , 99]
Наименьшее A: 50

Задача 2. Найти наибольшее A

Найдите наибольшее натуральное число A, при котором выражение

(3 ≤ x) И (x ≤ A)  →  (3 ≤ x) И (x ≤ 30)

истинно при любом натуральном x.

Шаг 1. Где теперь стоит A

Теперь параметр A прячется в посылке: (3 ≤ x) И (x ≤ A) — это отрезок [3; A]. Следствие фиксировано: отрезок [3; 30]. Условие истинности — отрезок посылки вложен в отрезок следствия: [3; A] ⊆ [3; 30].

Шаг 2. Условие на A

Левые концы совпадают, значит всё решает правый конец: A ≤ 30. При A = 31 число x = 31 входит в посылку, но не входит в следствие (31 ≤ 30 — ложь) — формула ломается.

Шаг 3. Ответ и важная тонкость

Нам нужно наибольшее A с условием A ≤ 30, то есть A = 30.

Тонкость про «пустую посылку». Если бы спросили наименьшее A, ответ был бы неожиданным: при A = 1 или A = 2 отрезок [3; A] пуст (нижняя граница больше верхней), посылка ложна при всех x, и импликация автоматически истинна (вспомните строки 0 -> ... в таблице). Перебор честно покажет такие «вырожденные» A — поэтому, читая список программы, всегда сверяйтесь с тем, какое именно A (наибольшее или наименьшее) требуется в задаче.

А что с делимостью

Половина заданий 15 говорит не про отрезки, а про делимость: ДЕЛ(x, n) означает «x делится на n». Приём тот же — переписать импликацию через «всякий x, для которого истинна посылка, удовлетворяет следствию». Например, утверждение «формула ДЕЛ(x, A) -> ДЕЛ(x, 30) истинна при всех натуральных x» означает «каждое число, кратное A, кратно 30», то есть A само должно делиться на 30. Множества «кратные A» играют роль отрезков, а вложенность множеств — роль вложенности отрезков. Брутфорс-проверка устроена идентично: меняем P и Q на условия x % A == 0 и x % 30 == 0.

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

• Путают направление вложенности. Истинна всегда — значит отрезок посылки вложен в отрезок следствия, а не наоборот.
• Берут не тот конец отрезка. Когда A — это «наименьшее», часто получается «A не меньше чего-то»; когда «наибольшее» — «A не больше чего-то». Не перепутайте знак.
• Забывают про пустую посылку. Если отрезок посылки может стать пустым, импликация становится тождественно истинной, и перебор выдаёт лишние вырожденные значения.
• Слишком узкий диапазон перебора. Если проверять x только до 50, можно пропустить контрпример. Берите диапазон с запасом.

Коротко

• Импликация P -> Q ложна только при P = 1, Q = 0 — это её единственная «дырка».
• «Истинна при всех x» ⟺ множество посылки вложено в множество следствия (отрезок в отрезок, кратные в кратные).
• Рисуйте отрезки на числовой прямой и следите за нужным концом: для «наименьшего A» обычно A ≥ k, для «наибольшего A» — A ≤ k.
• Перебор на Python через (not P) or Q — быстрый способ проверить аналитический ответ.