Фрагмент и порядок столбцов

В подтеме 2 мы нашли наборы задачи темы, в которых F = 1: 0011, 0100, 0101, 0111 в порядке xyzw. Теперь сопоставим их со строками фрагмента. Пронумеруем столбцы — C1, C2, C3, C4: это места в таблице, а не новые переменные.

Порядок столбцов подходит, если при нём каждую строку можно дополнить до набора с нужным F и все строки окажутся разными. Подпись столбца одна на все строки: если C1 — это w, то в каждой строке в C1 записано значение w.

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

• Пустая клетка скрывает 0 или 1, и разные пустые клетки заполняются независимо.
• Строки идут в любом порядке: первая строка фрагмента не обязана быть первым набором таблицы.
• Строки различны после заполнения: две строки «1, пустая клетка, 0» могут стать 100 и 110.
• Фрагмент не обязан содержать все наборы с нужным F: у задачи темы таких наборов четыре, а строк во фрагменте три.

Решение идёт по четырём шагам.

1. Найди наборы с нужным F — от внешней операции (подтема 2) или программой (подтема 4).
2. Ищи особые места: переменную, которая во всех наборах одна и та же; строку, которой подходит единственный набор; столбец с несколькими нулями или единицами.
3. Каждый вывод проверяй на всех строках сразу: подпись столбца общая, строки — разные наборы.
4. Запиши буквы в порядке столбцов слева направо.

Решим задачу темы: слева фрагмент, справа четыре набора с F = 1. На каждом шаге подсвечен столбец или строка, о которых идёт речь.

Два приёма решили задачу почти целиком. Переменная с одним и тем же значением во всех наборах (здесь x = 0) сразу находит свой столбец. Строка, которой подходит единственный набор, подписывает несколько столбцов за раз.

Условие «строки различны» исключает порядок, при котором две строки обязаны стать одним набором. Возьмём F = (x ∨ y) ∧ (x → z) из подтемы 2 — её наборы с F = 1: 010, 011, 101, 111. Первые две строки фрагмента выглядят одинаково, и это не ошибка: их пустые клетки заполнятся по-разному.

При C3 = y каждой из первых строк по отдельности подходит набор 101 — но вместе им нужен один и тот же набор. Поэтому проверка «у каждой строки есть подходящий набор» недостаточна: наборы выбирают сразу для всех строк, без повторов.

Если у строк разные F, каждую строку сверяют со своим списком наборов. Та же формула F = (x ∨ y) ∧ (x → z), но новый фрагмент:

Наборы с F = 0 в порядке xyz: 000, 001, 100, 110; с F = 1: 010, 011, 101, 111. Первую и третью строки ищем в первом списке, вторую — во втором.

В третьей строке две единицы и F = 0. Среди наборов с F = 0 две единицы только у 110: x = 1, y = 1, z = 0. Ноль может стоять только в C1, поэтому C1 = z. Во второй строке z = 0 и F = 1 — среди единичных наборов с z = 0 есть только 010, где y = 1: единица в C3 — это y, а C2 = x. Ответ zxy.

Если отобрать строки только с одним значением F, вторая строка выпадет из рассуждения, и решение станет неверным.

Цепочка (x → y) ∧ (y → z) ∧ (z → w) разрешает только наборы, где после первой единицы идут одни единицы. Каждая стрелка запрещает пару «1 слева, 0 справа», поэтому в последовательности x, y, z, w за единицей не может стоять ноль. Подходят пять наборов: 0000, 0001, 0011, 0111, 1111.

Отсюда правило: если в строке в одном столбце 0, а в другом 1, переменная с нулём стоит в цепочке раньше переменной с единицей. Первая строка: C1 раньше C3. Вторая: C2 и C4 раньше C1. Третья: C2 раньше C3 и C4. Вместе это один порядок — C2, C4, C1, C3, то есть x, y, z, w.

В ответ идут буквы по столбцам: C1 = z, C2 = x, C3 = w, C4 = y — ответ zxwy, а не порядок цепочки.

• Пустая клетка0 или 1, у каждой своё
• Подпись столбцаодна на все строки
• Строкипосле заполнения различны; порядок любой
• Постоянная переменнаясразу находит свой столбец
• Единственный наборподписывает сразу несколько столбцов
• Разные Fкаждая строка — в списке своего F
• Ответбуквы по столбцам слева направо