СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 18 № 9369

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4.

Для какого наименьшего неотрицательного целого числа А формула

 

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

 

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение.

Преобразуем выражение по законам алгебры логики:

 

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

 

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.

Имеем импликацию Z17ZA → Z25 или Z(17 or A) → Z25. Запишем число 25 в двоичной системе счисления: 2510 = 110012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 1710 = 100012, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 10002 = 810.

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ—2016 по информатике.