Задание 15: множества, отрезки, ДЕЛ

Учимся подбирать параметр A в выражениях с отрезками и делимостью так, чтобы условие было истинным для каждого целого x.

ДЕЛ(n, k) — предикат «n делится на k нацело». Задание 15 просит найти числовой параметр (часто отрезок [A; B] или число A), при котором заданная логическая формула с переменной x истинна на всём множестве целых чисел.

Формула задания 15 обычно выглядит как импликация, где условие и заключение — это принадлежность $x$ отрезкам или делимость. Пример:

$$\big(\text{ДЕЛ}(x, 6) \big) \Rightarrow \big( (x \le A) \lor \text{ДЕЛ}(x, 9) \big),$$

и нужно найти, например, наибольшее $A$, при котором это истинно для любого натурального $x$. Здесь сходятся две темы курса: множества (как отрезки на прямой) и логика (импликация). Ключ — переписать «истинно для всех x» как условие на множества.

Зачем это нужно

Задача проверяет, умеете ли вы переводить логику в язык множеств и обратно — навык, важный в базах данных (условие выборки = множество строк), в проектировании прав доступа и в любой фильтрации. Само задание дорогое и требует аккуратности: одна ошибка в границе отрезка или в направлении импликации убивает решение.

Главная идея: импликация как вложение множеств

Пусть $P(x)$ — условие (посылка), $Q(x)$ — заключение. Импликация $P(x) \Rightarrow Q(x)$ истинна для всех $x$ тогда и только тогда, когда множество, где истинно $P$, целиком лежит внутри множества, где истинно $Q$:

$$\forall x\, \big(P(x) \Rightarrow Q(x)\big) = 1 \iff \{x : P(x)\} \subseteq \{x : Q(x)\}.$$

Словами: «везде, где выполнена посылка, обязано выполняться и заключение». Если есть хоть один $x$, где $P$ истинно, а $Q$ ложно — импликация на нём ложна, и всё условие рушится. Поэтому задача сводится к геометрии множеств на числовой прямой.

Разбор 1: отрезки

Найдём наибольшее целое $A$, при котором для всех $x$ истинно

$$\big( x \in [10; 30] \big) \Rightarrow \big( x \in [A; 40] \big).$$

По правилу вложения нужно, чтобы отрезок посылки $[10; 30]$ целиком лежал в отрезке заключения $[A; 40]$. Правый конец в порядке: $30 \le 40$. Левый: чтобы $10$ попало в $[A; 40]$, нужно $A \le 10$. Наибольшее такое целое — $A = 10$. Проверка: при $A=10$ заключение $[10;40]$ полностью накрывает $[10;30]$ ✓. При $A=11$ точка $x=10$ удовлетворяет посылке, но не лежит в $[11;40]$ — импликация на ней ложна. Ответ: $A = 10$.

Разбор 2: делимость и «прокол» отрезка

Теперь с предикатом ДЕЛ. Найдём наименьшее $A$, при котором для всех натуральных $x$ истинно

$$\big( \text{ДЕЛ}(x, 12) \big) \Rightarrow \big( (x \ge A) \lor \neg\,\text{ДЕЛ}(x, 8) \big).$$

Посылка истинна на числах, кратных 12: $12, 24, 36, 48, \ldots$. Для каждого такого $x$ должно выполняться заключение $(x \ge A) \lor \neg\text{ДЕЛ}(x,8)$. Заключение нарушается только если одновременно $x \lt A$ и $\text{ДЕЛ}(x,8)$ истинно, то есть $x$ кратно 8. Число, кратное и 12, и 8, кратно их НОК: $\text{НОК}(12,8)=24$. Значит «опасные» $x$ — это кратные 24: $24, 48, 72, \ldots$. Чтобы для всех них заключение было истинно, нужно $x \ge A$ на каждом опасном $x$, то есть $A$ не больше наименьшего опасного числа. Наименьшее кратное 24 (натуральное) — это 24. Чтобы условие держалось на $x=24$, требуется $24 \ge A$. Наименьшего $A$ задача не ограничивает снизу разумно (подойдёт и $A=1$), поэтому корректно спрашивают НАИБОЛЬШЕЕ $A$: оно равно $A = 24$. При $A=24$ на $x=24$ имеем $24 \ge 24$ — истина; на остальных кратных 12, не кратных 8 (например 12, 36), второй дизъюнкт $\neg\text{ДЕЛ}(x,8)$ истинен. Ответ: наибольшее A = 24.

Как это работает

Алгоритм почти всегда один. Сначала описываете множество посылки $P$ (отрезок, кратные числа, объединение). Затем находите «контрпримеры» — те $x \in P$, на которых заключение $Q$ может быть ложно. Заключение часто имеет вид $(x \le A) \lor R(x)$ или $(x \ge A) \lor R(x)$; ложно оно там, где $R(x)$ ложно — именно эти точки и нужно «накрыть» отрезком с параметром $A$. Параметр выбираете так, чтобы накрыть все опасные точки и при этом быть максимальным или минимальным по условию. Для делимости главный инструмент — НОД и НОК: пересечение «кратных k» и «кратных m» — это «кратные НОК(k,m)».

Чтобы не ошибиться с границами и НОК, удобно перебрать диапазон программой:

from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

# Найти наибольшее A: ДЕЛ(x,12) -> (x >= A) или НЕ ДЕЛ(x,8), для всех x в 1..1000
def holds(A, limit=1000):
    for x in range(1, limit + 1):
        if x % 12 == 0:                      # посылка истинна
            concl = (x >= A) or (x % 8 != 0)  # заключение
            if not concl:
                return False
    return True

best = max(A for A in range(1, 200) if holds(A))
print("НОК(12, 8) =", lcm(12, 8))
print("Наибольшее A =", best)

Вывод:

НОК(12, 8) = 24
Наибольшее A = 24

Частые ошибки

Путают направление вложения. Из $P \Rightarrow Q$ следует $P \subseteq Q$, а не наоборот. «Внутри» обязано быть множество посылки.
Берут НОД вместо НОК (или произведение $12 \cdot 8 = 96$ вместо НОК = 24). Пересечение кратностей — это всегда НОК.
Ошибаются на единицу в границе: путают строгие и нестрогие неравенства. Если заключение содержит $x \ge A$, то на $x = A$ оно ещё истинно — проверяйте крайнюю точку отдельно.
Ищут наименьшее $A$, когда нет нижнего ограничения (или наоборот). Внимательно читайте, что спрашивают — наибольшее или наименьшее — и какая граница реально «работает».
Забывают про второй дизъюнкт ($\neg\text{ДЕЛ}$ или другой $R(x)$): он «спасает» часть точек, и их накрывать отрезком уже не нужно.

Итоги

«Истинно для всех x» в импликации $P \Rightarrow Q$ означает вложение множеств $\{P\} \subseteq \{Q\}$.
Найдите опасные точки — те $x$ из посылки, где заключение может стать ложным, — и накройте их параметром.
Пересечение «кратных k» и «кратных m» — это «кратные НОК(k, m)»; это сердце задач с ДЕЛ.
Крайние точки отрезков и направление неравенств проверяйте отдельно — здесь чаще всего теряют балл.