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

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

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

x &A ⁄= 0 → (x&10 = 0 → x&5 ⁄= 0)

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

Преобразуем выражение к виду $Z10Z5 → ZA$ с помощью законов де Моргана:

$(x &A = 0) ∨ (x&10 ⁄= 0) ∨ (x &5 ⁄= 0)$

$(x &10 = 0 ∧ x&5 = 0) → (x &A = 0)$

Заметим, что если $A = 0$ , то последнее выражение всегда $0$ , а следовательно последняя скобка всегда $0$ , то есть выражение имеет вид:

$X → 1$ , а это всегда истинно.

Нам нужно минимальное неотрицательное целое число $A$ , значит наш ответ $0$ .

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

for a in range(1000):
    fl = 0
    for x in range(1000):
        if ((x & a != 0) <= ((x & 10 == 0) <= (x & 5 != 0))) == 0:
            fl = 1
            break
    if not fl:
        print(a)
        break

Ответ: 0