Информатика решу ЕГЭ: как справиться с заданием №15 на математическую логику

В 2021 году ЕГЭ по информатике предстает в новом свете. Впервые экзамен будет проходить на компьютерах, что привело к глубокому изменению сути заданий и структуры контрольных измерительных материалов. Вместе с тем, в работе остались задания на математическую логику, с которыми у выпускников прошлых лет всегда были сложности. Достаточно проблемным является задание №18 из КИМ ЕГЭ 2020 года, которое в 2021 году сменило номер на №15. Разберем, как правильно решать это задание, а также аналогичные ему, чтобы задача «Информатика решу ЕГЭ на 80+ баллов» стала реальностью.

Особенности задания №15

Очевидно, что информатика как сфера человеческой деятельности в основе своей имеет математику, которая, в сущности, является языком всей науки. Раздел «Алгебра логики» играет огромную роль как с точки зрения организации работы ЭВМ, так и в решении прикладных задач, поэтому его знания проверяются на ЕГЭ. Вместе с тем, пересечение информатики и математики зачастую ставит в тупик участников экзамена, которые даже не пытаются решать соответствующие задачи.

В частности, в 2020 году с заданием №18 повышенного уровня сложности на ЕГЭ не справилось 48,9% — почти половина участников экзамена. Оно стало хорошим инструментом для дифференциации выпускников. В частности, с заданием хорошо справились сильные ребята (97% из этой группы правильно решили задачу), и очень плохо слабо подготовленные участники, из которых только 14% смогли найти правильный ответ.

Значительные трудности вызвало также задание №23 высокого уровня сложности, посвященное тому же разделу. Его выполнило только 0,5% участников, что свидетельствует о слабом владении математической логикой. Это один из базовых навыков, которые мы тренируем на курсах ЕГЭ по информатике, поэтому наши выпускники регулярно входят в число высокобалльников.

Установка «Информатика решу ЕГЭ на 80+ баллов»

Для того, чтобы справиться с заданием №15 ЕГЭ 2021, необходимо освоить основные моменты математической логики. В частности, следует понимать, что такое:

• логическая операция «отрицание» (НЕ либо ¬);
• конъюнкция (логическое умножение, И либо /\);
• дизъюнкция (логическое сложение, ИЛИ либо \/);
• импликация (логические следование, →);
• приоритет логических операций;
• таблица истинности;
• взаимосвязь между логическими операциями, приоритет их выполнения;
• преобразование или вычисление значений логических выражений.

Также рекомендуем выучить основные формулы алгебры логики, которые используются для преобразования логических выражений:

• правила тавтологии: А \/ А = А; А /\ А = А;
• двойное отрицание: ¬(¬А) = А;
• преобразование импликации в дизъюнкцию А → В = ¬ А + В (эта формула пригодится нам при решении задания №15);
• Формулы де-Моргана: ¬(А \/ В) = ¬А \/¬В; ¬(А /\ В) = ¬А /\¬В.

Кроме того, при решении заданий №15 понадобятся не только знания из алгебры логики, но и базовые математические знания, например, понимание натуральных чисел, понятие наименьшего общего кратного. В одном из вариантов используется навык перевода из десятичной системы счисления в двоичную, а также понятие поразрядной конъюнкции, то есть логическое поразрядное умножение чисел.

Решение задания №15

В качестве примера рассмотрим задание №15 из актуальной демоверсии КИМ ЕГЭ 2021 года.

Исходная формула:

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9)).

Для начала необходимо упростить выражение, заменив импликацию дизъюнкцией. Начнем с выражения в скобках (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9)), преобразовав его в соответствии с определением импликации: новое высказывание ложно, если посылка истинна, а следствие ложно. В итоге выражение (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9)) будет преобразовано в (¬ ДЕЛ(x, 6) \/ ¬ДЕЛ(x, 9)). Аналогичное действие произведем со всем выражением и получим:

ДЕЛ(x, А) \/ ¬ДЕЛ(x, 6) \/ ¬ДЕЛ(x, 9).

В переводе на «человеческий язык» это выражение означает: выражение истинно, если для всех значений натурального числа х выполняется хотя бы одно из условий:

• ДЕЛ(x, А) = 1
• ¬ДЕЛ(x, 6) = 1, то есть ДЕЛ(x, 6) = 0
• ¬ДЕЛ(x, 9) = 1, то есть ДЕЛ(x, 9) = 0

Анализируя формулу, мы можем увидеть:

• если ДЕЛ(x, 6) или ДЕЛ(x, 9) принимает значения 0 (это происходит тогда, когда х не делится нацело на 6 или на 9 или на 6 и 9 одновременно), то ДЕЛ(x, А) может быть ложью – тогда формула будет тождественно истинна;
• если и ДЕЛ(x, 6) и ДЕЛ(x, 9) принимают значение 1 (это происходит тогда, когда х делится нацело на 6 и 9, то есть является кратным для обоих чисел), то и ДЕЛ(x, А) обязательно должно быть правдой, то есть число х должно нацело делиться и на А.

По условию логическое утверждение ДЕЛ(n, m) означает, что при делении натурального числа n на натуральное число m получается натуральное число, то есть имеет место деление без остатка. Исходя из этой предпосылки, понимаем, что формула будет тождественно истинна тогда, когда истинно хотя бы одно слагаемое, то есть x делится на А, 6 и 9 без остатка. При этом по условию нам необходимо взять не любое, а максимально возможное значение А, которое будет равно наименьшему общему кратному 6 и 9, то есть 18.

Следует учесть, что при А = 3 выражение ДЕЛ(x, А) также будет истинно, но А не будет максимально возможным натуральным числом, что противоречит условию задачи. Также обратите внимание, что А не может равняться, например 36 или 72, поскольку тогда при х = 18 все три слагаемых выражения ДЕЛ(x, А) \/ ¬ДЕЛ(x, 6) \/ ¬ДЕЛ(x, 9) будут обращаться в 0 (будут ложными).

Занимайтесь на курсах подготовки к ЕГЭ и ОГЭ (ГИА) в паре TwoStu и получите максимум баллов на ЕГЭ и ОГЭ!