Обозначим через 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 таком, что x&49 ≠ 0, выполнялись два условия:

Если x&49 ≠ 0, то x&33 = 0.Если x&33 = 0, то x&A ≠ 0.

Заметим, что x&33 = 0 тогда и только тогда, когда одновременно выполняются два условия:

x не имеет единицы на 5 значимом разряде (соответствующем третьему биту).x не имеет единицы на 6 значимом разряде (соответствующем четвертому биту).

Так как x&49 ≠ 0, то x должно иметь хотя бы одну единицу на 5 значимом разряде.

Кроме того, так как x&A ≠ 0, x должно иметь хотя бы одну единицу на 6 значимом разряде. Исключим случай, когда x имеет 6 значимый разряд равный 1.

Итак, x должно иметь 5 значимый разряд равный 1, и не должно иметь 6 значимый разряд равный 1. Получаем, что A = 15 (1111_2) - наименьшее возможное число, удовлетворяющее условиям задачи.

Таким образом, наименьшее неотрицательное целое число A, для которого формула x&49 ≠ 0 → (x&33 = 0 → x&A ≠ 0) тождественно истинна, равно 15.