Задание 15 ЕГЭ по информатике: истинность выражения при любом x — разбор и примеры

В задании 15 дана логическая формула с переменной x и параметром A. Требуется найти такое A (наибольшее, наименьшее или наименьшую длину отрезка A), чтобы формула была тождественно истинной — истинной при любом допустимом значении x. Встречаются три основных вида: делимость (предикат ДЕЛ), отрезки на числовой прямой и поразрядная конъюнкция &. Каждый вид можно решить рассуждением, а на экзамене — перепроверить перебором.

Что проверяет задание

• знание логических операций: отрицание ¬, конъюнкция ∧, дизъюнкция ∨, импликация →;
• умение преобразовывать импликацию: P → Q равносильно ¬P ∨ Q;
• понимание, что «истинна при любом x» означает: не существует x, при котором формула ложна;
• умение работать с делимостью, отрезками и двоичной записью чисел.

Типичные формулировки

1. ДЕЛ: «Обозначим через ДЕЛ(n, m) утверждение "n делится без остатка на m". Для какого наибольшего натурального A формула … тождественно истинна?»
2. Отрезки: «На числовой прямой даны отрезки P и Q. Укажите наименьшую возможную длину отрезка A, при котором формула истинна при любом x».
3. Поразрядная конъюнкция: «Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел. Для какого наименьшего неотрицательного A формула тождественно истинна?»
4. Неравенства с двумя переменными x и y: «(x + 2y < A) ∨ (y > x) ∨ (x > 30)» — решаются тем же перебором по двум переменным.

Пошаговый метод

1. Запишите формулу через ¬, ∧, ∨, заменив каждую импликацию.
2. Найдите, при каких x формула ложна без участия A: именно эти x должны «спасаться» условием с A.
3. Подберите A, которое делает формулу истинной для всех таких x, и выберите наибольшее или наименьшее, как просят.
4. Проверьте перебором: переберите A и x в достаточно большом диапазоне и найдите подходящее A программой.

Разбор примера 1 (делимость)

Для какого наибольшего натурального A формула

(ДЕЛ(x, 18) ∧ ДЕЛ(x, 24)) → ДЕЛ(x, A)

тождественно истинна, то есть принимает значение 1 при любом натуральном x?

Формула ложна только тогда, когда x делится и на 18, и на 24, но не делится на A. Числа, делящиеся одновременно на 18 и на 24, — это кратные их наименьшего общего кратного: НОК(18, 24) = 72. Значит, нужно, чтобы каждое кратное 72 делилось на A, то есть A — делитель 72. Наибольший делитель — само 72.

Ответ: 72.

Разбор примера 2 (отрезки)

На числовой прямой даны отрезки P = [12, 40] и Q = [25, 60]. Укажите наименьшую возможную длину отрезка A, при котором формула

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

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Импликация x ∈ P → x ∈ Q ложна, когда x лежит в P, но не лежит в Q, то есть при 12 ≤ x < 25. Все такие x должны попасть в A. Наименьший отрезок, содержащий промежуток [12, 25), — это [12, 25]. Его длина 25 − 12 = 13.

Ответ: 13.

Разбор примера 3 (поразрядная конъюнкция)

Для какого наименьшего неотрицательного целого A формула

(x & 52 = 0) → ((x & 18 ≠ 0) → (x & A ≠ 0))

тождественно истинна при любом неотрицательном целом x?

52 = 110100 в двоичной записи (биты с номерами 5, 4, 2, если нумеровать с нуля справа), 18 = 10010 (биты 4 и 1). Формула ложна, когда x & 52 = 0 (биты 5, 4, 2 у x нулевые), x & 18 ≠ 0 и x & A = 0. Раз бит 4 у x нулевой, условие x & 18 ≠ 0 означает, что у x установлен бит 1. Чтобы формула была истинной, A должно иметь единицу в бите 1 — тогда x & A ≠ 0. Наименьшее такое A = 2**1 = 2.

Ответ: 2.

Код на Python

Перебор — универсальная проверка для всех трёх видов. Важно выбрать диапазон x достаточно широким: для делимости — до нескольких тысяч, для отрезков — с шагом меньше единицы (или по полуцелым точкам), для поразрядной конъюнкции — все числа до 2**k, где k — число бит в константах.

# пример 1: наибольшее A
def ok1(a):
    return all(not (x % 18 == 0 and x % 24 == 0) or x % a == 0
               for x in range(1, 10000))
print(max(a for a in range(1, 1000) if ok1(a)))   # 72

# пример 3: наименьшее A
def f(x, a):
    return (x & 52 != 0) or (x & 18 == 0) or (x & a != 0)
print(next(a for a in range(1024) if all(f(x, a) for x in range(1024))))  # 2

Для отрезков удобнее рассуждать, но проверить можно так же: перебрать x с шагом 0,25 и посмотреть, какие точки обязаны попасть в A; крайние точки дадут концы отрезка.

Формулы с двумя переменными

В некоторых вариантах формула содержит две целые неотрицательные переменные x и y, например (x + 2y < A) ∨ (y > x) ∨ (x > 30). Требование то же: формула должна быть истинной при любых x и y. Рассуждение строится так же — найдём «опасные» пары, для которых две последние скобки ложны: y ≤ x и x ≤ 30. Для них должно выполняться x + 2y < A. Наибольшее значение x + 2y среди таких пар достигается при x = y = 30 и равно 90, поэтому A должно быть больше 90; наименьшее подходящее A = 91.

На компьютере такие задачи решаются двойным циклом по x и y в диапазоне, заметно превышающем числа из условия (например, до 200), и внешним циклом по A. Если ответ меняется при увеличении диапазона, значит, диапазон был выбран слишком маленьким.

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

• Неправильно раскрывают импликацию: P → Q — это ¬P ∨ Q, а не P ∨ ¬Q.
• Ищут, когда формула истинна, а не когда она ложна: проще найти «плохие» x и закрыть их.
• В задачах на ДЕЛ путают НОК и НОД: «делится и на 18, и на 24» — значит, делится на НОК.
• В отрезках забывают про концы: точка 25 принадлежит Q, но отрезок A всё равно должен быть замкнутым, поэтому длина 13, а не 12,999.
• Берут слишком маленький диапазон перебора и получают неверный ответ — особенно когда ищется наибольшее A.
• Путают нумерацию битов в поразрядных задачах: младший бит — нулевой, он соответствует 1.

Потренируйтесь

Решите задания всех трёх видов: задания № 15 в банке. Для отработки переборных программ — задачи с проверкой кода. Логические операции подробно разобраны в статье «Логические операции, таблицы истинности и отрезки». Следующая тема — задание 16: рекурсивные функции.