Задание 15 ЕГЭ по информатике: побитовая конъюнкция, отрезки, координатная плоскость

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

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

Задание объединяет несколько разных техник, которые встречаются в вариантах под одним и тем же номером:

• работа с побитовой конъюнкцией целых чисел;
• работа с числовыми промежутками (неравенствами на числовой прямой);
• работа с областями на координатной плоскости;
• прочие формулы, где переменные принимают значения из небольшого набора или сводятся к таблице истинности.

По сути, во всех случаях проверяется одно и то же умение: перевести логическую формулу в язык множеств (битов, отрезков, фигур) и понять, при каком условии одно множество полностью содержится в другом.

Как выглядит формулировка и сколько баллов

Типичная формулировка: «Для какого наименьшего неотрицательного целого числа $A$ формула ... тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной $x$)?» Вместо побитовой конъюнкции в других вариантах формула может содержать неравенства вида $x \ge a$, $x \le b$ или условия принадлежности точки $(x,y)$ фигурам на плоскости.

Задание оценивается в 1 первичный балл, относится к повышенному уровню сложности. Ответ — число, которое нужно записать без единиц измерения. На решение стоит отводить не больше 5–7 минут: если формула громоздкая, лучше сразу искать условие ложности, а не истинности — это почти всегда короче.

Что нужно знать

• Таблица истинности импликации: $a \to b$ ложно только тогда, когда $a = 1$, $b = 0$; во всех остальных случаях истинно.
• Отрицание импликации: $\neg(a \to b) = a \wedge \neg b$.
• Законы де Моргана: $\neg(a \vee b) = \neg a \wedge \neg b$, $\neg(a \wedge b) = \neg a \vee \neg b$.
• Приоритет операций (от высшего к низшему): $\neg$, $\&$ (конъюнкция), $\vee$ (дизъюнкция), $\to$ (импликация), $\sim$ (эквивалентность).
• Формула тождественно истинна, если множество значений переменной, при которых она ложна, — пустое.
• Побитовая конъюнкция $m \& n$: результат получается применением логического И к каждому разряду двоичной записи чисел $m$ и $n$.
• Правило чтения условий с $\&$: $x \& K \ne 0$ означает, что у $x$ и $K$ есть хотя бы один общий установленный бит; $x \& K = 0$ означает, что на всех позициях, где у $K$ стоит 1, у $x$ стоит 0.
• Любое целое число раскладывается по степеням двойки: $K = \sum 2^{k_i}$, и это разложение удобно оформлять в виде набора номеров установленных битов.
• Для отрезков: неравенство $x \ge a$ задаёт луч, $x \le b$ — луч, их конъюнкция — отрезок $[a; b]$; объединение отрезков может давать промежуток без разрывов только при определённом соотношении границ.
• Для координатной плоскости: конъюнкция условий — пересечение фигур, дизъюнкция — объединение, отрицание — дополнение до всей плоскости.

Методы решения

1. Битовый анализ (побитовая конъюнкция). Все числа в формуле раскладываются на степени двойки, после чего формула превращается в систему условий на отдельные биты $x$. Наименьшее $A$ находится через определение того, какие биты обязаны в нём присутствовать.

Мини-пример. Пусть нужно, чтобы из $x \& 4 \ne 0$ следовало $x \& A \ne 0$ для всех $x$. Число 4 — это единственный бит (позиция 2). Если $A$ не содержит этот бит, можно взять $x = 4$: тогда $x\&4\ne0$ истинно, а $x\&A=0$ — импликация ложна. Значит, $A$ обязан содержать бит 2, минимальное такое $A = 4$.

2. Метод числовых отрезков. Условия вида $x < a$, $x \ge b$ переводятся в отрезки и лучи на числовой прямой, строится рисунок, и тождественная истинность формулы соответствует тому, что объединение «разрешённых» промежутков покрывает всю область значений $x$ без пропусков.

Мини-пример. Формула $(x < 5) \vee (x \ge A)$ тождественно истинна для всех целых $x$, если промежутки $(-\infty; 5)$ и $[A; +\infty)$ вместе покрывают всю прямую, то есть $A \le 5$. Наибольшее целое $A$ равно 5.

