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

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

Введем обозначение: Тогда данное выражение перепишется в виде

Воспользуемся тем, что Тогда наше выражение имеет вид

Теперь воспользуемся тем же, только в обратную сторону. Запишем выражение так:

Помним, что Значит, нам нужно найти наибольшее неотрицательное целое такое, что

мы можем сразу вычислить. Так как можем выполнить поразрядное сложение:

Чтобы импликация была истинна, нам нужно, чтобы на тех местах, где справа стоит единица (в двоичной записи числа), слева она стояла тоже.

Таким образом, единица может стоять на тех местах, где она стоит в двоичной записи числа слева — необязательно, но если где-то и стоит, то только там. Но вспомним, что мы ищем максимальное : значит, мы хотим, чтобы в было как можно больше единиц. А так как единицы могут быть только на тех местах, где стоят единицы в наибольшее возможное — это и есть

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

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

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

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

# Перебор возможных значений A с помощью цикла for (по убыванию)
for a in range(1000, 1, -1):
    # Флаг для отслеживания ложных выражений
    flag = True

    # Перебор неотрицательных целых x с помощью вложенного цикла for
    for x in range(10000):
        # Проверяем тождественную истинность формулы с операцией & для поразрядной конъюнкции
        if ((x & a != 0) <= ((x & 11 == 0) <= (x & 17 != 0))) == False:
            # Если выражение ложно для текущего x
            flag = False
            break

    # Если ложных выражений не было, выводим наибольшее A
    if flag == True:
        print(a)
        break