Шешімі: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_6, y_1, y_2, \ldots, y_6$, которые удовлетворяют всем перечисленным ниже условиям?
$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_6 \to (x_5 \land y_6)) \land (y_6 \to y_5) = 1$
Шешім по шагам
4 қадамИмпликация $a \to b$ истинна, если $a = 0$ или $b = 1$. Поэтому из условий для каждого $i \geq 2$ следует: если $x_i = 1$, то $x_{i-1} = 1$ и $y_i = 1$; если $y_i = 1$, то $y_{i-1} = 1$.
Следовательно, единицы в каждой последовательности идут только в начале. Последовательность $x$ определяется числом $a$ единиц, а последовательность $y$ — числом $b$ единиц, где $a,b \in \{0,1,\ldots,6\}$.
Условие $x_i = 1 \Rightarrow y_i = 1$ означает, что единиц в последовательности $x$ не больше, чем в последовательности $y$: $a \leq b$.
Число пар $(a,b)$, удовлетворяющих $0 \leq a \leq b \leq 6$, равно числу сочетаний с повторениями: $\binom{7+2-1}{2} = \binom{8}{2} = 28$.
Где здесь ошибаются
Считать переменные независимыми и получить $2^{12}$ нұсқа.
Забыть, что из $x_i \to (x_{i-1} \land y_i)$ следуют сразу два условия.
Не учесть возможность нулевого количества единиц в последовательности.