Задание 15: истинность логического выражения для всех x

Задание 15 (повышенный, частый камень преткновения): найти A, при котором выражение истинно для ВСЕХ x.

Задание 15 требует найти параметр A (число, длину отрезка или маску), при котором логическая формула с переменной x обращается в истину при любом значении x. Ключ — перебор всех x в нужном диапазоне.

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

Это одно из самых пугающих заданий: формулы громоздкие, с импликациями, делимостью или отрезками, а ответ должен «работать для всех x». Но именно здесь КЕГЭ даёт огромное преимущество: вместо тонких рассуждений можно перебрать все x программой и проверить условие напрямую. Разберём два главных типа.

Тип 1: поразрядная конъюнкция (битовые маски)

Обозначение вида «x & 25» означает поразрядное И числа x и числа 25; запись «(x & 25) ≠ 0» истинна, если у x есть хотя бы один общий единичный бит с 25. Типовая формулировка:

«Найдите наибольшее целое A, при котором выражение ((x & 25) ≠ 0) → (((x & 17) = 0) → ((x & A) = 0)) истинно для всех натуральных x».

Метод: перебираем A, для каждого A проверяем формулу на всех x в достаточно широком диапазоне (хватает x до 1024–2048, чтобы покрыть все значимые биты):

def always_true(A, R=4096):
    for x in range(R):
        p = (x & 25) != 0          # посылка 1
        q = (x & 17) == 0          # посылка 2
        r = (x & A) == 0           # следствие
        # импликация a->b это (not a) or b
        inner = (not q) or r       # q -> r
        whole = (not p) or inner   # p -> (q -> r)
        if not whole:
            return False
    return True

best = 0
for A in range(1, 1025):
    if always_true(A):
        best = A
print("наибольшее A:", best)

Вывод:

наибольшее A: 17

Программа за доли секунды перебрала все A от 1 до 1024 и для каждого проверила формулу на тысячах x. Ответ — 17. Никаких рассуждений о битах и переносах не потребовалось: машина сделала всё за нас. Это и есть главная идея решения задания 15 на КЕГЭ.

Тип 2: отрезки числовой прямой

Вторая разновидность работает с отрезками. Обозначение «x ∈ [a; b]» истинно, когда a ≤ x ≤ b. Типовая формулировка:

«На числовой прямой даны отрезки P = [3; 10] и Q = [8; 20]. Найдите наибольшую длину отрезка A, при котором формула (x ∈ A) → ((x ∈ P) ∨ (x ∈ Q)) истинна при любом x».

Логика: импликация «(x ∈ A) → ...» истинна для всех x ⟺ отрезок A целиком лежит внутри множества, где истинна правая часть. Объединение P и Q (они пересекаются) даёт [3; 20], значит наибольший A — это весь [3; 20], его длина 20 − 3 = 17. Проверим перебором положений и длин отрезка A:

def in_seg(x, lo, hi):
    return lo <= x <= hi

def whole_true(a_lo, a_hi):
    # формула истинна для всех целых x в широком диапазоне?
    for x in range(-10, 60):
        inA = in_seg(x, a_lo, a_hi)
        rhs = in_seg(x, 3, 10) or in_seg(x, 8, 20)   # x in P or x in Q
        if inA and not rhs:        # импликация нарушена
            return False
    return True

best_len = 0
best_seg = None
for lo in range(-10, 60):
    for hi in range(lo, 60):
        if whole_true(lo, hi) and (hi - lo) > best_len:
            best_len = hi - lo
            best_seg = (lo, hi)
print("наибольшая длина A:", best_len, " отрезок:", best_seg)

Вывод:

наибольшая длина A: 17  отрезок: (3, 20)

Тип 3: делимость (ДЕЛ)

Третья частая разновидность работает с делимостью: «ДЕЛ(x, n)» означает «x делится на n без остатка», в Python это x % n == 0. Типовая формулировка: «Найдите наименьшее натуральное A, при котором выражение (ДЕЛ(x, A) → (¬ДЕЛ(x, 6) ∨ ДЕЛ(x, 9))) истинно для всех натуральных x». Снова перебираем A и проверяем на всех x в достаточном диапазоне (хватает диапазона, кратного НОК участвующих чисел):

def always_true(A, R=10000):
    for x in range(1, R):
        left  = (x % A == 0)              # ДЕЛ(x, A)
        right = (x % 6 != 0) or (x % 9 == 0)
        if not ((not left) or right):     # импликация left -> right
            return False
    return True

# ищем НАИМЕНЬШЕЕ подходящее A
for A in range(1, 200):
    if always_true(A):
        print("наименьшее A:", A)
        break

Вывод:

наименьшее A: 9

Логика ответа: импликация истинна для всех x ⟺ всякое число, делящееся на A, попадает в правую часть. При A=9 любое кратное 9 либо не делится на 6, либо делится на 9 — правая часть всегда истинна. Меньшие A (например, кратные 6, но не 9) дают контрпример. Но и без этих рассуждений перебор выдал ответ мгновенно — в этом сила метода.

Как сводить любую формулу к перебору

Универсальный рецепт для задания 15:

1. Запишите правую и левую части как функции от x (используя (not a) or b для импликаций).
2. Параметр A (число / маску / границы отрезка) поставьте во внешний цикл перебора.
3. Для каждого A проверьте формулу на всех x в достаточном диапазоне.
4. Среди прошедших A выберите требуемый — наибольший, наименьший или их количество.

Типичные ловушки

• Узкий диапазон x. Для битовых задач берите x до 1024–4096, иначе пропустите «дальние» биты и получите неверный A.
• Граница отрезка. Уточняйте, входят ли концы (≤ или <). В ЕГЭ обычно входят: [a; b] включает a и b.
• «Для всех x» vs «существует x». Перечитайте задание: ищется A, при котором формула верна при любом x, — значит достаточно одного контрпримера, чтобы A отбросить.
• Наибольшее или наименьшее. Подходящих A может быть много — внимательно выбирайте требуемый экстремум.

Итог

• Задание 15 решается перебором: A — во внешнем цикле, x — во внутреннем; проверяем формулу на всех x.
• Импликацию записывайте как (not a) or b; для битовых задач берите x до нескольких тысяч.
• Для отрезков: импликация «x ∈ A → правда» истинна ⟺ A лежит внутри множества истинности правой части.