Для какого наименьшего целого неотрицательного числа А логическое выражение (78125 ≠ y + 4x) ∨ (A > x) ∧ (A > y) истинно (т.е. принимает значение 1) при любых целых положительных х и у?
Алгоритм решения задания 15. Часть 1
О задании
Ранее мы уже познакомились с операциями алгебры логики и изучили основные законы математической логики. Теперь настало время применить полученные знания на практике и научиться решать 15 задания ЕГЭ по информатике.
Эти задания направлены на проверку знаний основных понятий и законов математической логики. И суть их заключается в том, что вам необходимо проанализировать представленное логическое выражение, переписать его, используя синтаксис языка Python и подобрать возможные значения для заданных переменных.
Большинство заданий 15 решается подбором значения A. Мы выделим пять типов и каждому посвятим отдельную статью:
- Задания первого типа самые простые, в них даётся логическое выражение, содержащее некоторую неизвестную переменную А. Нужно подобрать такое значение этой переменной, при котором логическое выражение будет всегда истинным.
- В заданиях второго типа фигурируют название некоторых нетипичных функций: ДЕЛ, ТРЕУГ и так далее. Требуется лишь правильно записать действие этой функции, а далее все решение будет аналогично первому типу.
- И задания третьего типа, на самом деле, тоже не сильно отличаются от рассмотренных ранее. Только здесь предстоит работать с поразрядной конъюнкцией. Для ручного решения это может привнести некоторые трудности, но в программном методе отличий не будет никаких.
- А вот с заданиями четвёртого типа придётся постараться. В таких заданиях обычно даются два отрезка и требуется найти наименьшую или наибольшую длину некоторого отрезка А, для которого будет истинно логическое выражение. Программное решение здесь хоть и шаблонное, но довольно непростое для понимания.
- Наконец, задания пятого типа самые молодые — необычная формулировка была замечена в сборнике Крылова С.С. за 2026 год. Характерной чертой этих заданий является работа с множеством всех натуральных делителей какого-либо числа.
По ключевым словам в условии вы сможете определить тип задания и выбрать нужный алгоритм. В этой статье разберём первый, базовый, тип.
Эта же статья посвящена первому типу, здесь мы вспомним, как применять законы математической логики, как раскрывать несколько логических операций внутри выражения и научимся подбирать значения для неизвестного числа.
Алгоритм решения
Перед тем как перейдём к разбору алгоритма решения задания 15, давайте заострим внимание на некоторых основных моментах.
Начнём с простого вопроса: что означает формулировка «тождественно истинно»?
Обычная формула может быть истинной при одних значениях переменных и ложной при других. Тождественно истинная формула не имеет ни одного исключения: она обязана дать истину для каждого допустимого набора.
Представьте замок с тысячами комбинаций. Нас не устроит, если он откроется в 999 случаях из 1000. Достаточно одной «плохой» комбинации x и y, чтобы выбранное A не подошло.
Поэтому ручное решение часто начинается не с вопроса «когда формула истинна?», а с противоположного: «как заставить её стать ложной?». Найденный контрпример сразу отбрасывает A.
В формулировках 15 заданий часто будут встречаться слова «натуральные» или «целые» числа. Давайте вспомним, какие бывают множества чисел.
Начнём с самого малого — множества натуральных чисел. Натуральными называются числа, которые получаются при естественном счёте: 1, 2, 3 и так далее. То есть диапазон натуральных чисел N содержит числа от 1 до +∞. Здесь мы говорим только о целых числах, то есть не содержащих дробную часть!
Далее можно рассмотреть множество неотрицательных чисел. Неотрицательные числа включают в себя натуральные числа и 0. То есть содержат все числа от 0 до +∞.
Ну и последнее множество, которое будет использоваться в данных заданиях, — целые числа. Множество целых чисел представляет собой объединение натуральных чисел с противоположными им (1 и -1, 2 и -2), а также с нулём. То есть все числа от –∞ до +∞ (без дробной части).
Положительные числа строго больше 0. Неотрицательные включают положительные числа и 0. Всегда сверяйтесь с формулировкой: от неё зависит, включать ли 0 в перебор.
С основными терминами разобрались, теперь смело перейдём к решению 15 заданий. Для начала рассмотрим задание с такой формулировкой:
Решать его мы будем вручную. Давайте внимательно посмотрим на выражение и определим, в каких случаях оно будет истинным.
Первым делом вспоминаем приоритет логических операций (НЕ, И, ИЛИ). Расставим скобки в исходном выражении, чтобы подчеркнуть приоритет операций:
(78125 ≠ y + 4x) ∨ ((A > x) ∧ (A > y))
То есть первой операцией будет конъюнкция (A > x) ∧ (A > y), а затем дизъюнкция её результата с выражением 78125 ≠ y + 4x.
Главная идея такая: удобнее искать не все истинные случаи, а хотя бы один ложный. Фраза «тождественно истинно» означает, что ложных наборов x и y не должно быть вообще.
Контрпример — это конкретный набор значений, который опровергает общее утверждение. Если условие обещает истину при любых x и y, нам достаточно найти одну пару, на которой получится ложь.
И наоборот: чтобы доказать пригодность A, нужно показать, что ни одной такой пары существовать не может. Именно поэтому мы выписываем условия ложности и исследуем их как систему.
Согласно законам де Моргана дизъюнкция ложна только тогда, когда оба операнда ложны. То есть всё выражение ложно, если одновременно:
78125 = y + 4x(A > x) ∧ (A > y)— ложно
Перейдём к конъюнкции. Она может быть ложной, когда хотя бы одно из условий ложное:
(A ≤ x) ∨ (A ≤ y)
Здесь мы инвертировали операции и заменили конъюнкцию на дизъюнкцию.
Разберём этот переход медленно. Отрицание условия A > x даёт A ≤ x, то есть x ≥ A. Отрицание A > y даёт y ≥ A. По закону де Моргана отрицание И превращается в ИЛИ.
Так логическая фраза превращается в геометрическую: плоха любая точка на прямой y + 4x = 78125, у которой хотя бы одна координата достигла A.
Следовательно, чтобы всё выражение было ложным, требуется одновременное выполнение обоих условий при любых значениях переменных x, y:
78125 = y + 4xx ≥ Aилиy ≥ A
Но, а для решения задания нужно наоборот, чтобы таких пар не существовало. Для этого сначала найдём граничные значения для x и y относительно переменной A.
Перепишем первое равенство как y = 78125 − 4x. При целых x получаются целые y. Теперь нужно не допустить, чтобы хотя бы одно из этих значений было не меньше A.
Чтобы выражение всегда было истинным, для любой точки на этой прямой должно выполняться:
x < A и y < A
То есть все решения уравнения должны лежать строго внутри квадрата:
0 < x < A
0 < y < A
Рассматриваем положительные целые x и y. Максимальное x получается при минимальном y:
y ≥ 1
⇒ 78125 − 4x ≥ 1
⇒ 4x ≤ 78124
⇒ x ≤ 19531
В таком случае y будет равняться единице: y = 78125 − 4·19531 = 1. А максимальное y будет при минимальном x:
x ≥ 1
⇒ y = 78121
Всё, мы на финишной прямой. Поскольку уже найдены граничные значения для переменных (1, 19531 для x и 1, 78121 для y) мы можем найти наименьшее значение для A, исходя из выражений: x < A и y < A.
То есть значение А должно быть строго больше максимальных возможных значений для x и y. Максимальное из них — это 78121. Следовательно, A будет равняться 78122, как минимальное целое число, большее 78121.
Число 78122 и будет ответом на это задание.
Но давайте еще проверим границу, а не просто доверимся вычислениям. При A = 78121 берём x = 1 и y = 78121. Равенство y + 4x = 78125 выполняется, а условие A > y ложно. Получили контрпример.
При A = 78122 все положительные решения равенства имеют x < A и y < A. Поэтому обе части конъюнкции истинны, когда первая часть дизъюнкции ложна. Кандидат подходит.
Именно парная проверка A и соседнего значения защищает от ошибки на единицу. В заданиях со строгими знаками такая проверка особенно полезна.
Теперь давайте проанализируем наши действия и выведем алгоритм решения:
- Приводим выражение к однозначному виду: определяем приоритет операций и расставляем скобки внутри выражения.
- Выписываем условия ложности всего выражения. Ключевая мысль такая: «Тождественно истинно» = нет ни одного набора x, y, при котором выражение ложно. Определяем ложность выражения исходя из законов математической логики (чаще всего по законам де Моргана). Таким образом, получаем систему условий для всех переменных — только неравенства, без логических операций.
- Определяем граничные условия. Ищем такие значения переменных x, y, при которых система только-только начинает иметь решения. Именно здесь появляется число, вокруг которого крутится ответ.
- Связываем граничные условия с параметром А. Можно буквально проговорить: «Чтобы такие x, y существовали, значение А должно быть…».
После решения проверьте границу. Если искали наименьшее A, кандидат должен подходить, а A − 1 — уже нет. Для наибольшего A проверяйте A и A + 1.
Рассмотрим еще небольшой учебный пример.
Пусть требуется наибольшее A, для которого (x ≤ 7) ∨ (x ≥ A) истинно при любом натуральном x. Формула ложна, когда одновременно x > 7 и x < A.
Первое натуральное x, которое больше 7, равно 8. При A = 9 оно ещё и меньше A, поэтому появляется контрпример x = 8. А при A = 8 условия x > 7 и x < 8 несовместимы.
Ответом будет 8. На маленьком примере видна вся схема: выписали ложность, нашли первую опасную точку, проверили границу и соседнее значение.
Пример 1
Давайте закрепим выведенный алгоритм на примере решения такого задания:
Для какого наибольшего целого неотрицательного числа A выражение (x+y ≤ 30) ∨ (y ≤ x+2) ∨ (y ≥ A) тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y?
Пойдём по порядку. Сначала приведём выражение к однозначному виду. Здесь работаем только с дизъюнкцией, так что приоритет операций не играет роли. Этот шаг можем пропустить.
Далее выписываем условия ложности всего выражения. Дизъюнкция ложна тогда и только тогда, когда все три части выражения ложны одновременно:
x + y > 30y > x + 2y < A
Так мы получили систему строгих неравенств. Для фиксированного x плохое значение y должно быть строго больше и x + 2, и 30 − x, но при этом меньше A.
Иначе говоря, y > max(x + 2, 30 − x). Нам нужно найти самую низкую границу, выше которой может появиться плохая точка.
Одно выражение, x + 2, растёт, а второе, 30 − x, убывает. Максимум из них будет наименьшим рядом с точкой их пересечения.
x + 2 = 30 − x
2x = 28
x = 14
- При x = 14 обе границы равны 16.
- Но неравенства строгие: y должен быть больше 16. Первое целое плохое значение — y = 17.
На графике ниже видно, как границы сближаются именно в точке (14; 16).
С точки зрения геометрии это самая низкая высота (значение y), на которой можно оказаться выше обеих прямых y = x + 2 и y = 30 – x одновременно.
Проверим соседнее A = 18: при x = 14 и y = 17 все три части исходной дизъюнкции ложны.
14 + 17 > 30
17 > 14 + 2
17 < 18
Следовательно, A = 18 уже не подходит.
Знчение A = 17 подходит и является наибольшим возможным значением.
Ответ: 17.
Программное решение
Что же, к ручному методу мы вернёмся в разборах следующих типов, а теперь давайте разберём программное решение. Его суть до безобразия проста: мы не вручную вычисляем все возможные значения для неизвестных, при которых выражение будет истинно, а перебираем их в программе.
Как и с ручным методом, давайте сразу на примере реальной задачи напишем решение и потом его подробно разберём.
Формулировка будет следующая:
Для какого наименьшего целого неотрицательного числа A выражение (x-3y < A) ∨ (y > 400) ∨ (x>56) тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y?
Для начала нам следует переписать выражение в виде функции f:
Функция f получает один проверяемый набор x, y, A и возвращает True или False. Она не ищет ответ сама — она только честно отвечает на вопрос: «истинна ли формула на этой точке?»
Поиск выполняют циклы вокруг неё. Внешний перебор предлагает кандидата A, а генератор внутри all последовательно подставляет все нужные пары x и y. Запишем эту функцию так:
def f(x, y, A):
return (x - 3 * y < A) or (y > 400) or (x > 56)Перебираем A по возрастанию, потому что нужно наименьшее значение:
for A in range(0, 100):Полный бесконечный перебор не нужен. При y > 400 или x > 56 выражение сразу истинно. Поэтому достаточно точно проверить 1 ≤ x ≤ 56 и 1 ≤ y ≤ 400.
Эти значения для x и y, само собой, будем перебирать во вложенных циклах for. А передавать их в написанную ранее функцию f:
Функция all вернёт True лишь в том случае, если каждый вызов f оказался истинным. Если встретится первая ложная точка, проверка остановится: выбранное A уже не может быть ответом.
Диапазон нельзя брать наугад. Здесь условие y > 400 автоматически спасает формулу за пределами 400, а x > 56 — за пределами 56. Поэтому прямоугольник 1…56 на 1…400 покрывает все опасные случаи.
for A in range(0, 100):
if all(f(x, y, A) for x in range(1, 57) for y in range(1, 401)):Как только нашли A, при котором формула истинна для всех проверяемых x и y, выводим его и завершаем цикл:
def f(x, y, A):
return (x - 3 * y < A) or (y > 400) or (x > 56)
for A in range(0, 100):
if all(f(x, y, A) for x in range(1, 57) for y in range(1, 401)):
print(A)
breakГотово! Достаточно лишь запустить эту программу, чтобы получить ответ на текущее задание. В нашем случае это будет число 54.
В целом, такой несложный код подходит для решения первых трёх типов 15 заданий ЕГЭ по информатике. От вас лишь потребуется заменить выражение внутри функции f и, по необходимости, верхние границы переменных.
Но практиковаться в использовании этого кода мы уже будем в следующих статьях, посвященных второму и третьему типу 15 заданий.
Шаблон программного решения
Выведем вот такой шаблонный код решения 15 заданий первого типа:
def f(x, y, A):
return *1
for A in *2:
if all(f(x, y, A) for x in *3 for y in *4):
print(A)
breakЗдесь *1 — выражение из условия, *2 — диапазон A в нужном направлении (уменьшение или увеличение значения), *3 и *4 — диапазоны для x и y, берутся из выражения.
Итоги
В первом типе задания 15 мы ищем не множество истинных случаев, а возможный контрпример. Переводим формулу в условия ложности, связываем их с параметром A и находим границу, после которой плохой набор появляется или исчезает.
Всегда обращайте внимание на множество допустимых чисел: натуральный перебор начинается с 1, неотрицательный — с 0. Следите за строгими знаками и обязательно проверяйте найденное A вместе с соседним значением. В следующей статье адаптируем тот же подход к функциям ДЕЛ, ТРЕУГ и МАКС.
