Решение: Подсчёт наборов логических переменных
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным ниже условиям?
$(\neg x_1 \lor y_1) \to (\neg x_2 \land y_2) = 1$
$(\neg x_2 \lor y_2) \to (\neg x_3 \land y_3) = 1$
$\ldots$
$(\neg x_6 \lor y_6) \to (\neg x_7 \land y_7) = 1$
Решение по шагам
5 шаговРассмотрим каждую пару $(x_i, y_i)$ как одно состояние. Выражение $\neg x_i \lor y_i$ ложно только в состоянии $(1, 0)$.
Выражение $\neg x_{i+1} \land y_{i+1}$ истинно только в состоянии $(0, 1)$. Импликация нарушается, когда её левая часть истинна, а правая ложна.
Следовательно, из любого состояния, кроме $(1, 0)$, можно перейти только в $(0, 1)$. Из состояния $(1, 0)$ разрешены все четыре перехода.
Для первой пары существует $4$ состояния. Число наборов, заканчивающихся состоянием $(1, 0)$, после первого шага равно $1$ и далее остаётся равным $1. При добавлении каждой следующей пары общее число наборов увеличивается на $3$.
Для семи пар получаем:
$$4 + 6 \cdot 3 = 22$$Где здесь ошибаются
Считать запрещённым только переход из состояния $(1, 0)$, не учитывая все остальные состояния.
Забыть, что импликация ложна только при истинной левой части и ложной правой части.
Умножить число вариантов каждой пары независимо, не учитывая связи между соседними парами.