Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение

(X & 15 ≠ 0) → ((X & 35 ≠ 0) → (X & A ≠ 0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Для начала упростим выражение по закону

a → b = ¬a ˅ b

(X & 15 ≠ 0) → ((X & 35 ≠ 0) → (X & A ≠ 0))

(15 ≠ 0) → ((35 ≠ 0) → (A ≠ 0))

(15 = 0) ˅ (35 = 0) ˅ (A ≠ 0)

Теперь переведём 15 и 35 в двоичную систему счисления:

15₁₀ = 1111₂

35₁₀ = 100011₂

Выражение (15 = 0) ˅ (35 = 0) ˅ (A ≠ 0) должно быть истинно для любого натурального x. Проще говоря, если какое-то число при поразрядном умножении на 15 и на 35 не дают нуля, то при умножении на А это число также не должно давать нуля.

Рассмотрим произведение каждого разряда чисел 15 и 35 на единицу:

В первом столбце указаны разряды (единицы, десятки и т.д.) Во втором столбце проверяется истинность выражения x & 1111 = 0, в третьем — истинность выражения x & 100011 = 0, в четвёртом столбце указано, критично ли значение А для этого разряда.

Посмотрите на первые две строки. x & 1111 = 0 ложно, x & 100011 = 0 ложно, значит x & A ≠ 0 обязательно должно быть истинно. А наименьший А, для которого произведение 1 и 10 не даст нуля — 11.

11₂ = 3₁₀

Ответ: 3