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

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

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

((x&47 ⁄= 0 ) ∨ (x&24 ⁄= 0)) → ((x &29 = 0) → (x&A ⁄= 0))

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

Решение руками

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

((x&47 ⁄= 0 ) ∨ (x&24 ⁄= 0)) → ((x &29 = 0) → (x&A ⁄= 0))

Раскроем импликации:

--------------------------- ------------ ((x &47 ⁄= 0 ) ∨ (x&24 ⁄= 0)) ∨ ((x &29 = 0) ∨ (x&A ⁄= 0))

((x &47 = 0 ) ∧ (x&24 = 0)) ∨ ((x &29 ⁄= 0) ∨ (x&A ⁄= 0))

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

(((x&47 = 0) ∧ (x&24 = 0)) ∨ (x &29 ⁄= 0)) ∨ (x&A ⁄= 0)

Сделаем отрицание известной части, чтобы найти те значения $x$ , которые будут давать истину для отрицания.

Тогда они будут обязаны выполняться для условия с $A$ : $(x&A ⁄= 0)$

((x&47 ⁄= 0) ∨ (x &24 ⁄= 0)) ∧ (x&29 = 0)

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

11101 -xxxxx--- xxx0x

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

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

x &24

11000 000x0 --------- 00000

Условие $x&24 ⁄= 0$ не выполнится, так как для уже известных цифр чисел $x$ результат поразрядной конъюнкции будет равен 0.

x &47

101111 x000x0 ---------- x000x0

Условие $x&47 ⁄= 0$ выполнится, если хотя бы одна цифра на месте x будет равна 1. Выпишем числа $x$ , которые дают истину для отрицания известной части: $100000 000010 100010$

Для этих чисел $x$ должно быть истинным условие $(x &A ⁄= 0)$ . Значит, в числе $A$ обязательно должны быть единицы в двоичном виде на разрядах 1 и 5 при нумерации с 0 справа налево. Значит наименьшее число $A$ имеет значение $1000102 = 3410$ . Ответ 34.

Программное решение

for a in range(1000):
    flag = True
    for x in range(10000):
        if (((x & 47 != 0) or (x & 24 != 0)) <= ((x & 29 == 0) <= (x & a != 0))) == False:
            flag = False
            break
    if flag == True:
        print(a)
        break

Ответ: 34