Задание 2 ЕГЭ по информатике: таблицы истинности

В условии даны логическая функция, записанная формулой, и частично заполненный фрагмент её таблицы истинности: несколько строк, в которых часть клеток заполнена нулями и единицами, а столбцы переменных не подписаны. Столбцов столько, сколько в формуле переменных, и значение самой функции в каждой строке известно. Нужно определить, какому столбцу какая переменная соответствует. Ответом служат буквы, записанные одна за другой в порядке столбцов, без пробелов и разделителей, и мелочь с порядком в этом задании стоит отдельного внимания, потому что именно на ней проседает ответ.

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

Что понадобится знать заранее

Начинать нужно с привычки читать связки словами, а не значками. Читайте формулу по-русски: «и», «или», «не», «из ... следует ...», «равносильно». Тогда каждая строка таблицы превращается в предложение, которое либо верно, либо нет, и спорить с ним нечего.

Четыре факта нужно помнить твёрдо:

• «и» даёт единицу только тогда, когда единицы обе части
• «или» даёт нуль только тогда, когда нули обе части
• «из A следует B» даёт нуль в единственном случае: A истинно, а B ложно, во всех остальных случаях единица
• «равносильно» даёт единицу, если обе части одинаковые, нуль в противном случае

Самая частая путаница связана со «следует»: направление важно. Из «x следует y» не вытекает «y следует x», и формулы «x следует y» и «y следует x» дают разные столбцы. Если вы читаете выражение глазами и сомневаетесь, проговорите его вслух по-русски с начала: так порядок виден.

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

Два разбора: единицы и нули

Для разбора я составил функцию сам: «из x следует y, и при этом верно z». Пусть дан фрагмент таблицы, в котором везде функция равна единице, то есть показаны только строки с истинным значением. Строки такие: 1 0 0, 1 1 0 и 1 1 1, где цифры идут по столбцам слева направо, а столбец функции не показан. Клетки я заполнил полностью, чтобы разбор был короче. В настоящем задании часть клеток пуста, и вывод делается по тем, что есть, но ход мысли тот же.

Начинать надо со строки, которая сильнее всего ограничивает выбор. Функция равна единице, а в формуле стоит «и z». Значит, z обязана быть единицей в каждой из показанных строк. Смотрим на столбцы: первый — это единица во всех трёх строках, а второй и третий содержат нули. Следовательно, первый столбец — z.

Остаются x и y, и между ними связь «из x следует y». Она запрещает ровно одно сочетание: x равно единице, а y нулю. Проверим вариант «второй столбец x, третий y»: в строке 1 1 0 во втором столбце единица, а в третьем нуль, то есть как раз запрещённое сочетание. Вариант неверный. Другой вариант: второй столбец y, третий x. Для строки 1 1 0 тогда x равен нулю, y единице, всё в порядке, и остальные строки тоже проходят. Ответ: zyx.

Весь разбор уместился в минуту-две, и это нормальная скорость для такого задания. Если вы тратите заметно больше, стоит разобраться, где именно: на чтении формулы или на переборе вариантов.

Бывает и обратное условие: в фрагменте перечислены наборы, на которых функция ложна. Рассуждение зеркальное, и привычка к единицам тут мешает. Для него я придумал ещё одну функцию: «x и не y, или z». Показаны три строки: 0 0 0, 1 0 0 и 1 0 1, цифры снова по столбцам слева направо.

«Или» ложно только тогда, когда ложны обе части. Значит, в каждой строке z равна нулю, и этому условию удовлетворяет один-единственный столбец, средний. Остаются два других, и вторая часть, «x и не y», должна быть ложной во всех трёх строках. Она ложна, если x равен нулю или y равен единице, то есть опасное сочетание одно: x единица, y нуль. Попробуем считать, что первый столбец x, а третий y: в строке 1 0 0 получится как раз опасное сочетание, значит, так нельзя. Остаётся первый столбец y, третий x, и ответ yzx.

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

Когда лучше программа

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

Порядок действий для четырёх переменных такой: сначала записать строки фрагмента списком из четырёх значений и значения функции, затем написать вычисление формулы в виде короткой функции, затем перебрать перестановки четырёх букв и для каждой перестановки пройти по всем строкам. Если хоть одна строка не совпала, перестановка отбрасывается. Если выживает ровно одна, это ответ; если несколько, значит, где-то ошибка в записи формулы, потому что задание подразумевает единственное решение. Такая программа сама служит проверкой: ошибка в записи формулы обычно оставляет ноль или несколько выживших, и это сразу видно.

