Сверь числа и знаки с фото.
Обозначим через \(m \& n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n\). Так, например, \(12 \& 6 = 1100_2 \& 0110_2 = 0100_2 = 4\). Для какого наименьшего неотрицательного целого числа \(A\) формула \((x \& 41 \ne 0) \to ((x \& 9 = 0) \to (x \& A \ne 0))\) тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной \(x\))? В ответе запишите найденное число \(A\).
Краткий ответ: \(A = 32\).
Разбор
Переведём числа в двоичную систему: \[ 41 = 101001_2,\qquad 9 = 001001_2. \] Если нумеровать биты с нуля, у числа 41 единицы в позициях 5, 3 и 0, а у числа 9 — в позициях 3 и 0.
Условие \(x \& 41 \ne 0\) означает, что в \(x\) есть хотя бы один из битов 5, 3 или 0. Условие \(x \& 9 = 0\) запрещает биты 3 и 0. Значит, если выполнены оба условия, у \(x\) обязательно установлен бит 5.
Импликация \(U \to (V \to W)\) ложна только тогда, когда \(U\) и \(V\) истинны, а \(W\) ложно. Поэтому при \(x \& 41 \ne 0\) и \(x \& 9 = 0\) должно обязательно выполняться \(x \& A \ne 0\).
Чтобы это работало для всех \(x\), число \(A\) должно содержать бит 5. Иначе возьмём \(x=32\): тогда \(32 \& 41 \ne 0\), \(32 \& 9 = 0\), но \(32 \& A = 0\), и формула становится ложной.
Минимальное неотрицательное число с установленным битом 5 — это \(2^5 = 32\). Остальные биты в \(A\) добавлять не нужно: они только увеличивают число.
Проверка. При \(A=32\), если \(x \& 41 \ne 0\) и \(x \& 9=0\), то у \(x\) есть бит 5, поэтому \(x \& 32 \ne 0\). Значит, формула истинна при любом неотрицательном \(x\).
Ответ: 32.