Задание 2 ЕГЭ: строки с пропущенными значениями в таблице истинности

Что проверяет задание

Задание 2 ЕГЭ по информатике проверяет умение анализировать таблицу истинности логического выражения без её полного построения «в столбик». В подтеме «строки с пропущенными значениями» проверяется конкретный навык: дан фрагмент таблицы истинности, где строки заполнены конкретными нулями и единицами, но неизвестно, какой столбец соответствует какой переменной формулы (заголовки скрыты вопросительными знаками). Нужно восстановить это соответствие, используя логическую структуру выражения и свойства данных строк — например, что все строки различны или что показаны все строки с определённым значением функции.

По сути задание проверяет три вещи одновременно: знание таблиц истинности базовых операций ($\neg$, $\wedge$, $\vee$, $\to$, $\equiv$), умение быстро вычислять значение сложного выражения на конкретном наборе переменных и умение рассуждать «от следствия к причине» — по итоговому значению функции восстанавливать условия на переменные.

Как выглядит формулировка и сколько баллов

Типичная формулировка: «Логическая функция $F$ задаётся выражением … Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции $F$. Определите, какому столбцу соответствует каждая из переменных». В ответе нужно записать буквы переменных подряд, без пробелов и разделителей, в порядке следования столбцов фрагмента слева направо.

Задание оценивается 1 первичным баллом, ответ — короткая строка из букв (например, xzy). Формат ответа не числовой, а буквенный, поэтому важно строго соблюдать порядок столбцов. На задание стоит тратить не более 3–4 минут: правильный метод позволяет обойтись без построения полной таблицы даже для 4–5 переменных.

Что нужно знать

• Отрицание $\neg A$ истинно, когда $A$ ложно.
• Конъюнкция $A \wedge B$ истинна только тогда, когда оба операнда истинны.
• Дизъюнкция $A \vee B$ истинна, если хотя бы один операнд истинен.
• Импликация $A \to B$ ложна ровно в одном случае — когда $A=1$, $B=0$; во всех остальных случаях истинна.
• Эквивалентность $A \equiv B$ истинна, когда $A$ и $B$ равны.
• Число строк полной таблицы истинности с $n$ переменными равно $2^n$.
• Стандартный порядок перечисления наборов — по возрастанию значения двоичного числа, составленного из значений переменных (первая переменная — старший разряд).
• «Неповторяющиеся строки» — условие, что среди показанных строк нет двух одинаковых наборов; это ограничивает число допустимых перестановок столбцов.
• Приоритет операций: сначала $\neg$, затем $\wedge$, затем $\vee$, затем $\to$, затем $\equiv$; скобки меняют порядок вычисления.

Методы решения

Метод полного перебора. Строится вся таблица истинности выражения (все $2^n$ строк в исходном алфавитном порядке переменных), затем среди них ищутся строки, совпадающие по значению функции с фрагментом. Мини-пример: для $F=a\wedge b$ единственная строка с $F=1$ — это $(1,1)$; по одной такой строке различить $a$ и $b$ нельзя, нужны ещё строки.

Метод поиска константного столбца. Если столбец фрагмента состоит только из нулей или только из единиц, стоит проверить, не вынуждает ли формула эту переменную быть постоянной при заданном значении $F$. Мини-пример: если в выражении есть член $\neg w$, то при $F=0$ во всех строках $w=1$ — значит столбец из единиц соответствует $w$.

Метод поиска «столбцов-антонимов». Если два столбца во всех строках фрагмента всегда противоположны, это признак условия вида $x\equiv z$ или $x\ne z$ в формуле. Подробный пример разобран ниже.

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

Метод проверки гипотезы подстановкой. Выдвигается предположение о соответствии столбцов переменным, значения из фрагмента подставляются в формулу, результат сравнивается со столбцом $F$. Если хотя бы одна строка не совпала — гипотеза отбрасывается; условие «строки различны» помогает быстро исключать заведомо неверные варианты.

Алгоритм решения по шагам

1. Определить число переменных $n$ и количество строк фрагмента.
2. Проанализировать формулу: определить, при каком сочетании значений операндов она принимает то значение, которое показано в столбце $F$.
3. Построить (полностью или частично) набор строк, при которых функция принимает нужное значение, в исходном алфавитном порядке переменных.
4. Сравнить количество полученных строк с количеством строк фрагмента — совпадение подтверждает, что это именно те строки.
5. Сопоставить структуру столбцов фрагмента (константы, пары-антонимы, чередование) со структурой, полученной на шаге 3, чтобы определить перестановку переменных.
6. Подставить восстановленное соответствие в формулу и проверить совпадение со всеми строками фрагмента.
7. При неоднозначности использовать условие «строки не повторяются», отбрасывая перестановки, дающие повторы.
8. Записать ответ буквами переменных подряд, в порядке столбцов слева направо, без разделителей.

Разбор примеров

Пример 1. Дано $F=(x\vee y)\to(z\equiv x)$, ответ: xzy.

Строим полную таблицу для трёх переменных в порядке $x,y,z$, вычисляя $F$ по определению импликации (ложна только когда $x\vee y=1$ и $z\equiv x=0$):