3. Метод координатной плоскости. Каждое условие на $(x, y)$ изображается как фигура (круг, полоса, угол, прямоугольник). Импликация $P \to Q$ тождественно истинна тогда и только тогда, когда фигура $P$ целиком лежит внутри фигуры $Q$ (при этом важно учитывать, включена граница или нет).

Мини-пример. Если $P$ — круг радиуса 3 с центром в начале координат, а $Q$ — круг радиуса $R$ с тем же центром, то $P \to Q$ тождественно истинна при $R \ge 3$; наименьшее такое целое $R = 3$.

4. Метод таблиц истинности и алгебраических преобразований (разное). Если переменных немного или формула содержит параметр в «неудобном» месте, формулу упрощают алгебраически (снятие импликаций, раскрытие отрицаний, вынесение общих множителей) либо строят таблицу истинности по всем комбинациям значений, сравнивая столбцы.

Мини-пример. Формула $(x \to y) \wedge (y \to x)$ равносильна $x \sim y$, что сразу видно после раскрытия импликаций и упрощения — не нужно перебирать все четыре строки таблицы вручную.

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

1. Расставить приоритеты операций и, если нужно, добавить скобки, чтобы не ошибиться в структуре формулы.
2. Определить, при каком условии формула ложна — почти всегда это проще, чем искать условие истинности напрямую, потому что импликация ложна только в одном случае.
3. Последовательно раскрыть все вложенные импликации через $\neg(a \to b) = a \wedge \neg b$, получив в итоге одну большую конъюнкцию элементарных условий.
4. Перевести элементарные условия на язык подтемы: биты числа (для $\&$), отрезки (для неравенств с $x$) или фигуры (для $(x,y)$).
5. Потребовать, чтобы система условий, полученная в шаге 3–4, была невыполнима — то есть не существовало $x$ (или пары $(x,y)$), удовлетворяющего всем условиям одновременно.
6. Из требования невыполнимости вывести ограничение на параметр $A$ и найти его наименьшее/наибольшее допустимое значение.
7. Подставить найденное значение в исходную формулу на граничном случае и убедиться, что импликация действительно не нарушается.

Разбор примеров

Пример 1. Найти наименьшее неотрицательное целое $A$, при котором формула $$(x\&29\ne0) \to \big((x\&17=0) \to (x\&A\ne0)\big)$$ тождественно истинна.

Шаг 1–3. Формула ложна, когда истинна левая часть внешней импликации и ложна правая. Раскрываем: формула ложна тогда и только тогда, когда $$x\&29\ne0 \ \wedge\ x\&17=0 \ \wedge\ x\&A=0.$$

Шаг 4. Раскладываем числа по степеням двойки: $29 = 16+8+4+1$ — установлены биты на позициях 4, 3, 2, 0; $17 = 16+1$ — установлены биты 4 и 0.

Условие $x\&17=0$ означает, что у $x$ биты 4 и 0 равны нулю. При этом условии выражение $x\&29\ne0$ может выполняться только за счёт битов 3 или 2 (биты 4 и 0 уже занулены). Значит, система из шага 3 равносильна: у $x$ бит 4 = 0, бит 0 = 0, и (бит 3 = 1 или бит 2 = 1), и при этом $x\&A=0$.

Шаг 5–6. Чтобы такой $x$ не существовал, $A$ должен «перехватывать» оба варианта: если бы $A$ не содержал бит 3, можно было бы взять $x$ с единственным установленным битом 3 — тогда $x\&A=0$, и формула оказалась бы ложной. Аналогично для бита 2. Значит, $A$ обязан содержать оба бита: 3 и 2, то есть $A \ge 8+4=12$.

Шаг 7. Наименьшее $A = 12$. Проверка: $12 = 1100_2$ пересекается с любым $x$, у которого установлен бит 3 или бит 2, значит условие выполняется. Ответ: 12.

Пример 2. Найти наименьшее неотрицательное целое $A$, при котором формула $$\big((x\&28\ne0)\vee(x\&45\ne0)\big) \to \big((x\&17=0)\to(x\&A\ne0)\big)$$ тождественно истинна.

Шаг 1–3. Формула ложна, когда: $$\big((x\&28\ne0)\vee(x\&45\ne0)\big)\ \wedge\ x\&17=0\ \wedge\ x\&A=0.$$

