Статья Автор: Деникина Н.В., Деникин А.В.

Почему строки должны различаться

ЕГЭ-2025 · основная волна, 11 июня

F = ¬(w → (x ≡ y)) ∧ (z → x)

Дан фрагмент из трёх различных строк. Требуется восстановить подписи x, y, z, w. Точка обозначает неизвестное значение.

№1№2№3№4F
·0101
0··01
·11·1
Получим нужные строки

Равенство x ≡ y записывается как x == y. Импликацию A → B заменяем на not A or B, а отрицание всей скобки ставим перед ней. Программа напечатает только строки с F = 1.



Цветные числа — восстановленные значения. Курсивом отмечены значения при проверяемом, пока не доказанном порядке букв.

Найдём постоянное значение

В выводе программы w во всех строках равен 1. В первом, втором и четвёртом столбцах условия уже есть нули, поэтому эти столбцы не подходят.

Вывод Python · только F = 1
xyzwF
01011
10011
10111
Фрагмент из условия
№1№2w№4F
·0101
0·101
·11·1

Для w остаётся третий столбец. Допишем единицу во второй строке.

Определим места x и y

В выводе x и y всегда различаются. Во второй и четвёртой позициях первой строки стоят два нуля — эта пара столбцов не подходит. Первая и четвёртая позиции тоже не подходят: во второй строке обе равны 0.

Вывод Python · только F = 1
xyzwF
01011
10011
10111
Фрагмент из условия
№1№2wzF
·0101
0·101
·11·1

Для x и y остаются первый и второй столбцы. Четвёртый — z. Порядок x и y пока неизвестен.

Проверим первый порядок

Предположим, что первый столбец — x, второй — y. В первой строке тогда y = 0 и z = 0: подходит только набор 1001 из вывода, поэтому x = 1. Во второй строке x = 0: подходит только набор 0101, поэтому y = 1.

Вывод Python · только F = 1
xyzwF
01011
10011
10111
Проверяемый порядок · ещё не доказан
xywzF
10101
01101
·11·1

Первые две строки совместимы с выводом. Теперь проверим третью строку при том же порядке букв.

Стоп: две строки совпали

В третьей строке при выбранных подписях y = 1. В выводе только один такой набор — 0101. Он уже использован для второй строки. Другого набора с y = 1 нет, поэтому изменить пропуски и избежать повтора не получится.

Вывод Python · только F = 1
xyzwF
01011
10011
10111
Проверяемый порядок · ещё не доказан
xywzF
10101
01101
01101
Строка 2 = строка 3

В обеих строках: 0, 1, 1, 0. Один и тот же набор использован дважды — это противоречит условию.

Вторая и третья строки совпали целиком. Условие требует три различные строки. Следовательно, проверяемый порядок x, y, w, z неверен, хотя каждая строка отдельно даёт F = 1.

Проверим оставшийся порядок

Остаётся порядок y, x. В первой строке во втором столбце дан 0, то есть x = 0. В выводе только один такой набор — 0101, поэтому y = 1. Во второй строке y = 0 и z = 0: подходит только 1001, поэтому x = 1.

Вывод Python · только F = 1
xyzwF
01011
10011
10111
Фрагмент из условия
yxwzF
10101
01101
011·1

В третьей строке x = 1. В обоих подходящих наборах y = 0, но z может быть 0 или 1. Допишем y = 0; последнее значение пока оставим неизвестным.

Восстановим пропуск по различию строк

Сравним вторую и третью строки: первые три значения у них одинаковы — 0, 1, 1. Во второй строке z = 0. Если в третьей поставить тоже 0, строки снова совпадут.

Вывод Python · только F = 1
xyzwF
01011
10011
10111
Фрагмент из условия
yxwzF
10101
01101
01111

Значит, в третьей строке z = 1. Все три набора присутствуют в выводе и различаются. Ответ в порядке столбцов условия: yxwz.


Проверим понимание

Каждая заполненная строка даёт нужное F, но две строки совпали. Можно ли принять такой порядок столбцов?

Печать