Шешімі: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, которые удовлетворяют всем перечисленным ниже условиям?
$(x_1 \to (x_2 \land y_2)) \land (y_1 \to y_2) = 1$
$(x_2 \to (x_3 \land y_3)) \land (y_2 \to y_3) = 1$
$\ldots$
$(x_8 \to (x_9 \land y_9)) \land (y_8 \to y_9) = 1$.
Шешім по шагам
5 қадамОбозначим состояние пары $(x_i,y_i)$ одним из төрт кодов: $00$, $10$, $01$, $11$.
Условия перехода между соседними парами дают следующие возможности: $00 \to 00,10,01,11$; $10 \to 11$; $01 \to 01,11$; $11 \to 11$.
Для первой пары каждое из төрт состояний встречается по одному разу: $(1,1,1,1)$.
После последовательного подсчёта переходов получаем количества для пар с номерами от 1 до 9: $(1,1,1,1)$, $(1,1,2,4)$, $(1,1,3,8)$, $(1,1,4,13)$, $(1,1,5,19)$, $(1,1,6,26)$, $(1,1,7,34)$, $(1,1,8,43)$, $(1,1,9,53)$.
Складываем количества последовательностей для тоғыз пар: $1+1+9+53=64$.
Где здесь ошибаются
Считать, что из состояния $10$ можно перейти в $10$; это невозможно, так как при $x_i=1$ обязательно должны выполняться $x_{i+1}=1$ и $y_{i+1}=1$.
Рассматривать логические импликации как равенства.
Не учитывать все төрт возможных значения начальной пары $(x_1,y_1)$.