Шаг 4. Раскладываем числа: $28 = 16+8+4$ — биты 4,3,2; $45 = 32+8+4+1$ — биты 5,3,2,0; $17=16+1$ — биты 4,0.

При условии $x\&17=0$ (биты 4 и 0 равны нулю) выражение $x\&28\ne0$ сводится к «бит 3 или бит 2 установлен», а $x\&45\ne0$ — к «бит 5, 3 или 2 установлен» (бит 0 уже занулён). Дизъюнкция этих двух условий даёт: установлен хотя бы один из битов 5, 3, 2.

Шаг 5–6. Система ложности требует, чтобы при установленном хотя бы одном из битов {5,3,2} выполнялось $x\&A=0$ — этого нужно не допустить. Значит, $A$ должен содержать все три бита: если бы, например, бит 5 отсутствовал в $A$, можно было бы взять $x$ с единственным установленным битом 5, и получить $x\&A=0$, что ломает формулу. Аналогично для битов 3 и 2.

Шаг 7. Минимальное $A = 32+8+4 = 44$. Ответ: 44.

Пример 3 (для самопроверки) решается тем же методом: формула $x\&33=0 \to (x\&45\ne0 \to x\&A\ne0)$ ложна при $x\&33=0 \wedge x\&45\ne0 \wedge x\&A=0$. Так как $33=32+1$ (биты 5,0), а $45=32+8+4+1$ (биты 5,3,2,0), при занулённых битах 5 и 0 условие $x\&45\ne0$ сводится к «бит 3 или бит 2 установлен». Значит, $A$ должен содержать оба этих бита: $A = 8+4=12$.

Во всех трёх примерах видно общее правило: если из условия «внешние биты уже занулены» следует, что оставшееся неравенство $x\&K\ne0$ держится сразу на нескольких независимых битах, то параметр $A$ обязан включать каждый из этих битов по отдельности — иначе всегда найдётся $x$ с единственным «неудобным» битом, который обнуляет пересечение с $A$.

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

• Путают приоритет операций и забывают, что импликация выполняется после конъюнкции и дизъюнкции — это меняет структуру формулы и приводит к неверной системе условий.
• Ищут, при каких $x$ формула истинна, вместо того чтобы искать, при каких она ложна: второй путь почти всегда короче, особенно для сложных импликаций.
• Ошибаются при переводе десятичного числа в биты — стоит всегда явно выписывать степени двойки, а не держать разложение в уме.
• Считают, что для тождественной истинности достаточно, чтобы $A$ пересекался хоть с одним из «опасных» битов, а не с каждым по отдельности — это самая частая ошибка именно в задачах на побитовую конъюнкцию.
• В задачах на отрезки путают строгие и нестрогие неравенства, из-за чего граничное значение параметра оказывается на единицу меньше или больше нужного.
• На координатной плоскости забывают учитывать, входит ли граница фигуры (окружность, прямая) в саму фигуру, — это критично при поиске точного наименьшего/наибольшего значения радиуса или координаты.
• Путают понятия «тождественно истинна» (верно для всех $x$) и «выполнима» (верно хотя бы для одного $x$) — это меняет весь ход решения.
• Забывают, что в ответе нужно указать именно наименьшее (или именно наибольшее) число, а не любое подходящее значение параметра.

Как готовиться

Сначала отработайте перевод чисел в двоичную систему и обратно настолько, чтобы раскладывать двух-трёхзначные числа на степени двойки почти автоматически. Затем натренируйте единый алгоритм: всегда искать условие ложности формулы через раскрытие импликаций, а не пытаться угадывать ответ. Решите подряд десяток задач именно на побитовую конъюнкцию — это самая частая разновидность задания 15 в последних вариантах, и приёмы там почти не меняются от задачи к задаче. После этого разберите отдельно блок с числовыми отрезками (рисуйте числовую прямую и штрихуйте области — это резко снижает число ошибок) и блок с координатной плоскостью (стройте фигуры на бумаге, а не в уме). Полезно после каждой решённой задачи проверять себя подстановкой граничного значения $x$ и параметра — это позволяет поймать ошибку до того, как ответ будет засчитан неверным.