В этой статье мы решим задачу № 2 из демонстрационного варианта ЕГЭ-2023 года по информатике. Задача № 2 встречается почти в неизменном виде, начиная с ЕГЭ-2016. До 2016 года задача была в тестовом виде, где нужно было выбрать один из четырёх вариантов. В соответствии со спецификацией ФИПИ задача относится к базовому уровню сложности и оценивается в 1 балл, рекомендуемое время на решение этой задачи составляет 3 минуты. В конце статьи будет ссылка на тест на портале Эрудит.Онлайн, в котором вы сможете потренироваться в решении задач такого типа. Обращайте внимание не только на правильность решения, но и на затраченное время.
Демонстрационный вариант ЕГЭ-2023 по информатике
Миша заполнял таблицу истинности логической функции F = ¬(y->x) \/ (z-> w) \/ ¬z, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение
Для решения задачи № 2 нужно знать основные функции алгебры логики и уметь составлять таблицу истинности. Мы подготовили краткую памятку по основным функциям:
Функции алгебры логики в задачах ЕГЭ по информатике
Способ 1
Посмотрим на функцию F = ¬(y -> x) \/ (z -> w) \/ ¬z, она представляет собой дизъюнкцию трех выражений: ¬(y -> x), z -> w и ¬z. В последнем столбце таблицы все значения равны 0, следовательно, каждое из выражений равно 0. Проанализируем их по отдельности.
1) Рассмотрим выражение ¬z. Так как оно должно быть равно 0, то z всегда принимает значение 1. Можно сделать вывод, что z соответствует третьему столбцу таблицы, так как другие столбцы содержат в себе значение 0.
2) Рассмотрим выражение z -> w и вспомним, что импликацию можно выразить через дизъюнкцию и отрицание, а именно: z -> w = ¬z \/ w = 0. Такой результат можно получить в единственном случае, когда ¬z = 0 (то есть z = 1, что подтверждается первым пунктом рассуждений) и w = 0. Следовательно, переменной w может соответствовать только столбец 4, так как первый и второй содержат в себе значение 1, а третий уже соотнесен с переменной z.
3) Итак, нам осталось распределить по двум столбцам оставшиеся переменные, рассмотрим выражение ¬(y -> x). Аналогично предыдущему пункту выразим в виде: ¬(y -> x) = ¬(¬y \/ x). Затем используем одну из формул де Моргана и получим: ¬(¬y \/ x) = ¬¬y /\ ¬x = y /\ ¬x = 0.
Перейдем к фрагменту таблицы:
Нас будет в большей мере интересовать вторая строка. Допустим, что столбцу 1 соответствует y, а столбцу 2 соответствует x, тогда y /\ ¬x = 0 /\ ¬1 = 0 /\ 0 = 0. Выражение верное.
Убедимся в правильности нашего решения, выполнив проверку: допустим, что столбцу 2 соответствует y, а столбцу 1 соответствует x, тогда y /\ ¬x = 1 /\ ¬0 = 1 /\ 1 = 1, что неверно.
Итак, получено решение yxzw.
Способ 2
Если нам все же требуется перебор всех значений, ускорить работу поможет MS Excel. Заполним таблицу всех возможных значений:
Определим набор операций и конечный результат:
- ¬(y -> x)
- z -> w
- ¬z
- F = ¬(y -> x) \/ (z -> w) \/ ¬z
Добавим новый столбец для каждого из этих выражений, как показано на рисунке:
Теперь необходимо написать формулы для их вычисления, в MS Excel используются:
Для столбца ¬z опишем формулу: НЕ(C2), получим результат:
Взяв за нижний правый угол границу ячейки, протащим формулу на все 16 ячеек и получим результат:
Аналогично напишем остальные выражения:
Далее отфильтруем последний столбец по значению ЛОЖЬ, так как этого требует условие задачи. Сделаем это следующим образом: на главной странице выбираем Сортировка и фильтр -> Фильтр, затем выбираем необходимое значение:
Получаем, что функция F равна 0 только в трех случаях, тогда нам остается только сопоставить полученный результат с исходными данными:
Видим, что z не может быть 1, 2 или 4 столбцом, так как в них присутствуют нули, значит, z – это третий столбец. Аналогично, w может быть только 4-м столбцом, а чтобы распределить x и y, проведем анализ как в Способе 1, а именно: допустим, что столбцу 1 соответствует y, а столбцу 2 соответствует x, тогда y /\ ¬x = 0 /\ ¬1 = 0 /\ 0 = 0. Выражение верное. Убедимся в правильности нашего решения, выполнив проверку: допустим, что столбцу 2 соответствует y, а столбцу 1 соответствует x, тогда y /\ ¬x = 1 /\ ¬0 = 1 /\ 1 = 1, что неверно.
Получаем ответ: yxzw.
Способ 3
Для построения таблицы истинности также можно написать программу, которая выведет все строки, результат которых равен 0. Далее приведен фрагмент кода на языке Python и результат его выполнения.
Теперь можно соотнести таблицы как в предыдущем способе.
В другой нашей статье можно посмотреть еще примеры решения аналогичных задач из ЕГЭ предыдущих лет:
Задача № 2 из ЕГЭ-2021 по информатике
Потренироваться в решении задач такого типа можно в тесте на портале Эрудит.Онлайн «ЕГЭ-2023 Задача № 2».
Разборы других задач: