15.04 Побитовая конъюнкция

Обозначим Перепишем: для любых

Воспользуемся тем, что Тогда Теперь воспользуемся тем же в обратную сторону: соберем импликацию. Получим

Помним, что Тогда

Переведем в двоичную систему счисления известные числа: 17 = 10001, 25 = 11001.

\(\)

r _& 10001;
;

\(\)

Известно, что, чтобы данная импликация была равна 1, на тех местах, где в двоичной записи 25 стоят единички, в двоичной записи должны тоже стоять единички.

Мы ищем наименьшее неотрицательное целое число Значит, где вместо звездочек можно ставить нули, — будем ставить. Двигаемся справа налево. На место первой звездочки можно поставить 0 — единичка уже есть в записи числа 17. На втором месте все равно, что ставить, — в записи 25 на этом месте 0. Ставим 0. Аналогично ставим на третье место. Теперь посмотрим на четвертое: в записи 25 — стоит 1, а вот в записи 17 — 0. Значит, на четвертом месте в числе должна быть единичка. Аналогично заканчиваем ставить знаки. Никаких лишних разрядов впереди числа добавлять не будем — мы ищем наименьшее.

Итак, получили 1000. Это число в двоичной системе счисления. В десятичной — 8.