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

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

Для того чтобы формула была тождественно истинной, необходимо чтобы правая часть импликации всегда была истинной, когда левая часть истинна.

Рассмотрим случай, когда x & 49 ≠ 0. Это означает, что в числе x хотя бы один бит равен 1 в позиции, где у числа 49 бит равен 0.

Теперь рассмотрим случай x & 33 = 0. Это означает, что в числе x все биты, где у числа 33 бит равен 1, равны 0. Таким образом, для числа x биты, соответствующие битам числа 49 (равные 0), должны быть равны 1.

Следовательно, минимальное число A, при котором формула будет тождественно истинна, будет равно
49 & A = 0
33 & A ≠ 0.

Последнее означает, что в числе А должен быть хотя бы один бит, который равен 1 и соответствует биту числа 33.

Таким образом, минимальное неотрицательное целое число A, удовлетворяющее этим условиям, будет наименьшим общим делителем чисел 33 и 49, то есть 3.

Итак, минимальным неотрицательным целым числом А будет 3.