Решение: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, которые удовлетворяют всем условиям:
$(\neg x_1 \lor y_1) \to (\neg x_2 \land y_2) = 1$
$(\neg x_2 \lor y_2) \to (\neg x_3 \land y_3) = 1$
$\ldots$
$(\neg x_8 \lor y_8) \to (\neg x_9 \land y_9) = 1$
Решение по шагам
5 шаговКаждую пару $(x_i,y_i)$ можно рассматривать как одно из четырёх состояний: $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$.
Импликация $(\neg x_i \lor y_i) \to (\neg x_{i+1} \land y_{i+1})$ ложна только при $x_i=1$ и $y_i=0$, когда первая часть истинна, а вторая часть для следующей пары должна быть истинной. Поэтому из состояний $(0,0)$, $(0,1)$ и $(1,1)$ можно перейти только в $(0,1)$.
Из состояния $(1,0)$ можно перейти в любое из четырёх состояний. Обозначим через $T_n$ число допустимых последовательностей длины $n$. Состояние $(1,0)$ на каждом шаге имеет ровно один способ продолжения из самого себя, поэтому его число всегда равно $1$.
При добавлении следующей пары каждая последовательность увеличивает общее число продолжений на один, а последовательность, заканчивающаяся в состоянии $(1,0)$, даёт ещё три дополнительных продолжения. Поэтому $T_{n+1}=T_n+3$.
Для одной пары $T_1=4$. Всего пар девять, поэтому $T_9=4+8\cdot3=28$.
Где здесь ошибаются
Считать, что из каждого состояния можно перейти в любое следующее состояние.
Забыть, что импликация ложна только при истинном условии и ложном следствии.
Рассматривать переменные $x_i$ и $y_i$ независимо, не объединяя их в пары состояний.