Задание 15 · Законы математической логики
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — наибольшее A, при котором ДЕЛ(x, A) ∨ ((x ∈ [50; 70]) → ¬ДЕЛ(x, 15)) истинна при любом x, — решается в подтеме 1, а подтема 4 продолжает её. Пролистай черновик: точками отмечены строки, которых не было в предыдущем шаге.
- Подтема 1, «Стрелка через ИЛИ»: три части через ИЛИ. Точками отмечены новые строки.
- Подтема 1, «Где решает A»: все части без A ложны.
- Подтема 1, «Проверка программой»: A подходит, если верно при всех x.
- Подтема 4, «Несколько кратных»: несколько чисел — их НОД. Ответ задачи темы — 60; на отрезке [50; 100] было бы 15.
Остальные подтемы — тот же вопрос «где все части без A ложны» для других условий: отрезков и множеств, плоскости, поразрядной конъюнкции, а дополнительный урок — для новых условий с A.
Карта темы
Каждая подтема дала правило для своего вида условий, и любое решение собирается из них. Сверху — путь от формулы к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Стрелкиp → q заменить на ¬p ∨ q
- Где решает Aвсе части без A ложны
- Ответнаибольшее, наименьшее, длина, сумма
1Формула с параметром A
- p → qложна только при 1 → 0
- ДЕЛ(n, m)n делится на m — первое на второе
all(f(x, A) for x in …)проверка A программой
2Отрезки и множества
- A справаточки, которые A обязан накрыть
- ¬Aточки, где A быть можно
- длина [a; b]b − a, а точек b − a + 1
3Координатная плоскость
- A > выражениябольше наибольшего в области
- строгий знакграница сдвигается на 1
4Делимость
- на оба числаделится на их НОК
- A делит всенаибольшее A — их НОД
5Поразрядная конъюнкция
- наименьшее Aтолько обязательные двоичные веса
- наибольшее Aвсе разрешённые веса
6Треугольник, MAX и условия с Aдополнительный урок
- новое условиечитать по определению из условия
Как решать
Любое задание 15 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- 0 → 1
- 0 → 1 посчитали ложью → стрелка ложна только при 1 → 0. Спроси себя: это запрещённая пара 1 → 0?подтема 1
- стрелка в Python
p or q→(not p) or q. Спроси себя: где отрицание левой части?подтема 1- ДЕЛ наоборот
- ДЕЛ(15, x) — «x кратно 15» → 15 делится на x: x — делитель 15. Спроси себя: какое число делится на какое?подтема 1
- длина и точки
- длина [25; 40] — 16 → длина 15, точек 16. Спроси себя: спрашивают длину или число точек?подтема 2
- строгий знак
- A > 30 — ответ 30 → A = 31. Спроси себя: подходит ли само граничное значение?подтема 3
- угол области
- наибольшее — при самых больших x и y → для каждого x — свой наибольший y. Спроси себя: все ли точки области я сравнил?подтема 3
- break для наибольшего
- для наибольшего A — первое подходящее с break → последнее подходящее, без break. Спроси себя: в какую сторону идёт перебор?подтема 1
- узкий диапазон
- x перебран до 50, а отрезок до 70 → диапазон с запасом накрывает все числа условия. Спроси себя: все ли важные x попали в перебор?подтема 1
Итог
Тема пройдена: задача темы решена от замены стрелки до ответа 60. Вот что взять с собой.
- ПорядокСтрелки, где решает A, требование, ответ, проверка.
- Стрелкаp → q = ¬p ∨ q: ложна только при 1 → 0.
- Главный вопросПри каких x все части без A ложны?
- ДелимостьНа оба — НОК, A делит все — НОД.
- Задача темыРешает только x = 60 — A делит 60, ответ 60.
Проверьте себя
Ответь сначала сам, потом открой ответ.
В задаче темы делитель 15 заменили на 25. Какое наибольшее A теперь?
ОтветСкрыть ответ
Кратное 25 на [50; 70] — только 50 (75 уже вне). A делит 50 — наибольшее A = 50.
Формула истинна при x = 7 без A. Влияет ли A на ответ при этом x?
ОтветСкрыть ответ
Нет: A решает только при тех x, где все части без A ложны.
A должно делить 60, 75 и 90. Какое наибольшее A?
ОтветСкрыть ответ
НОД(60, 75, 90) = 15.
Нужно A > x + y при всех точках области, наибольшее x + y = 30. Какое наименьшее целое A?
ОтветСкрыть ответ
31: строгий знак сдвигает границу на 1.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Наименьшее A: x · x < A
Для какого наименьшего целого числа A формула (x ≤ 12) → (x · x < A) тождественно истинна, то есть принимает значение 1 при любом натуральном значении переменной x?
Введите число.
Подсказка
Всё решает A при x от 1 до 12. Найди самое большое x · x.
Решение
При x ≥ 13 левая часть ложна. При x от 1 до 12 нужно x · x < A, самое большое значение — 144. Нужно 144 < A, наименьшее A = 145.
def imp(p, q): return (not p) or q def f(x, A): return imp(x <= 12, x * x < A) for A in range(-100, 1000): if all(f(x, A) for x in range(1, 1000)): print(A) breakОтвет: 145
Наименьшая длина отрезка A
На числовой прямой даны два отрезка: P = [15; 40] и Q = [21; 63]. Укажи наименьшую возможную длину такого отрезка A, что формула (x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P)) истинна при любом значении переменной x.
Введите число.
Подсказка
Замени стрелки и найди точки, где всё решает A.
Решение
Заменим стрелки: ¬P ∨ ¬(Q ∧ ¬A) ∨ ¬P = ¬P ∨ ¬Q ∨ A. Всё решает A на общей части P и Q — отрезке [21; 40]. Наименьший A — он сам, длина 40 − 21 = 19.
Ответ: 19
Наименьшее A: маски 29 и 17
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Для какого наименьшего неотрицательного целого числа A формула (x & 29 ≠ 0) → ((x & 17 = 0) → (x & A ≠ 0)) тождественно истинна при любом неотрицательном целом x?
Введите число.
Подсказка
Найди веса, которые есть в 29, но нет в 17.
Решение
29 = 16 + 8 + 4 + 1, 17 = 16 + 1. В 29, но не в 17 — веса 8 и 4. Оба обязаны быть в A: наименьшее A = 12.
def imp(p, q): return (not p) or q def f(x, A): return imp(x & 29 != 0, imp(x & 17 == 0, x & A != 0)) for A in range(0, 256): if all(f(x, A) for x in range(0, 256)): print(A) breakОтвет: 12
Наибольшее A: 2x + y = 70
Укажи наибольшее целое значение A, при котором выражение (2x + y ≠ 70) ∨ (x < y) ∨ (A < x) истинно для любых натуральных x и y.
Введите число.
Подсказка
Всё решает A на точках прямой 2x + y = 70, где x ≥ y.
Решение
Части без A ложны, когда 2x + y = 70 и x ≥ y. Тогда 3x ≥ 70, x ≥ 24; а y ≥ 1 даёт x ≤ 34. На этих точках нужно A < x, самый трудный — x = 24. A < 24, наибольшее A = 23.
def f(x, y, A): return 2 * x + y != 70 or x < y or A < x answer = Nonefor A in range(-100, 1000): if all(f(x, y, A) for x in range(1, 100) for y in range(1, 100)): answer = Aprint(answer)Ответ: 23
Наименьшее A: некратные 4
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула (x ∈ [20; 50]) → (ДЕЛ(x, 4) ∨ (x < A)) тождественно истинна при любом натуральном x?
Введите число.
Подсказка
Всё решает A при числах отрезка, не кратных 4. Проверь конец отрезка.
Решение
Части без A ложны при числах отрезка [20; 50], которые не делятся на 4. Конец 50 на 4 не делится — он самый большой. Нужно 50 < A, наименьшее A = 51.
def imp(p, q): return (not p) or q def f(x, A): return imp(20 <= x <= 50, x % 4 == 0 or x < A) for A in range(1, 1000): if all(f(x, A) for x in range(1, 1000)): print(A) breakОтвет: 51