Домашние задания: Информатика

Помогите решить информатику

Найти наибольшее натуральное А, для которого формула всегда истинна:
(x & 38 = 0) -> ( (x & 49 = 0) -> (x & A = 0) )
Это не информатика
КВ
Кристина Вакутина
43 053
Лучший ответ
Чтобы вся формула всегда была истинна, необходимо, чтобы:
• либо (x & 38 = 0) было ложно,
• либо ( (x & 49 = 0) -> (x & A = 0) ) было истинно.

Чтобы ( (x & 49 = 0) -> (x & A = 0) ) было истинно, необходимо, чтобы:
• либо (x & 49 = 0) было ложно,
• либо (x & A = 0) было истинно.

Таким образом, для истинности всей формулы необходимо соблюсти одно из трех условий:
• либо (x & 38 = 0) ложно,
• либо (x & 49 = 0) ложно,
• либо (x & A = 0) истинно.

Запишем константы в двоичной форме:
38 = 32 + 4 + 2 = 100110
49 = 32 + 16 + 1 = 110001

Выражение (x & A = 0) обязательно должно быть истинным лишь для таких x,
для которых (x & 38 = 0) и (x & 49 = 0) также истинны.
Для этого необходимо, чтобы x не содержал единичных битов чисел 38 и 49.

38 = 100110, единичные биты №№2, 3, 6 (нумерация справа).
49 = 110001, единичные биты №№1, 5, 6.
У переменной x в этих битах должен быть ноль, тогда конъюнкция с 38 и 49 будет равна 0, и первые два условия будут соблюдены.

То есть условие будет соблюдено для x = ####…00#000, где # — любой бит.

Нам нужно подобрать наибольшее A, для которого x & A = 0.

Рассмотрим пример:
x = ####…#00#000
A = 0000…1111111
Для x = 11001000 получим x & A = 1001000.
Биты за решетками привели к ненулевой конъюнкции.

Следовательно, значение A не должно иметь единиц там, где x имеет решетки
(за решеткой может оказаться 1, и тогда конъюнкция будет ≠ 0).

A может иметь единицы лишь там, где x имеет нули, которые загасят единицы: 0 & 1 = 0.
Чтобы получить наибольшее натуральное A, необходимо проставить единицы везде, где только можно:
x = ####…#00#000
A = 0000…0110111 = 32 + 16 + 4 + 2 + 1 = …
Что прямо в пять утра?
Сергей Цимбал
Сергей Цимбал
16 493