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