Задание EGEINFCF662F: Логические выражения и уравнения

Всего 9 пар (xᵢ, yᵢ). Каждая пара имеет четыре состояния: 00, 01, 10, 11.
Условия связывают только соседние пары. Поэтому достаточно считать допустимые начала последовательности отдельно для каждого состояния её последней пары.
Импликация ложна только при 1 → 0; эквивалентность истинна при равных значениях; ∧ требует истинности обеих частей, ∨ — хотя бы одной.
Первое условие: (¬x₁ ∨ y₁) → (¬x₂ ∧ y₂) = 1.
В остальных связях индексы увеличиваются одновременно. Проверим все 4 · 4 = 16 переходов подстановкой в это условие.
В каждой следующей строке слева указана предыдущая пара, справа — разрешённые состояния следующей пары:
00 → 01.
01 → 01.
10 → 00, 01, 10, 11.
11 → 01.

Обозначим через Nₖ(s) число допустимых начал из k пар, оканчивающихся состоянием s. Для получения Nₖ₊₁(s) складываем количества только тех предыдущих состояний, из которых разрешён переход в s.
Nₖ₊₁(00) = Nₖ(10).
Nₖ₊₁(01) = Nₖ(00) + Nₖ(01) + Nₖ(10) + Nₖ(11).
Nₖ₊₁(10) = Nₖ(10).
Nₖ₊₁(11) = Nₖ(10).
Дополнительных условий на первую или последнюю пару нет.
Начинаем с одного способа выбрать каждую допустимую первую пару. Во всех векторах порядок состояний один и тот же: 00, 01, 10, 11.
После 1 пар: (1; 1; 1; 1).
После 2 пар: (1; 4; 1; 1).
После 3 пар: (1; 7; 1; 1).
После 4 пар: (1; 10; 1; 1).
После 5 пар: (1; 13; 1; 1).
После 6 пар: (1; 16; 1; 1).
После 7 пар: (1; 19; 1; 1).
После 8 пар: (1; 22; 1; 1).
После 9 пар: (1; 25; 1; 1).
Учитываем только разрешённые последние состояния: 00, 01, 10, 11.
Итоговое количество: 1 + 25 + 1 + 1 = 28.

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