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

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

Враги хотят чтобы одновременно , , .

Для выполнения первого условия должен иметь вид _ _ _ 0 _ 0 _ _ 0. На месте _ может стоять либо 0, либо 1.

Для выполнения и второго условия должен иметь вид _ _ * 0 * 0 * * 0. На месте хотя бы одной звездочки должна стоять единичка.

Для выполнения третьего условия единиц должно быть как можно меньше, значит должен иметь вид 0 0 * 0 * 0 * * 0. На месте только одной звездочки должна стоять единица.

Тогда друзья подберут такое минимальное чтобы . Друзьям достаточно подставить единички в тех местах где они могут появиться в . Итоговое .

 

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

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

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

# функция проверяет выполнение выражения для конкретного x и A
def f(a):
    # перебираем x от 1 до 999 и проверяем тождественную истинность выражения
    for x in range(1, 1000):
        if ((x & 41 == 0) <= ((x & 119 != 0) <= (x & a != 0))) == 0:
            return False
    return True

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

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

Враги хотят чтобы одновременно , , .

Для выполнения первого условия должен иметь вид _ _ _ _ 0 0 _ 0. На месте _ может стоять 1 или 0.

Для выполнения и второго условия должен иметь вид _ _ 0 _ 0 0 0 0.

Для выполнения третьего условия единиц в должно быть как можно больше. Тогда он имеет вид ...1 1 0 1 0 0 0 0.

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

 

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

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

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

# функция проверяет выполнение выражения для конкретного x и A
def f(a):
    # перебираем x от 1 до 999 и проверяем тождественную истинность выражения
    for x in range(1, 1000):
        if ((((x & 13 != 0) or (x & 39 == 0)) <= (x & 13 != 0)) or ((x & a == 0) and (x & 13 == 0))) == 0:
            return False
    return True

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

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

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

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    # возвращает True, если выражение тождественно истинно для данного x
    return (x & 25 != 0) <= ((x & 17 == 0) <= (x & A != 0))

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

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

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

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    # возвращает True, если выражение тождественно истинно для данного x
    return ((x & 28 != 0) or (x & 45 != 0)) <= ((x & 48 == 0) <= (x & A != 0))

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

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

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

# функция проверяет выполнение выражения для конкретного x и a
def f(a):
    # возвращает True, если выражение тождественно истинно для данного x
    for x in range(1, 1000):
        if ((x & 144 == 0) <= ((x & 220 != 0) <= (x & a != 0))) == 0:
            return False
    return True

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

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

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

# перебор возможных значений A от 10 до 50 включительно
for A in range(10, 50+1):
    # флаг: True - выражение ложно для всех x, False - хотя бы один случай нарушает
    flag = True
    # проверяем выражение для всех x от 0 до 99999
    for x in range(100000):
        f = (((x & 56 != 0) <= (x & 18 != 0)) or (x & A != 0)) <= (
            (x & 18 == 0) and (x & A == 0) and (x & 43 != 0))
        # если выражение оказалось истинным хотя бы для одного x
        if f == 1:
            flag = False
            break
    # если выражение ложно для всех x, обновляем максимальное значение A
    if flag:
        maxim = A

# выводим наибольшее подходящее A
print(maxim)

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

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

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

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

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

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

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

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

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

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

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

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

# функция проверяет выполнение выражения для конкретного a и всех x
def f(a):
    for x in range(1, 1000):
        # если выражение ложно для текущего x, возвращаем False
        if ((x & 27 != 0) <= ((x & 83 == 0) <= (x & a != 0))) == 0:
            return False
    # если для всех x выражение истинно, возвращаем True
    return True

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

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

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

# функция проверяет выполнение выражения для конкретного a и всех x
def f(a):
    for x in range(1, 1000):
        # если выражение ложно для текущего x, возвращаем False
        if ((x & 125 != 1) or ((x & 34 == 2) <= (x & a == 0))) == 0:
            return False
    # если для всех x выражение истинно, возвращаем True
    return True

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

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

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

# функция проверяет выполнение выражения для конкретного x и A
def f(x, a):
    # возвращает True, если выражение истинно для данного x и A
    return ((x & a == 0) and (x & 58 != 0) and (x & 22 == 0))

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # если для всех x от 1 до 99 выражение ложно, выводим A и прекращаем поиск
    if all(f(x, a) == False for x in range(1, 100)):
        print(a)
        break

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

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

