Для какого наименьшего неотрицательного целого числа `A` формула x&49 ≠ 0 → (x&33 = 0 → x&A ≠ 0) тождественно истинна? Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110_2 & 0101_2 = 0100_2=4. Для какого наименьшего неотрицательного целого числа `A` формула x&49 ≠ 0 → (x&33 = 0 → x&A ≠ 0) тождественно истинна (т. е. принимает значение `1` при любом неотрицательном целом значении переменной `x`)? Ответ обосновать.

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

Для того чтобы формула была тождественно истинной, необходимо, чтобы в случае x & 49 ≠ 0 и x & 33 = 0 всегда было верно, что x & A ≠ 0.

Заметим, что 49 = 110001, 33 = 100001 и 4 = 100. Последний бит в числе 49 равен 1, а в числе 33 - 0. Это значит, что если x & 49 ≠ 0 (т.е. x имеет 1 в последнем бите), то x & 33 обязательно равно 0 (т.е. x не имеет 1 в предпоследнем бите).

Таким образом, нам нужно найти такое A, что для любого x, у которого последний бит равен 1, x & A также не равно 0.

Минимальное неотрицательное целое число A, удовлетворяющее этому условию, будет 1, так как для любого x, у которого последний бит равен 1, x & 1 = 1, то есть не равно 0.

Таким образом, искомое наименьшее значение A равно 1.