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

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

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

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

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

Тогда они будут обязаны выполняться для условия с :

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

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

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

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

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

После объединения чисел из предыдущего пункта получаем весь список которые дают истину отрицания известной части: .

Для этих чисел должно быть истинным условие . Значит, в числе обязательно должны быть нули в двоичном виде на разрядах 0, 2 и 5 при нумерации с 0 справа налево. Так как число натурально, то все нули в нем стоять не могут, поэтому поставим 1 на самый правый доступный разряд. Значит наименьшее число имеет значение . Ответ 2.  

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

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

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

# функция проверяет выполнение формулы для конкретного x и A
def f(x, a):
    return ((x & 35 != 0) or (x & 23 != 0)) <= ((x & 26 != 0) or (x & a == 0))

# перебор возможных значений A от 1 до 299
for a in range(1, 300):
    # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    p = True
    for x in range(0, 300):
        # проверка истинности формулы для текущего x и A
        if f(x, a) == False:
            p = False
            break
    # если формула выполняется для всех x, выводим A и прекращаем поиск
    if p == True:
        print(a)
        break