# перебор возможных значений A от 999 до 2 включительно
for A in range(1000, 1, -1):
    # флаг: True - выражение ложно для всех x, False - хотя бы один случай нарушает
    p = True
    # проверяем выражение для всех x от 1 до 999
    for x in range(1, 1000):
        f = (x & A != 0) and (x & 48 == 0) and (x & 27 == 0)
        # если выражение оказалось истинным хотя бы для одного x
        if f == True:
            p = False
            break
    # если выражение ложно для всех x, выводим текущее A и прекращаем перебор
    if p == True:
        print(A)
        break

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

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

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

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

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

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

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

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

Программное решение

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

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

# перебор возможных значений A от 0 до 999 включительно
for a in range(1000):
    # флаг: True - выражение выполняется для всех x, False - хотя бы один случай нарушает
    flag = True
    # проверяем выражение для всех x от 0 до 9999
    for x in range(10000):
        # проверка выполнения формулы для конкретного x и a
        if ((x & 38 == 0) <= ((x & 55 != 0) <= (x & a != 0))) == False:
            flag = False
            break
    # если выражение выполняется для всех x, выводим текущее a и прекращаем перебор
    if flag == True:
        print(a)
        break

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значит для истинности отрицания числа должны в двоичном виде принимать вид , где 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

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

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

Раскроем отрицания:

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

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

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

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

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

Условие выполнится, если цифра a будет равна 0. Значит двоичная запись чисел , которые делают отрицание истинным, имеет следующий вид: , где x - любая цифра. Чтобы условие условие было истинным нужно, чтобы двоичная запись числа имела вид . Тогда при поразрядной конъюнкции с любым числом в результате будет 0. Значит наибольшее число имеет значение . Ответ .

Программное решение

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

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

# переменная для хранения наибольшего подходящего A
ans = 0

# перебор возможных значений A от 0 до 999
for a in range(1000):
    # флаг: True - формула выполняется для всех x, False - хотя бы один случай нарушает
    flag = True
    # перебор всех значений x от 0 до 9999
    for x in range(10000):
        # проверка истинности формулы для текущего x и a
        if ((not (x & a != 0)) or (not (x & 122 == 0)) or (x & 144 != 0)) == False:
            flag = False
            break
    # если формула выполняется для всех x, обновляем максимум
    if flag == True:
        ans = max(ans, a)

# выводим наибольшее подходящее A
print(ans)

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

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

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

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

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

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

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

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

# функция проверяет выполнение формулы для конкретного x и a
def f(a):
    # если отрицание формулы возвращает истину,
    # то сама формула возвращает ложь
    for x in range(1000):
        if not((x & 85 == 0) <= ((x & 54 != 0) <= (x & a != 0))):
            return False
    return True

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

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

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

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

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

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

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

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

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

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

Значит для истинности отрицания числа должны в двоичном виде принимать вид , где 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

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

Преобразуем выражение по законам алгебры логики:

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

Итак, импликация должна быть тождественно истиной. Запишем число 10 в двоичной системе счисления:

Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут и не быть) только первый и третий биты (считая справа налево, начиная с нуля). Поскольку искомое А – наибольшее натуральное число, все биты, которые могут быть единичными будут единичными.

Тем самым, наибольшее .

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

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

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

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # флаг: True - формула выполняется для всех X, False - хотя бы один X нарушает
    flag = True
    for x in range(1, 1000):
        # проверка истинности формулы для текущего X и A
        if ((x & 10 != 0) or (x & 39 == 0) or (x & a == 0)) == False:
            flag = False
            break
    # если формула выполняется для всех X, выводим A
    if flag:
        print(a)

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

Упростим выражение, раскрыв импликацию:

Преобразуем выражение по законам алгебры логики:

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

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

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

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

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # флаг: True - формула выполняется для всех X, False - хотя бы один X нарушает
    flag = True
    for x in range(1, 1000):
        # проверка истинности формулы для текущего X и A
        if (((x & 13 != 0) or (x & 13 == 0)) <= ((x & a != 0) or (x & 39 == 0))) == False:
            flag = False
            break
    # если формула выполняется для всех X, выводим наименьшее подходящее A и прерываем цикл
    if flag:
        print(a)
        break