+Оглавление
Разбираем задачу №2 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Тут говорится что задача на умение строить таблицы истинности и логические схемы (обратите внимание - строить, а не читать и не ещё что-то). Элементы содержания и уровни подготовки посмотрим в кодификатору по кодам 1.5.1 и 1.1.6 соответственно.
Требуется знать про логические операции, "кванторы" (тоже название операций, но с другим подтекстом), уметь строить (опять) таблицы истинности.
Про алгебру логики (про ту часть, которая нужна в школе) я написал статью, стоит с ней ознакомиться, даже если Вам всё по логике вещей ясно.
Несколькими годами ранее, задание на второй позиции было другим. Там требовалось определять, подходит ли функция под таблицу истинности. В общем-то ничего не изменилось, кроме того, что подбор стал чуть труднее: вместо четырёх явно записанных вариантов, которые надо было перебрать тогда, стало 24 варианта, которые ещё надо самому записать.
Дополнительно осложняется дело тем, что в некоторых ячейках таблицы нет чисел, то есть, это может быть любая или даже каждая строка таблицы, в которых остальные цифры совпадают.
Метод грубой силы
С первым заданием сработал такой метод, стоило лишь выписать числа по порядку. Это тогда сэкономило нам кучу времени и памяти на формулы, избавило нас от серьёзных рисков что-то перепутать. Можно попытаться решить и это задание таким же методом. Для этого достаточно составить полную таблицу истинности для высказывания (сделать за Мишу его работу), и определить, какой столбец куда подходит.
Сразу видно, что в условии нам дали все три строки с "нулями", и других нет. Осталось лишь определить, какие куда подойдут.
И строки, и столбцы в "дано" перемешаны как попало. В нашей таблице тоже можно переставлять как пожелаем, но только одна конфигурация совпадёт с данной нам таблицей. Таких перестановок 144 штуки. Большое, но вполне себе конечное поле. Кстати, есть и закономерности. Есть уникальный столбец, где два нуля (он точно x), и одно это скидывает нам число перестановок всего до 12 (3 столбца свободно переставляются и можно менять местами две строки. Ну, а если заметить, что в оставшихся столбцах по одному нулю, а в столбце w - ни одного, то вообще перестановок только четыре.
Совпадает правая нижняя. Ответ: xwzy
Метод красив и привлекателен своей простотой. Даже если не использовать хитрые приёмы снижения количества вариантов, то он всё равно работает на 100%. Гарантированно верный результат даёт всего лишь умение строить таблицы истинности.
Другие методы
На этом можно было бы и закончить, но, к сожалению, этот метод очень трудоёмкий. Только на первом этапе необходимо выполнить 6*16=96 логических вычислений. Если заглянем в спецификацию, то увидим, что авторы считают, что на это задание можно потратить (открыл, прочитал, понял, решил, проверил, записал ответ) всего лишь 3 минуты. Большинство других методов сводятся к попыткам сократить количество вычислений до минимума (желательно до 6*3=18) или ещё меньше.
Рекомендуется, в первую очередь, использовать законы алгебры логики. Их очень много, но в этом задании используется всего три.
Обратите внимание на действия и порядок действий в выражении
Во всех вторых заданиях даются выражения, где два последних действия одинаковые. Это либо конъюнкция, либо дизъюнкция, либо импликация (крайне редко, но зато бывает в других заданиях). Чем так интересны эти три действия? Взгляните на их таблицы истинности:
Сюда ещё можно добавить стрелку Пирса и штрих Шеффера, но их в школе не проходят. У них есть одна уникальная строка. В конъюнкции - первая строка (там ВСЕ столбцы по "1"), а в остальных строках справа - "нули". В дизъюнкции, наоборот, в последней строке везде "0", а в остальных справа "единицы". Вторая строка импликации тоже, бывает, используется, не будем о ней забывать.
Есть правило, закон, определение или как хотите, что
сложное высказывание, составленное из любого количества выражений, соединённых конъюнкцией, истинно только тогда, когда истинны одновременно все входящие в него выражения.
Аналогично с дизъюнкцией, только там "ложно" надо писать. С импликацией чуть сложнее.
Это правило используется для того, чтобы из 144 перестановок получить куда меньше. Например, мы видим (и так будет всегда в ЕГЭ), что везде должны получиться нули и имеет место дизъюнкция - это последняя строка. Значит, при всех входящих, ВСЕ простые высказывания (x /\ ¬ y) и (x ≡ z) и даже (¬ w) должны получаться ложными. А чтобы увидеть, когда какое будет ложным, надо иметь приличный опыт работы с такими вещами.
Но теперь, после такого правила, нам остаётся анализировать 3 высказывания отдельно, а не одно, составленное из трёх. А это, скажу Вам наперёд, куда проще. И самое простое - (¬ w). Даже не имея большого опыта, можно сказать, что оно будет ложным только тогда, когда w будет "1". В столбце w просто не может стоять нулей.
Такой шаг из 144 вариантов оставил нам всего 36, а это уже кое что. И пока ещё вычислений (явных) мы не делали. Так можно и вообще до одной перестановки сократить. Методик таких масса, они есть в интернете, и мы их сейчас рассматривать не будем, как самостоятельные.
Важно, что в сложнейшем переборе из 144 вариантов мы существенно снижаем количество вариантов каждымкаждым ходом.
Стратегия подготовки
Я рекомендую в первую очередь тренироваться составлять таблицы истинности. Если нарешивать по сборникам, то начинать стоит именно с метода грубой силы, составляя полные таблицы истинности. Это кажется нерентабельным, но будет очень полезным: по мере составления таблиц вы увидите закономерности, близкие именно вам и получите такой метод, который подойдёт персонально для вас.
Лучше всего искать способы ускорить построение таблиц истинности.
Хитрые ходы, размышления и прочие методы, которые описаны в разных ютьюбах, стоит смотреть уже после того, как вы будете уверенно выполнять это задание (пусть и дольше 3х минут) с помощью таблицы истинности.
Надеюсь вам понравилась статья.
Читайте о структуре КИМ ЕГЭ по информатике и разбор первой задачи.
Ставьте лайк и подписывайтесь, чтобы не пропустить дальнейшие разборы
