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

Преобразуем формулу: \(x\&39 = 0 \lor (x\&42 = 0 \to x\&A \neq 0)\) равносильно \(x\&39 = 0 \lor x\&42 \neq 0 \lor x\&A \neq 0\).

Формула ложна только при \(x\&39 \neq 0\), \(x\&42 = 0\) и \(x\&A = 0\) одновременно. Чтобы этого не случилось ни для какого \(x\), нужно, чтобы при \(x\&39 \neq 0\) и \(x\&42 = 0\) обязательно выполнялось \(x\&A \neq 0\).

Рассмотрим двоичные представления: \(39 = 100111_2\) (биты 0,1,2,5), \(42 = 101010_2\) (биты 1,3,5). Условие \(x\&42 = 0\) запрещает биты 1,3,5. Тогда \(x\&39 \neq 0\) возможно только за счёт битов 0 или 2. Значит, \(x\) может иметь единицы только в битах 0 и 2 (остальные нули). Чтобы для любого такого \(x\) выполнялось \(x\&A \neq 0\), число \(A\) должно содержать единицы в битах 0 и 2. Минимальное такое \(A = 2^0 + 2^2 = 1 + 4 = 5\).

Ответ: 5.

0 0 Пожаловаться