Задание 15 КЕГЭ: выражение с ДЕЛ истинно для всех x — перебор не лезет по времени, как сузить?

Тут две хитрости: ограничить и A, и x.

По x: проверять все натуральные x не нужно. Условия с ДЕЛ "ломаются" на небольших числах — обычно достаточно прогнать x примерно до 1000 (а часто хватает и до 100). Если для всех x в этом диапазоне выражение истинно, считаем что оно истинно всегда.

По A: перебирай A в разумных пределах (1..1000) и бери первое подходящее.

def P(x, A):
    # пример выражения: (ДЕЛ(x,A) -> ДЕЛ(x,6)) and (ДЕЛ(x,4) -> ДЕЛ(x,A))
    def D(a, b): return a % b == 0
    return (not D(x, A) or D(x, 6)) and (not D(x, 4) or D(x, A))

for A in range(1, 1001):
    if all(P(x, A) for x in range(1, 1001)):
        print(A)
        break

Ключ — переписать импликацию A->B как (not A) or B. Дальше all(...) по диапазону x делает всю работу. break после первого найденного A даёт наименьшее.