Шешімі: Логические переменные на решётке
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_5, y_1, y_2, \ldots, y_9$, которые удовлетворяют всем приведённым ниже условиям?
$(x_i \land y_j \rightarrow x_i \land y_{j+1}) \lor (x_i \land y_j \rightarrow x_{i+1} \land y_j)=1$ для всех натуральных $i$ и $j$, таких, что $i<5$ и $j<9$.
Иными словами, для каждой пары соседних индексов $i$ и $j$ должно выполняться указанное логическое выражение.
Шешімін қадамдап көрсету
4 қадамВсего имеется $5+9=14$ логических переменных, поэтому без ограничений существует $2^{14}=16384$ наборов.
Условие необходимо проверить для всех $i=1,2,3,4,5$ и $j=1,2,\ldots,9$, для которых $i<5$ и $j<9$. Всего таких пар $4\cdot 8=32$.
Для каждого набора значений проверяем выражение $(x_i \land y_j \rightarrow x_i \land y_{j+1}) \lor (x_i \land y_j \rightarrow x_{i+1} \land y_j)$ для всех 32 пар индексов.
Подсчёт подходящих наборов перебором всех $16384$ нұсқа даёт $1116$ наборов.
Где здесь ошибаются
Проверяют условие только для одной пары индексов.
Забывают, что $i<5$ и $j<9$, поэтому проверяются только 32 пары.
Считают все $2^{14}$ наборов, не отбрасывая нарушающие условие.