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

Предыдущий
вопрос Следующий
вопрос

Для начала заметим, что если A нечетное, то (X & A) также будет нечетным для любого X, а значит (X & A ≠ 0) всегда будет ложным выражением. Следовательно, A должно быть четным числом.

Далее заметим, что для любого X выполнено: (X & 14 = 0) → (X & 75 ≠ 0) тогда и только тогда, когда X & 14 = 0 и X & 75 ≠ 0. Рассмотрим битовые записи чисел 14 (1110) и 75 (1001011). Эти числа имеют только один общий бит на позиции, соответствующей двоичному разряду 2^1, т.е. бит 2 (считая справа).

Поэтому нам нужно выбрать такое A, что при поразрядной конъюнкции с этим числом A все числа X, у которых нулевые биты 2 и 3, дают на выходе результат, у которого этот же будет нулевым, а у которых бит 6 будет равен единице. Таким числом A будет число, у которого бит 6 равен 1, а биты 2 и 3 равны 0, т.е. A = 64 + 4 = 68.

Таким образом, наибольшее натуральное число A, удовлетворяющее условию выражения, равно 68.