Законы математической логики

В задании 15 дана логическая формула с неизвестным числом A. Нужно найти A, при котором формула истинна при любом x. Вот задача, которую мы будем решать всю тему:

«Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула ДЕЛ(x, A) ∨ ((x ∈ [50; 70]) → ¬ДЕЛ(x, 15)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?»

Перебирать все x вручную не нужно: почти при любом x формула истинна и без A. Достаточно найти те немногие x, при которых всё решает A. Сначала разберём, что сказано в условии:

Тема состоит из шести подтем — у каждой своя страница. Идём по ним по порядку:

1. Формула с параметром A — ты сейчас здесь. Здесь же решим задачу темы: ответ 60.
2. Отрезки и множества — A не число, а отрезок или набор чисел.
3. Координатная плоскость — две переменные x и y; самый частый вид задачи.
4. Делимость — ДЕЛ и общие кратные, как в задаче темы.
5. Поразрядная конъюнкция — операция & над двоичными записями.
6. Треугольник, MAX и условия с A — дополнительный урок для редких задач.

Почти любую задачу можно решить и вручную, и программой. На экзамене подойдёт любой способ, а второй пригодится для проверки.

Как узнать, истинна ли формула при конкретном x?

При конкретном x каждое условие либо истинно, либо ложно. Истину записывают 1, ложь — 0, а логические операции соединяют эти 0 и 1 в значение всей формулы. Возьмём x = 55: условие x ∈ [50; 70] истинно — 1, а ДЕЛ(55, 15) ложно — 0, ведь 55 на 15 не делится.

С ¬, ∧ и ∨ всё как в обычной речи. На стрелке → ошибаются чаще всего — разберём её отдельно.

Когда ложна формула «если p, то q»?

Импликация p → q ложна только в одном случае: p истинно, а q ложно. Во всех остальных случаях она истинна. Это как обещание «если сдашь экзамен, получишь подарок». Оно нарушено, только если экзамен сдан, а подарка нет. Если экзамен не сдан, обещание не нарушено — будет подарок или нет.

Отсюда удобная замена: p → q — то же самое, что ¬p ∨ q. Обе формулы ложны только при p = 1 и q = 0. Заменим так стрелку в задаче темы:

(x ∈ [50; 70]) → ¬ДЕЛ(x, 15) = ¬(x ∈ [50; 70]) ∨ ¬ДЕЛ(x, 15).

Теперь вся формула задачи — три части, соединённые через ИЛИ: ДЕЛ(x, A) ∨ ¬(x ∈ [50; 70]) ∨ ¬ДЕЛ(x, 15).

Как найти A, не проверяя все x подряд?

Формула из частей через ИЛИ истинна, если истинна хоть одна часть. Поэтому A влияет на ответ только при тех x, где все части без A ложны: там часть с A обязана быть истинной.

В задаче темы части без A — ¬(x ∈ [50; 70]) и ¬ДЕЛ(x, 15). Обе ложны, когда x лежит на отрезке и делится на 15. Такое x одно — 60: соседние кратные 45 и 75 лежат вне отрезка.

Значит, A должно быть делителем 60. Самый большой делитель 60 — само 60. Ответ задачи темы — 60.

Проверим. При A = 60 формула истинна при x = 60, а при всех остальных x её делают истинной части без A. А любое A больше 60 не делит 60 — при x = 60 формула ложна.

Как получить тот же ответ программой?

Программа делает то, что написано в условии: для каждого кандидата A проверяет формулу при всех x из большого диапазона и запоминает подходящие A. Сначала формулу переводят на Python — каждому знаку соответствует своя запись:

Для стрелки готового знака нет, поэтому заведём функцию imp(p, q) — она возвращает ¬p ∨ q. Формулу задачи запишем функцией f(x, A):

def imp(p, q):    return (not p) or q  def f(x, A):    return x % A == 0 or imp(50 <= x <= 70, x % 15 != 0)

Теперь переберём кандидатов A и для каждого проверим все x:

answer = 0for A in range(1, 1000):    if all(f(x, A) for x in range(1, 1000)):        answer = Aprint(answer)

all(...) истинно, только если f(x, A) истинна при каждом x от 1 до 999. Кандидаты A идут по возрастанию, поэтому последнее запомненное A — наибольшее.

Почему x до 999 хватает? Вне отрезка [50; 70] формула истинна сама — все x, где решает A, лежат внутри диапазона. Диапазон берут с запасом, чтобы он накрыл все числа условия.

for A in range(1, 1000):    if all(f(x, A) for x in range(1, 1000)):        print(A)        break

• Формула при xкаждое условие — 1 или 0
• p → qложна только при 1 → 0; это ¬p ∨ q
• Части через ИЛИистинна, если истинна хоть одна часть
• Когда решает Aвсе части без A ложны — часть с A обязана быть 1
• Задача темырешает только x = 60 → A делит 60 → 60
• Pythonimp, f(x, A), all(...) по всем x