Поразрядная конъюнкция

Что означает запись x & 22?

Числа записывают в двоичной системе друг под другом. В каждом разряде результата стоит 1, только если в этом разряде у обоих чисел 1. Операцию называют поразрядной конъюнкцией: это логическое И, применённое к каждой паре цифр.

Посчитаем 26 & 13. Веса разрядов справа налево — 1, 2, 4, 8, 16, как в теме о системах счисления: 26 = 16 + 8 + 2 = 11010₂, 13 = 8 + 4 + 1 = 01101₂.

В формулах чаще важен не сам результат, а равен ли он нулю. x & M ≠ 0 — у x и M есть общая единица хотя бы в одном разряде. x & M = 0 — общих единиц нет. Например, 26 & 13 ≠ 0, а 26 & 5 = 0: у 5 = 101₂ единицы в разрядах 4 и 1, а у 26 там нули.

В Python операция записывается так же: 26 & 13 даёт 8.

Найдём наименьшее неотрицательное A, при котором формула (x & 22 ≠ 0) → ((x & 10 = 0) → (x & A ≠ 0)) тождественно истинна при любом неотрицательном целом x.

Всё решает A при тех x, у которых есть единица из 22 и нет единиц из 10. A должно иметь общую единицу с каждым таким x.

Заменим стрелки: ¬(x & 22 ≠ 0) ∨ ¬(x & 10 = 0) ∨ (x & A ≠ 0). Части без A ложны, когда x & 22 ≠ 0 и x & 10 = 0. Разложим маски: 22 = 16 + 4 + 2, 10 = 8 + 2. У такого x нет весов 8 и 2, но есть 16 или 4 — единственные веса 22, которых нет в 10.

Возьмём x = 16. У него одна единица, значит, A обязано содержать вес 16 — иначе общей единицы не будет. Так же x = 4 требует вес 4. Значит, в A есть веса 16 и 4, и наименьшее такое A = 16 + 4 = 20.

Проверка: любой x, где решает A, содержит 16 или 4 — общая единица с 20 найдётся. A = 19 = 16 + 2 + 1 не подходит: при x = 4 общих единиц нет, и формула ложна.

Теперь A стоит слева от стрелки: найдём наибольшее A, при котором (x & A ≠ 0) → ((x & 12 = 0) → (x & 5 ≠ 0)) тождественно истинна.

Когда A стоит слева от стрелки, ищут разряды, которые брать в A нельзя, — и берут все остальные.

Заменим стрелки: (x & A = 0) ∨ (x & 12 ≠ 0) ∨ (x & 5 ≠ 0). Части без A ложны, когда у x нет единиц ни из 12 = 8 + 4, ни из 5 = 4 + 1 — то есть нет весов 8, 4 и 1. Тогда нужно x & A = 0.

Такой x может содержать любой другой вес — 2, 16, 32, … Значит, этих весов в A быть не должно. Разрешены только 8, 4 и 1: наибольшее A = 8 + 4 + 1 = 13.

Как проверить ответ 20 программой?

Шаблон тот же, что для задачи темы; меняется только формула и диапазон x. В Python знак & выполняется раньше сравнения, поэтому x & 22 != 0 означает (x & 22) ≠ 0.

def imp(p, q):    return (not p) or q  def f(x, A):    return imp(x & 22 != 0, imp(x & 10 == 0, x & A != 0))

for A in range(0, 256):    if all(f(x, A) for x in range(0, 256)):        print(A)        break

Почему x до 255? Все маски меньше 32 — в них пять разрядов. Разряды x старше пятого с масками не совпадают и на формулу не влияют. Диапазон до 256 берёт все сочетания восьми младших разрядов — с запасом.

• x & M1 там, где 1 у обоих чисел
• x & M ≠ 0есть общая единица
• Наименьшее Aвеса, которые обязаны быть в A
• Наибольшее Aвсе разрешённые веса
• Проверкаx с одной единицей
• Pythonx до 256 — с запасом