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

Решение аналитически

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

Отделим скобками известную часть выражения от части с :

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

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

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

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

Условие выполнится, если на месте будет стоять 0. Значит в числах обязательно должен быть ноль в 1 и 3 разряде. Тогда, все , которые дают истину для отрицания известной части имеют вид: .

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

Тогда, чтобы найти наибольшее значение , подставим на место x единицы: .

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

Для нахождения наибольшего целого числа , при котором выражение

тождественно истинно для всех неотрицательных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от 1000 вниз до 1. Для каждого перебираем от 0 до 999 и проверяем выполнение логической формулы. Если формула ложна хотя бы для одного , текущее отбрасываем. Если формула истинна для всех , выводим этот как наибольшее подходящее и прекращаем перебор.

# функция проверяет выполнение формулы для конкретного A
def f(a):
    # перебираем все значения x от 0 до 999
    for x in range(1000):
        # проверяем истинность формулы для текущего x и a
        if ((x & a == 0) or ((x & 74 == 0) <= (x & 65 != 0))) == 0:
            return False
    return True

# перебор возможных значений A от 1000 до 1 включительно
for a in range(1000, 0, -1):
    # если формула выполняется для всех x, выводим A и прекращаем перебор
    if f(a):
        print(a)
        break