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

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

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

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