Логика

Слово «логика» в кодификаторе (код 5.2) сбивает с толку: на ЕГЭ по математике это не таблицы истинности и не значки «И/ИЛИ» из информатики. На профиле логика выходит в задании 19 — одном из двух самых дорогих заданий экзамена (наравне с № 18), 4 балла и около 40 минут. Это задача про числа: делимость, остатки, наибольшие и наименьшие значения. Но проверяют в ней не арифметику, а рассуждение: умеешь ли ты доказать, а не просто угадать ответ.

Задание 19 почти всегда состоит из трёх пунктов — а), б), в), — и они устроены логически по-разному. Один спрашивает «можно ли», «существует ли», «приведите пример». Другой — «докажите, что всегда», «верно ли для любого». Третий — «найдите наибольшее (наименьшее) значение», «найдите все такие числа». За каждым типом стоит своя логика доказательства, и путать их нельзя: то, что закрывает один пункт, не годится для другого.

Баллы тут делят по пунктам, а не по «примерно решил». Официальные критерии простые: 1 балл — верно только пункт а или только б; 2 балла — верно в или сразу а и б; 3 балла — два пункта, включая в; 4 — все три. Пункт в) обычно самый тяжёлый и самый ценный: без него выше двух баллов не подняться.

Дальше — логические инструменты, которыми берётся это задание: кванторы «существует / для любого», связка «оценка плюс пример», доказательство невозможности через инвариант, полный перебор случаев (удобнее всего — по остаткам), принцип Дирихле и метод крайнего. Опорные для задания 19 — оценка с примером, инвариант и перебор по остаткам; Дирихле и метод крайнего выручают реже, но знать их стоит. Арифметику делимости и остатков разбираем в соседней теме про натуральные числа; здесь — про то, как из неё собрать доказательство, которое примет эксперт.

Вся логика задания 19 держится на различии двух формулировок. «Существует ли число, для которого…» (то же самое: «можно ли», «приведите пример») — это вопрос о существовании. «Верно ли для любого числа…» («докажите, что всегда») — вопрос о всеобщности. Отвечают на них принципиально по-разному.

Чтобы доказать существование, достаточно одного примера. Нашёл хоть одно подходящее число, проверил, что оно годится, — пункт закрыт. Никаких «а вдруг есть ещё» доказывать не нужно: спросили, бывает ли, — ты показал, что бывает.

Чтобы доказать всеобщность, одного примера категорически мало. «Проверил на трёх числах, сошлось» — это не доказательство, а наблюдение: следующее число может всё сломать. Здесь нужно рассуждение, которое охватывает сразу все числа — обычно через остатки, разложение на множители или общую формулу. Зато у всеобщности есть слабое место: чтобы её опровергнуть, хватит одного контрпримера. Если утверждают «для любого n верно P», а ты предъявил хоть одно n, где P ломается, — утверждение неверно, и доказывать больше нечего.

Формально это правило отрицания квантора: отрицание «для любого x верно P» — это «существует x, для которого P неверно».

Отсюда рабочая привычка: прочитав пункт, сначала спроси себя — это «существует» или «для любого»? От ответа зависит, что вообще считается решением. Под пункт «докажите, что всегда» подсунуть пример — значит получить за него ноль, даже если пример верный.

Пункты «можно ли» коварны тем, что ответ бывает «нет». Показать, что можно, легко — приводишь пример. А как доказать, что нельзя? Перебрать все числа не выйдет, их бесконечно много. Значит, нужен признак, который отличает возможное от невозможного разом для всего множества.

Такой признак называют инвариантом — это величина или свойство, которое не меняется при всех разрешённых действиях (или одинаково у всех допустимых объектов). Логика доказательства невозможности прямая: если у всего, что нам доступно, инвариант один, а у цели он другой — цель недостижима.

Самый частый инвариант — чётность. Разберём на примере. Выпишем числа от 1 до 10; за один ход разрешено стереть любые два числа $a$ и $b$ и вместо них записать их разность $|a-b|$. Так продолжаем, пока не останется одно число. Может ли им оказаться ноль?

Считаем сумму всех чисел на доске. Сначала она равна $1+2+\dots+10 = 55$ — число нечётное. Каждый ход заменяет пару $a,\,b$ на $|a-b|$, то есть уменьшает сумму на $a+b-|a-b|$. Эта величина равна удвоенному меньшему из чисел — она всегда чётна. Значит, каждый ход меняет сумму на чётное число, а чётность суммы остаётся прежней. Она была нечётной — нечётной и останется до самого конца.

Последнее оставшееся число и есть вся сумма, а она нечётна. Ноль чётен — получить его невозможно. Вот и всё доказательство: мы не перебирали ходы, а нашли то, что при них не портится. Чётность — простейший инвариант, но по той же схеме работают остатки по другим модулям и другие сохраняющиеся величины.

Когда чисел или вариантов конечное, обозримое число, работает честный перебор случаев. Он законен и оценивается наравне с «красивым» решением — критерии прямо говорят: метод не важен, важна грамотность рассуждения. Но у перебора есть железное требование — полнота. Разобрал пять случаев из шести и забыл шестой — считается, что задача не решена: вдруг именно в пропущенном случае ответ другой.

Чтобы перебор был полным, дели множество на случаи так, чтобы они точно покрывали всё. Классический приём — по остаткам: любое целое число при делении на 3 даёт остаток 0, 1 или 2, других вариантов нет. Разобрал эти три — значит, разобрал все целые числа сразу, хотя их бесконечно много. Это мостик от перебора к доказательству всеобщности.

Метод крайнего — ещё один логический приём: рассмотреть самый большой или самый маленький объект в наборе. Часто именно у крайнего элемента обнаруживается свойство, которое двигает всё решение: наименьшему числу некуда убывать, наибольшему — некуда расти, и это ограничение и есть зацепка. Простейшая иллюстрация: почему не бывает бесконечно убывающей цепочки натуральных чисел? Возьми в ней наименьшее число — меньше него натуральных в цепочке уже нет, а убывать дальше некуда, значит цепочка обрывается. Крайний элемент сам закрыл вопрос — и никакого перебора не понадобилось.

Все эти инструменты — кванторы, оценка с примером, инвариант, Дирихле, перебор — не набор рецептов «на каждую задачу свой», а разные грани одного навыка: доводить мысль до конца так, чтобы к ней нельзя было придраться. Именно за это в задании 19 и платят четырьмя баллами.