Решение: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_6, y_1, y_2, \ldots, y_6$, удовлетворяющих условиям: для каждого $i=1,2,\ldots,5$ выполняется $((x_i \equiv y_i) \to (x_{i+1} \equiv y_{i+1})) \land (x_i \lor y_i)=1$, а также $x_6 \lor y_6=1$?
Укажите количество таких наборов.
Решение по шагам
6 шаговИз условия $x_i \lor y_i=1$ каждая пара $(x_i,y_i)$ может быть одной из трёх: $(0,1)$, $(1,0)$ или $(1,1)$.
Для пар $(0,1)$ и $(1,0)$ значение $x_i \equiv y_i$ равно 0, а для пары $(1,1)$ — 1.
Импликация $((x_i \equiv y_i) \to (x_{i+1} \equiv y_{i+1}))$ запрещает только переход от пары с эквивалентностью 1 к паре с эквивалентностью 0. Поэтому после появления $(1,1)$ все последующие пары также должны быть $(1,1)$.
Если пары $(1,1)$ нет, то на каждой из шести позиций есть 2 варианта: $2^6=64$.
Если первая пара $(1,1)$ стоит на позиции $k$, то до неё можно выбрать пары $(0,1)$ или $(1,0)$: $2^{k-1}$ вариантов. После неё все пары однозначно равны $(1,1)$.
Суммарное количество наборов равно $2^6+\sum_{k=1}^{6}2^{k-1}=64+(1+2+4+8+16+32)=127$.
Где здесь ошибаются
Считать пару $(0,0)$ допустимой, хотя она нарушает условие $x_i \lor y_i=1$.
Разрешить переход от $(1,1)$ к $(0,1)$ или $(1,0)$.
Не учитывать случай, когда пара $(1,1)$ вообще не встречается.