Шешімі: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным условиям?
$x_1 \to y_1 = 1$
$(x_2 \to (x_1 \land y_2)) \land (y_2 \to y_1) = 1$
$(x_3 \to (x_2 \land y_3)) \land (y_3 \to y_2) = 1$
$\ldots$
$(x_7 \to (x_6 \land y_7)) \land (y_7 \to y_6) = 1$
Шешімін қадамдап көрсету
4 қадамДля первой пары $(x_1,y_1)$ условие $x_1 \to y_1=1$ исключает только комбинацию $(1,0)$. Поэтому возможны состояния $00$, $01$ и $11$.
$$(a_1,b_1,c_1)=(1,1,1)$$Для каждой следующей пары $(x_i,y_i)$ состояние $10$ невозможно. Состояние $00$ может следовать за любым состоянием, состояние $01$ — только за состояниями $01$ или $11$, а состояние $11$ — только за состоянием $11$.
$$a_{i+1}=a_i+b_i+c_i,\quad b_{i+1}=b_i+c_i,\quad c_{i+1}=c_i$$Последовательно вычисляем количества состояний для семи пар.
$$(a_1,b_1,c_1)=(1,1,1)\to(3,2,1)\to(6,3,1)\to(10,4,1)\to(15,5,1)\to(21,6,1)\to(28,7,1)$$Общее число наборов равно сумме количества наборов трёх типов для седьмой пары.
$$28+7+1=36$$Где здесь ошибаются
Разрешают состояние $(x_i,y_i)=(1,0)$, хотя из условия $x_i \to (x_{i-1}\land y_i)=1$ при $y_i=0$ следует $x_i=0$.
Забывают, что из условия $y_i \to y_{i-1}=1$ при $y_i=1$ следует $y_{i-1}=1$.
Считают только допустимые состояния последней пары, не учитывая количество способов их получения.