Карточки
Тесты
Главная
Курсы
Подписка
15. Преобразование логических выражений: #292410
Обозначим через $m\mathbin{\&}n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$. Так, например, $$14\mathbin{\&}5=1110_2\mathbin{\&}0101_2=0100_2=4.$$
Для какого наименьшего неотрицательного целого числа $A$ формула $$\bigl((x\mathbin{\&}42\ne0)\land(x\mathbin{\&}34=0)\bigr)\to\neg(x\mathbin{\&}A=0)$$ тождественно истинна (т. е. принимает значение $1$) при любом неотрицательном целом значении переменной $x$?
Запишем числа $42$ и $34$ в двоичной системе счисления:
- $42=101010_2,$
- $34=100010_2.$
Условие $x\mathbin{\&}34=0$ означает, что в двоичной записи числа $x$ на местах единиц числа $34$ должны стоять нули.
Сравним двоичные записи:
- $42=101010_2,$
- $34=100010_2.$
У числа $42$ единицы стоят в разрядах, соответствующих числам $32$, $8$ и $2$. У числа $34$ единицы стоят в разрядах, соответствующих числам $32$ и $2$.
Так как $x\mathbin{\&}34=0,$ число $x$ не может содержать единицы в разрядах $32$ и $2$.
Чтобы при этом выполнялось условие $x\mathbin{\&}42\ne0,$ в числе $x$ обязательно должна стоять единица в разряде $8$.
Следовательно, для каждого подходящего числа $x$ должно выполняться: $$x\mathbin{\&}A\ne0.$$
Для этого число $A$ должно содержать единицу в разряде $8$.
Наименьшее такое неотрицательное целое число: $A=8.$ Наименьшее подходящее значение: $A=8$.
20