Два замечания о записи. Знак «из ... следует ...» в Python удобно записывать как сравнение: выражение «x <= y» ложно лишь тогда, когда x равно единице, а y нулю, и это в точности то, что требуется от импликации. Знак «равносильно» записывается как «x == y». Перед экзаменом проверьте это на двух-трёх примерах, чтобы не потерять минуты в зале на разбирательство. В других языках импликация записывается иначе, так что способ, который вам удобен, проверьте на своём языке дома.

По-моему, при четырёх переменных надо идти в программу сразу, а при трёх вручную. Ручной способ при трёх быстрее, чем набрать код, и вдобавок он учит рассуждению, которое понадобится в других заданиях. Спорная точка зрения, потому что есть учителя, которые настаивают на ручном решении всегда. Тем, кто на пробниках стабильно решает вручную и не ошибается, программа не нужна, и менять привычку я не посоветую.

Запись ответа

Здесь нередко теряют балл по глупости. Ответ — последовательность букв в порядке столбцов, как они стоят в таблице слева направо. Алфавитный порядок и порядок появления переменных в формуле здесь ни при чём. Перед вводом перечитайте последнюю строку условия: в ней сказано, какие именно столбцы нужно назвать и в каком порядке записать буквы.

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

Откуда тема и что делать, если задание не идёт

Алгебра логики проходится в основной школе, в разных линиях учебников в разных классах, и обычно её дают небольшим блоком: связки и таблицы истинности для двух переменных, несколько упрощений. Для задания нужно больше: уверенно строить таблицы для трёх-четырёх переменных и читать их в обратную сторону, от строк к формуле. Дальше в курсе эта же тема возвращается в старших классах с более сложными выражениями, и подробности о том, что и когда проходится, есть в статье про информатику в школе.

Различайте два случая. В первом вы не умеете вычислять выражение: путаете, когда импликация истинна, или не помните приоритета операций. Лечится это коротким повторением и десятком упражнений на вычисление значения формулы при заданных значениях переменных. Во втором вычисление вам знакомо, но вы не видите, с какой строки начать. Здесь помогает один приём: ищите строку, где требуемое значение функции получается единственным способом, и ограничивайте выбор столбцов от неё.

Не мучайте одно условие больше десяти минут. Если ответ не сходится, проверьте, верно ли вы прочитали саму формулу: с таблицей ошибаются реже. С предыдущим заданием это связано общим подходом к описанию, где данные частично скрыты, и об этом вы можете прочитать в статье про таблицы и графы. Следующее по теме — базы данных, там нужны уже другие навыки.

Где найти разбор с репетитором

Хорошо, если репетитор показывает оба способа и спрашивает, какой у вас получается надёжнее. Платформа не записывает занятия и не показывает экран, поэтому свою программу вы присылаете в чат (он открывается после того, как репетитор получил ваш контакт) и разбираете вместе на занятии.

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ

Вопросы и ответы

Нужно ли помнить таблицы истинности наизусть? Достаточно помнить, когда связка даёт нуль: у «и» нуль, если хоть одна часть ложна, у «или» — только если обе ложны, у «следует» — в одном случае. Остальное выводится.

Что делать, если в строке заполнена всего одна клетка? Эта строка как раз может быть самой полезной. Если функция в ней ложна, а известна только одна клетка, спросите у формулы, при каком значении этой переменной ложность вообще возможна, и привяжите клетку к переменной, у которой такое значение допустимо. Строки с множеством заполненных клеток проверяют, а строки с одной клеткой чаще всего и дают первое решение.

Сколько времени отводить на это задание? Ориентируйтесь на свой пробник: измерьте время на десяти заданиях и возьмите ближайшее круглое число минут с запасом.

Как проверить себя после ответа? Подставьте найденное соответствие обратно в формулу и вычислите значение функции для каждой строки, где хватает известных клеток. Строк в фрагменте немного, поэтому проверка занимает минуту. Если хоть в одной строке значение не совпало с тем, что дано в таблице, соответствие неверное, и вводить ответ нельзя. Такая обратная проверка ловит не только ошибку в рассуждении, но и ошибку в самом чтении формулы, а это самая частая причина неверного ответа у тех, кто торопится.

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