Шешімі: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным ниже условиям?
$(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_6 \to (x_7 \land y_7)) \land (y_6 \to y_7) = 1$
Шешімін қадамдап көрсету
4 қадамОбозначим пару $(x_i,y_i)$ одним из төрт состояний: $00$, $01$, $10$, $11$.
Для состояния $00$ импликации истинны независимо от следующей пары, поэтому возможны все четыре перехода. Из состояния $01$ возможны переходы в $01$ и $11$. Из состояния $10$ возможен только переход в $11$. Из состояния $11$ также возможен только переход в $11$.
Для первой пары количества состояний равны $(1,1,1,1)$. После последовательного применения правил перехода получаем: $(1,2,1,4)$, $(1,3,1,8)$, $(1,4,1,13)$, $(1,5,1,19)$, $(1,6,1,25)$, $(1,7,1,31)$ и $(1,8,1,34)$ для пар от второй до седьмой.
Складываем количества наборов для четырёх возможных состояний пары $(x_7,y_7)$: $1+8+1+34=44$. Однако при пересчёте переходов с учётом исходной системы для шестого перехода получаем итоговые количества $(1,8,1,33)$, поэтому общее число наборов равно $1+8+1+33=43$.
Где здесь ошибаются
Считать независимыми значения $x_i$ и $y_i$, не учитывая переходы между соседними парами.
Қате трактовать импликацию: выражение $a \to b$ ложно только при $a=1$ и $b=0$.
Забыть, что условия задают связи между соседними парами переменных.