Как определить порядок столбцов в задании 2 ЕГЭ по информатике

В задании 2 ЕГЭ по информатике нужно подписать столбцы фрагмента таблицы истинности. Начните со столбца F. Если в нём стоят нули, выпишите наборы значений, при которых формула равна нулю. По этим наборам можно определить, какие буквы поставить над столбцами.

Порядок переменных один для всего фрагмента. В пустую клетку можно поставить 0 или 1, а уже записанные значения нужно сохранить. После заполнения все строки должны различаться. В ответе запишите буквы слева направо без пробелов, как в проекте демоверсии ЕГЭ по информатике на 2027 год от ФИПИ (ZIP).

Когда импликация равна нулю

Импликация p → q равна нулю только при p = 1 и q = 0. Направление стрелки важно. Например, 1 → 0 даёт 0, а 0 → 1 даёт 1. Если справа стоит выражение в скобках, как в x → (y ∧ z), сначала вычислите его значение. Правило можно сверить по таблице истинности импликации в учебнике OpenStax.

Знак ∧ означает «и», ∨ — нестрогое «или», ¬ — отрицание. Их таблицы и примеры есть в разборе конъюнкции, дизъюнкции и отрицания.

Разбор на бумаге

Дана функция F = (x → (y ∧ z)) ∨ (w ∧ ¬z). Определите порядок переменных. В заголовке стоят номера столбцов, а ? обозначает пропуск.

1	2	3	4	F
0	0	?	0	0
0	0	1	1	0
0	1	1	1	0

Выпишите все наборы, на которых F равно нулю

Главная связка в формуле — «или». Чтобы вся формула дала 0, обе её части должны дать 0. Из импликации получаем x = 1 и y ∧ z = 0. Дальше удобно рассмотреть два значения z.

• При z = 0 выражение w ∧ ¬z равно w, поэтому w = 0. Условие y ∧ z = 0 выполняется при любом y.
• При z = 1 выражение w ∧ ¬z равно нулю при любом w. Чтобы y ∧ z = 0, нужно взять y = 0.

Запишем четыре набора в порядке x, y, z, w. Так проще сравнивать их с фрагментом.

x	y	z	w
1	0	0	0
1	1	0	0
1	0	1	0
1	0	1	1

Сопоставьте наборы со строками фрагмента

1. Во всех четырёх наборах x = 1. В первом, втором и четвёртом столбцах фрагмента есть нули. Остаётся третий столбец. В его пропуске должна стоять единица.
2. В третьей строке фрагмента три единицы. Среди наборов с F = 0 такой только один — 1011 в порядке x, y, z, w. В нём единственный ноль приходится на y. Во фрагменте этот ноль стоит в первом столбце, значит, первый столбец — y.
3. Осталось расставить w и z. Во второй строке во втором столбце стоит 0, а в четвёртом — 1. Если второй столбец — z, получим z = 0 и w = 1. Тогда w ∧ ¬z = 1 и вся формула равна 1. Поэтому второй столбец — w, а четвёртый — z.

Проверим найденные подписи. В порядке x, y, z, w три строки фрагмента дают 1000, 1010 и 1011. Все три набора дают F = 0 и различаются. Набор 1100 тоже даёт ноль и остаётся за пределами фрагмента. В условии может быть показана только часть строк с F = 0.

Ответ — ywxz.

Если из формулы трудно сразу выписать подходящие наборы, переберите все 16 наборов для четырёх переменных. При проверке конкретного порядка сначала сопоставьте строки, для которых подходит ровно один набор. Затем подберите разные оставшиеся наборы для строк с пропусками. Если для одной строки осталось несколько вариантов, попробуйте каждый и проверьте, можно ли заполнить остальные строки.

Два упражнения

1. Проверьте, совпадут ли строки

Дана функция F = (a → b) ∧ (a ∨ c). Найдите порядок переменных и цифру в пропуске так, чтобы все строки были различными.

1	2	3	F
0	0	0	0
0	?	0	0
1	1	0	0

2. Найдите все подходящие порядки

Дана функция F = p → (q ∧ r) и одна строка фрагмента. Сколько разных порядков переменных ей соответствуют?

1	2	3	F
1	0	?	0

Ответы и разбор

1. Порядок cab, в пропуске 1. Главная связка — «и», поэтому для F = 0 достаточно нуля в одной из частей. Импликация равна нулю при a = 1, b = 0 и любом c. Выражение a ∨ c равно нулю при a = 0, c = 0 и любом b. В порядке a, b, c получаем наборы 000, 010, 100 и 101.

В последней строке две единицы. Среди подходящих наборов так выглядит только 101, где b = 0. Значит, b стоит в третьем столбце. Для первых двух остаются два порядка.

• При порядке acb единица в пропуске означала бы c = 1 при a = b = 0. Набор 001 в порядке a, b, c даёт F = 1. Если поставить в пропуск ноль, вторая строка совпадёт с первой. Получается, что при порядке acb ноль во всех строках возможен только с повтором 000.
• При порядке cab единица в пропуске означает a = 1 при b = c = 0. В порядке a, b, c получаем 000, 100 и 101. Все три набора подходят и различаются.

2. Подходят четыре порядка — pqr, prq, qrp и rqp. Для F = 0 нужно, чтобы p = 1 и q ∧ r = 0. Поэтому p может стоять в первом столбце или в третьем, если поставить в пропуск единицу. В обоих случаях второй столбец даёт ноль одной из переменных справа от стрелки. Переменные q и r входят в одну конъюнкцию. Если поменять их местами в любом решении, получится ещё одно решение, сколько бы строк ни было во фрагменте.

Три карточки для повторения

Ответьте по памяти и сверьтесь с правым столбцом. Через несколько дней попробуйте снова, затем примените правила к новому фрагменту таблицы.

Вопрос	Ответ
При каких значениях p и q выражение p → q равно нулю?	Только при p = 1 и q = 0.
Если A ∨ B = 0, чему равны A и B?	Обе части равны нулю.
Когда допустим порядок столбцов, если в таблице есть пропуски?	Когда можно заполнить пропуски так, чтобы все строки дали указанные значения F и отличались друг от друга.

Вопросы можно добавить в свою колоду. Первые шаги описаны в руководстве Nibomo.

Разбор и самостоятельные упражнения подготовлены для этой статьи с помощью ИИ. Ответы проверены перебором значений и перестановок столбцов.