15.04 Побитовая конъюнкция

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

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

, а это всегда истинно.

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

Идея решения:

Перебираем целые неотрицательные с помощью цикла for, начиная с малых значений, чтобы найти наименьшее. Для каждого проверяем тождественную истинность

для всех неотрицательных , используя вложенный цикл for. Для проверки поразрядной конъюнкции применяем оператор &. Если найдётся хотя бы одно , при котором формула ложна, сбрасываем цикл и текущее не подходит. Первое , для которого формула истинна для всех , будет искомым наименьшим.

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

# Перебор возможных значений A
for a in range(1000):
    # Флаг для проверки, подходит ли текущее A
    fl = 0
    # Перебор всех неотрицательных x
    for x in range(1000):
        # Проверка формулы с использованием поразрядной конъюнкции
        if ((x & a != 0) <= ((x & 10 == 0) <= (x & 5 != 0))) == 0:
            # Сбрасываем цикл, данное A не подходит
            fl = 1
            break
    # Если A подходит для всех x, выводим его и прекращаем поиск
    if not fl:
        print(a)
        break