Задача к ЕГЭ по информатике на тему «побитовая конъюнкция» №3

Просмотров 13 Комментарии 0

Введём выражение $M &K$ , обозначающее поразрядную конъюнкцию $M$ и $K$ (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число $a$ , такое что выражение

(x &27 ⁄= 0) → ((x&83 = 0) → (x&a ⁄= 0))

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

Решение аналитически

Для начала упростим данное выражение:

---------- ---------- (x&27 ⁄= 0)∨ ((x&83 = 0)∨(x&a ⁄= 0))

(x&27 = 0)∨ (x&83 ⁄= 0)∨(x&a ⁄= 0)

Отделим скобками известную часть выражения от части с $A$ :

((x&27 = 0)∨ (x&83 ⁄= 0))∨ (x&a ⁄= 0)

Сделаем отрицание известной части, чтобы найти те значения $x$ , которые будут давать истину для отрицания. Тогда они будут обязаны выполняться для условия с $A$ : $((x&a ⁄= 0)$

(x&27 ⁄= 0) ∧(x&83 = 0)

Выпишем поразрядную конъюнкцию $(x&83 = 0)$ :

1010011 xxxxxxx ---------- x0x00xx

Значит для истинности отрицания числа $x$ должны в двоичном виде принимать вид $...0x0xx00$ , где x – любая цифра.

Теперь выпишем поразрядную конъюнкцию $(x &27 ⁄= 0)$ с учётом известных цифр в числах $x$ :

11011 0x0xx00 ----------- ...000b000

Условие $(x&27 ⁄= 0)$ выполнится, если хотя бы одна цифра на месте $b$ будет равна 1. Значит в числах $x$ обязательно должна быть единица в 3 разряде. Выпишем числа $x$ , которые дают истину для отрицания известной части: $1000$ .

Для всех таких чисел $x$ должно быть истинным условие $(x&a ⁄= 0)$ . Значит, двоичная запись числа $a$ обязательно должна иметь вид $...xx1xxx$ , чтобы при поразрядной конъюнкции с любым числом $x$ получался в результате хотя бы один разряд 1. Значит наименьшее число $a$ имеет значение $10002 = 810$ . Ответ $8$ .

Решение программой

def f(a):
    for x in range(1, 1000):
        if ((x & 27 != 0) <= ((x & 83 == 0) <= (x & a != 0))) == 0:
            return False
    return True

for a in range(1, 1000):
    if f(a):
        print(a)
        break

Ответ: 8