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

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

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

Для какого наибольшего неотрицательного целого числа $A$ формула $((x&23 = 0) ∨ (x&17 = 0)) → ((x&58 ⁄= 0) → (x&A = 0 ))$ тождественно истинна (т.е. принимает значение $1$ при любом неотрицательном целом значении переменной $x$ )?

Введем обозначение: $x&a = 0 ⇔ ZA.$ Тогда наше выражение имеет вид: $---- (Z23 ∨ Z17) → (Z58 → ZA ).$

Так как $a → b = a-∨ b,$ получаем $(Z23 ∨ Z17) → (Z58 ∨ ZA ).$ Так как $Z23 ∨ Z17 = Z23&17.$

$23 = 101112,17 = 100012.$ Тогда посчитаем $23&17 :$

10111; -10001;-- 10001

$100012 = 1710.$

Тогда наше выражение имеет вид $Z → (Z ∨ Z ). 17 58 A$ Это то же самое, что $(Z → Z ) ∨ (Z → Z ). 17 58 17 A$

Мы сразу можем определить, истинна ли $Z17 → Z58.$

$17 = 010001 58 = 111010$

Нет, не истинна, т.к. на первом месте, например, в двоичной записи 17 стоит 0, а на первом в двоичной записи 58 — 1. Значит, нужно, чтобы истинна была импликация $Z17 → ZA.$

Мы ищем наибольшее $A.$ Чтобы импликация истинна, на тех местах, где в двоичной записи A стоят единицы, стоят единицы и в двоичной записи 17. То есть больше единиц, чем есть в 17, в записи $A$ быть не может. Тогда наибольшее $A$ — это и есть само 17.

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

for a in range(1,1000):
    flag = True
    for x in range(10000):
        if (((x & 23 == 0) or (x & 17 == 0)) <= ((x & 58 != 0) <= (x & a == 0))) == False:
            flag = False
            break
    if flag == True:
        print(a)

Ответ: 17