Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)
Для какого наименьшего неотрицательного целого числа \(A\) формула \((x\&25 \neq 0) \to ((x\&17 = 0) \to (x\&A \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?
Обозначим \(x\&25 = 0 \Leftrightarrow Z_{25}, \; x\&17 = 0 \Leftrightarrow Z_{17}, \; x\&A = 0 \Leftrightarrow Z_{A}.\) Перепишем: \(\overline{Z_{25}} \to (Z_{17} \to \overline{Z_{A}}) = 1\) для любых \(x.\)
Воспользуемся тем, что \(a \to b = \overline{a} \vee b, \; \overline{\overline{a}} = a.\) Тогда \(Z_{25} \vee \overline{Z_{17}} \vee \overline{Z_{A}} = 1.\) Теперь воспользуемся тем же в обратную сторону: соберем импликацию. Получим \((Z_{17} \wedge Z_{A}) \to Z_{25} = 1.\)
Помним, что \(Z_{17} \wedge Z_{A} = Z_{17 \; or \; A}.\) Тогда \(Z_{17 \; or\; A} \to Z_{25} = 1.\)
Переведем в двоичную систему счисления известные числа: 17 = 10001, 25 = 11001.
\(\)
r _& 10001;
\(*****\);
\(11001\)
\(\)
Известно, что, чтобы данная импликация была равна 1, на тех местах, где в двоичной записи 25 стоят единички, в двоичной записи \(Z_{17 \; or \; A}\) должны тоже стоять единички.
Мы ищем наименьшее неотрицательное целое число \(A.\) Значит, где вместо звездочек можно ставить нули, — будем ставить. Двигаемся справа налево. На место первой звездочки можно поставить 0 — единичка уже есть в записи числа 17. На втором месте все равно, что ставить, — в записи 25 на этом месте 0. Ставим 0. Аналогично ставим на третье место. Теперь посмотрим на четвертое: в записи 25 — стоит 1, а вот в записи 17 — 0. Значит, на четвертом месте в числе \(A\) должна быть единичка. Аналогично заканчиваем ставить знаки. Никаких лишних разрядов впереди числа добавлять не будем — мы ищем наименьшее.
Итак, получили 1000. Это число в двоичной системе счисления. В десятичной — 8.
Ответ: 8