$$\begin{array}{ccc|c}x&y&z&F\\\hline0&0&0&1\\0&0&1&1\\0&1&0&1\\0&1&1&0\\1&0&0&0\\1&0&1&1\\1&1&0&0\\1&1&1&1\end{array}$$

Значение $F=0$ встречается у трёх наборов: $(0,1,1)$, $(1,0,0)$, $(1,1,0)$ — это строки фрагмента. Во всех трёх строках $x$ и $z$ всегда противоположны: импликация ложна только когда $z\equiv x=0$, то есть $x\ne z$ обязательно. Значит пара столбцов-антонимов в фрагменте — это $x$ и $z$, а третий столбец — $y$.

Чтобы различить, какой из антонимов $x$, а какой $z$, проверяем подстановкой: гипотеза «первый столбец $x$, второй $z$, третий $y$» даёт $F=0$ на всех трёх строках фрагмента — совпадение полное. Обратная гипотеза («первый $z$, второй $x$») на одной из строк даёт $F=1$, что противоречит данным. Значит верно: столбцы — $x,z,y$. Ответ: xzy.

Пример 2. Дано $F=(x\equiv z)\vee(x\to(y\wedge z))$, ответ: yzx.

Функция ложна только когда оба слагаемых дизъюнкции ложны: $x\equiv z=0$ (то есть $x\ne z$) и $x\to(y\wedge z)=0$, что для импликации означает $x=1$ и $y\wedge z=0$. Из $x=1$ и $x\ne z$ получаем $z=0$; условие $y\wedge z=0$ выполняется автоматически. Ложные наборы: $(x,y,z)=(1,0,0)$ и $(1,1,0)$.

Видно, что $z$ всегда равен 0 в обеих строках — это константный столбец, жёстко зафиксированный структурой формулы. Значит столбец фрагмента из одних нулей — это $z$. Переменная $x$ тоже константна (всегда 1), а $y$ меняется. Ответ yzx означает: первый столбец — меняющийся $y$, второй — константный ноль $z$, третий — константная единица $x$. Подстановка в формулу подтверждает $F=0$ для обеих строк только при таком порядке; любая другая расстановка констант нарушает совпадение хотя бы раз.

Пример 3. Дано $F=(x\wedge\neg y)\vee(y\equiv z)\vee\neg w$, ответ: wzyx. Условие прямо говорит, что фрагмент содержит все строки, где $F$ ложна.

Функция ложна, только когда ложны все три слагаемых: $x\wedge\neg y=0$, $y\equiv z=0$ (то есть $y\ne z$) и $\neg w=0$ (то есть $w=1$). Последнее сразу даёт сильную подсказку: во всех строках фрагмента столбец, состоящий только из единиц, соответствует $w$.

Далее $y\ne z$ даёт варианты $y=0,z=1$ или $y=1,z=0$; условие $x\wedge\neg y=0$ означает $x=0$ или $y=1$. Комбинируя, получаем три ложных набора: $(w,x,y,z)=(1,0,0,1)$, $(1,0,1,0)$, $(1,1,1,0)$.

Столбец $w$ — константа 1, узнаётся сразу. Столбец $z$ принимает значения $1,0,0$, столбец $y$ — $0,1,1$, столбец $x$ — $0,0,1$. Проверка подстановкой с гипотезой «столбцы идут в порядке $w,z,y,x$» даёт $F=0$ на всех трёх строках; любая другая расстановка приводит к расхождению хотя бы на одной строке. Ответ: wzyx.

Типичные ошибки и ловушки

• Путают порядок операций и забывают, что импликация и эквивалентность вычисляются позже конъюнкции и дизъюнкции без скобок.
• Считают импликацию ложной чаще, чем она есть — забывают, что $A\to B$ истинна всегда, кроме случая $A=1$, $B=0$.
• Забывают, что порядок букв в ответе — это порядок столбцов слева направо, а не порядок появления переменных в формуле.
• Не проверяют финальную гипотезу подстановкой всех строк фрагмента — ограничиваются одной удачно совпавшей строкой и делают поспешный вывод.
• Игнорируют условие «строки не повторяются», хотя это часто единственный способ отбросить частично совпадающую, но неверную перестановку.
• Путают, для какого значения функции построен фрагмент (все строки с $F=0$ или все с $F=1$) — это меняет всю дальнейшую логику.
• Допускают ошибки при переборе всех $2^n$ строк из-за невнимательного заполнения — заполнять нужно строго в стандартном возрастающем порядке.

Как готовиться

Начинать стоит с автоматизации таблиц истинности пяти базовых операций — их нужно знать наизусть, без вычислений на бумаге. Далее полезно решать задачи на аналитическое определение условий, при которых сложное выражение ложно или истинно — это тренирует навык декомпозиции формулы без построения полной таблицы, что резко ускоряет решение при 4–5 переменных.

Отдельно стоит потренироваться в поиске «признаков» в столбцах — константных значений и пар-антонимов — и в быстрой проверке гипотез подстановкой. Полезно решать подряд 5–7 задач этого типа с разными формулами (с импликациями, эквивалентностями, отрицаниями снаружи скобок), чтобы закрепить связь между структурой формулы и структурой данных фрагмента. Хорошая практика — решать одну задачу двумя способами (полным перебором и аналитически) и сравнивать скорость и надёжность каждого подхода.