Для какого числа А формула x & 49 = 0 → (x & 28 ≠ 0 → x & А ≠ 0) истинна?

Слушайте, когда дело доходит до подготовки к ЕГЭ по информатике, задачки на поразрядную конъюнкцию часто кажутся каким-то дремучим лесом. Вроде и правила понятны, а как начнешь расписывать эти бесконечные иксы, голова идет кругом. Давайте сегодня разберем один конкретный пример, который нет-нет да и всплывает в пробниках. Вопрос звучит типично: Для какого числа А формула x & 49 = 0 → (x & 28 ≠ 0 → x & А ≠ 0) истинна? при любом натуральном xx.

Начнем с того, что разложим всё по полочкам. Нам нужно, чтобы выражение было истинным, то есть равнялось единице, вообще всегда. Чтобы не запутаться в стрелочках, вспомним старую добрую мантру: импликация A→BA \to B — это то же самое, что ¬A∨B\neg A \vee B. Если переписать наше выражение, избавившись от лишних сложностей, мы получим конструкцию, где либо первая часть ложна, либо вторая истинна. Но стоп, у нас же тут вложенная стрелка!

Разбор полетов: Для какого числа А формула x & 49 = 0 → (x & 28 ≠ 0 → x & А ≠ 0) истинна?

Давайте переведем числа в двоичную систему, без этого в таких делах каши не сваришь. Число 49 — это 32+16+132 + 16 + 1, то есть 1100012110001_2. Число 28 — это 16+8+416 + 8 + 4, получаем 11100211100_2.
Суть условия в чем? Если x&49=0x \& 49 = 0, это значит, что у числа xx на позициях, где у 49 стоят единички (это 0-й, 4-й и 5-й биты), обязательно должны быть нули.
Теперь смотрим на скобку: x&28≠0→x&A≠0x \& 28 \neq 0 \to x \& A \neq 0. Если перевести на человеческий язык, это звучит так: «Если в иксе есть хотя бы одна единица из тех, что есть в числе 28, то в нем должна быть хотя бы одна единица из тех, что есть в числе А».

Но подождите, у нас же есть ограничение из первой части! Мы рассматриваем только те xx, у которых на местах 49-ки стоят нули. Значит, 4-й бит (это который «16») у нашего xx автоматически вылетает, он равен нулю. Остаются биты от числа 28 — это 8 и 4 (3-й и 2-й биты). Если хотя бы один из них у xx равен единице, то эта единица обязана «перекрываться» числом А.

Ищем ответ на вопрос: Для какого числа А формула x & 49 = 0 → (x & 28 ≠ 0 → x & А ≠ 0) истинна?

Ой, да тут всё просто, если присмотреться! Чтобы условие выполнялось для любого xx, наше искомое число А должно содержать в себе все те биты, которые могут сделать посылку x&28≠0x \& 28 \neq 0 истинной, но при этом не затронуты условием x&49=0x \& 49 = 0.
Как мы выяснили, из бит числа 28 (16,8,416, 8, 4) бит 16 заблокирован первой частью формулы. Значит, остаются биты 8 и 4. Чтобы выражение гарантированно работало, число А должно «подхватить» эти разряды. Складываем их: 8+4=128 + 4 = 12.

Вот и всё, делов-то! Получается, минимальное А равно 12. Конечно, А может быть и больше, если в нем есть другие биты, но 12 — это тот самый необходимый минимум, который закрывает все дыры в логике. Главное — не паниковать при виде амперсандов и помнить, что двоичная система — наш лучший друг. Надеюсь, теперь этот вопрос не вызовет у вас дрожи в коленках на экзамене!