Логические выражения с параметром A

Что проверяет номер

Дана логическая формула с неизвестным A. Это может быть число, отрезок или множество. Надо найти такое A, при котором формула истинна для всех x. Именно это значат слова «тождественно истинна».

Основной способ это код: перебираем A и проверяем формулу на большом диапазоне x. Руками проверяем себя в конце урока.

Формула в Python и общий шаблон

Импликация записывается через <=, потому что True <= False это False, а все остальные сочетания дают True. Как раз так работает импликация: ложна она только тогда, когда из истины следует ложь.

Вот что будет без скобок. Формула A → (B ∧ C) при A = 0 истинна, а запись без скобок даёт другое:

print(False <= True and False)     # Python считает (False <= True) and False
print(False <= (True and False))   # а так как надо

Общий шаблон

Описываем формулу функцией f, перебираем A и проверяем, что f истинна для всех x. Функция all(...) истинна, когда истинна каждая проверка внутри.

def d(n, m):
    return n % m == 0                 # n делится на m

def f(x, A):
    return d(x, 128) <= ((not d(x, A)) <= (not d(x, 80)))

print(max(A for A in range(1, 1000) if all(f(x, A) for x in range(1, 2000))))

Ответ 640. Если нужно наименьшее значение, max меняем на min. Диапазон x берём с запасом: range(1, 2000) для обычных чисел, range(0, 4000) для поразрядных.

ДЕЛ: делимость

ДЕЛ(n, m) значит «n делится на m без остатка». Пишем функцию d, а дальше формулу из условия. Пример с наибольшим A был в прошлом разделе, вот пример с наименьшим:

def d(n, m):
    return n % m == 0

def f(x, A):
    return d(x, A) <= (d(x, 18) or (not d(x, 24)))

print(min(A for A in range(1, 200) if all(f(x, A) for x in range(1, 2000))))

Поразрядная конъюнкция

x & 52 это поразрядное И: единица стоит только в тех разрядах, где она есть у обоих чисел. Сравнение с нулём пишется без скобок вокруг x & 52, потому что & в Python выполняется раньше, чем != и ==.

def f(x, A):
    return ((x & 52 != 0) and (x & 48 == 0)) <= (not (x & A == 0))

print(min(A for A in range(1, 2000) if all(f(x, A) for x in range(0, 4000))))

В условии обычно написано x & A ≠ 0, поэтому not (x & A == 0) можно записать и как x & A != 0.

Неравенства с двумя переменными

Тут внутри all два перебора: по x и по y.

def f(x, y, A):
    return (x + 2 * y != 58) or (A > 2 * x) or (A > y)

print(min(A for A in range(1, 200)
          if all(f(x, y, A) for x in range(1, 500) for y in range(1, 500))))

Такой код уже работает пару секунд. Если он упирается в лимит времени, подбери диапазоны меньше, но так, чтобы опасные значения в них попадали. В примере важны только пары, где x + 2y = 58, значит x и y не больше 58.

Отрезки

Тут A это отрезок [a1; a2], а спрашивают его длину. Проверять все x не нужно. Значение формулы меняется только у концов отрезков, поэтому берём опасные точки: концы отрезков из условия и точки чуть левее и правее. Концы A ищем среди них же.

def f(x):
    P = 15 <= x <= 40
    Q = 30 <= x <= 65
    A = a1 <= x <= a2
    return P <= ((Q and (not A)) <= (not P))

d = [y for x in (15, 30, 40, 65) for y in (x, x - 0.1, x + 0.1)]
n = []
for a1 in d:
    for a2 in d:
        if a2 >= a1 and all(f(x) for x in d):
            n.append(a2 - a1)
print(round(min(n)))

Здесь a1 и a2 внутри f берутся из цикла снаружи. round нужен, потому что из-за 0.1 длина получается с хвостиком.

• Нужна наибольшая длина: min меняем на max.
• Формула должна быть ложной при любом x: проверяем f(x) == 0 вместо f(x), то есть all(f(x) == 0 for x in d).

Множества

Тут A это множество чисел. Начинаем с пустого и идём по всем x. Если формула ложна, значит этот x обязан быть в A, и мы его добавляем.

a = set()

def f(a):
    P = x in {2, 4, 6, 8, 10, 12}
    Q = x in {4, 5, 6, 7, 8}
    A = x in a
    return (P <= (not Q)) or A

for x in range(1, 100):
    if f(a) == 0:                  # формула ложна
        a.add(x)                   # значит, x обязан быть в A
print(sorted(a))
print(sum(a))

Тут x внутри f тоже берётся из цикла снаружи. Если множество нужно не наименьшее, а наибольшее, стартуем с a = set(range(1, 100)) и убираем лишнее через a.remove(x).

Проверяем руками

Код даёт ответ, а руками удобно проверить, что формула записана верно. Порядок такой:

1. С частью без A находим значения x и y.
2. Часть без A делаем ложной.
3. Делаем выводы и пишем ответ.

Для неравенств и ДЕЛ правило короткое: отрицаем условия и решаем.

Законы

• A → B = ¬A ∨ B
• ¬(A ∨ B) = ¬A ∧ ¬B
• ¬(A ∧ B) = ¬A ∨ ¬B
• ¬¬A = A

ДЕЛ руками

Разберём формулу ДЕЛ(x, 128) → (¬ДЕЛ(x, A) → ¬ДЕЛ(x, 80)). Для краткости будем писать только числа.

1. Записываем: 128 → (¬A → ¬80).
2. Упрощаем: ¬128 ∨ A ∨ ¬80, то есть ¬128 ∨ ¬80 ∨ A.
3. Сворачиваем обратно: (128 ∧ 80) → A.

Значит, если x делится на 128 и на 80, то он делится на A. Такие x это числа, кратные 640, поэтому A должно быть делителем 640. Наибольшее A равно 640, как и в коде.

Отрезки и множества руками

Формула P → ((Q ∧ ¬A) → ¬P) по тем же законам равна (P ∧ Q) → A. Значит, A должен накрыть общую часть P и Q, и наименьшая длина это длина пересечения.

С множествами так же. Формула (P → ¬Q) ∨ A требует, чтобы A содержало пересечение P и Q. Напомним: объединение это всё, что есть хотя бы в одном множестве, а пересечение это общая часть.