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

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

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

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

Теперь воспользуемся свойством :

Получим:

Аналогично применим предыдущее свойство:

В итоге выражение упростится до следующего вида:

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

Выпишем поразрядную конъюнкцию :

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

Теперь выпишем поразрядную конъюнкцию с учётом известных цифр в числах :

Условие выполнится, если хотя бы одна цифра на месте x будет равна 1. Выпишем числа , которые дают истину для отрицания известной части: Для всех таких чисел должно быть истинным условие . Значит, двоичная запись числа обязательно должна иметь вид , чтобы обнулить все разряды, где могут быть 1 Значит наибольшее число имеет значение . Ответ 24.

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

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

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

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

# Перебор возможных значений A с помощью цикла for
ans = 0
for a in range(1000):
    # Флаг для отслеживания ложных выражений
    flag = True
    # Перебор неотрицательных целых x с помощью вложенного цикла for
    for x in range(10000):
        # Проверяем тождественную истинность формулы с операцией & для поразрядной конъюнкции
        if (((x & 24 != 0) or (x & a != 0)) <= ((x & 24 != 0) or ((x & a != 0) and (x & 47 == 0)))) == False:
            # Если выражение ложно для текущего x
            flag = False
            break
    # Если ложных выражений не было, обновляем наибольшее значение A
    if flag == True:
        ans = max(ans, a)
print(ans)