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


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

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 14&5 = 11102&01012 = 01002 = 4.

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

 

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

 

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

Решение.

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

 

Х → (¬Y → ¬Z) = ¬Х + (¬Y → ¬Z) = ¬Х + Y + ¬Z = Y + ¬(XZ) = XZ → Y.

 

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

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

Тем самым, наименьшее А = 11002 = 1210.