Задание 15: Преобразование логических выражений

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

…

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