Question

Найти количество различных наборов значений логических переменных $x_1, x_2, \ldots, x_{12}$, удовлетворяющих системе:

$$\begin{align}
\left((x_1 \leftrightarrow x_2) \land (x_3 \leftrightarrow x_4)ight) \lor \left(
eg(x_1 \leftrightarrow x_2) \land 
eg(x_3 \leftrightarrow x_4)ight) &= 0 \
\left((x_3 \leftrightarrow x_4) \land (x_5 \leftrightarrow x_6)ight) \lor \left(
eg(x_3 \leftrightarrow x_4) \land 
eg(x_5 \leftrightarrow x_6)ight) &= 0 \
\left((x_5 \leftrightarrow x_6) \land (x_7 \leftrightarrow x_8)ight) \lor \left(
eg(x_5 \leftrightarrow x_6) \land 
eg(x_7 \leftrightarrow x_8)ight) &= 0 \
\left((x_7 \leftrightarrow x_8) \land (x_9 \leftrightarrow x_{10})ight) \lor \left(
eg(x_7 \leftrightarrow x_8) \land 
eg(x_9 \leftrightarrow x_{10})ight) &= 0 \
\left((x_9 \leftrightarrow x_{10}) \land (x_{11} \leftrightarrow x_{12})ight) \lor \left(
eg(x_9 \leftrightarrow x_{10}) \land 
eg(x_{11} \leftrightarrow x_{12})ight) &= 0
\end{align}$$

Accepted Answer

128

Answer

Идея решения: каждое уравнение связывает две пары переменных через эквиваленцию; уравнения образуют цепь, где каждое следующее уравнение зависит от значения эквиваленции из предыдущего.

Проанализируем структуру одного уравнения. Выражение вида $\left((a \leftrightarrow b) \land (c \leftrightarrow d)ight) \lor \left(
eg(a \leftrightarrow b) \land 
eg(c \leftrightarrow d)ight)$ равно 1 тогда и только тогда, когда $(a \leftrightarrow b)$ и $(c \leftrightarrow d)$ имеют одинаковое значение (оба истинны или оба ложны). Нам нужно, чтобы это выражение равнялось 0, то есть $(a \leftrightarrow b)$ и $(c \leftrightarrow d)$ должны иметь **разные** значения.

**Первое уравнение:** $(x_1 \leftrightarrow x_2)$ и $(x_3 \leftrightarrow x_4)$ должны быть разными.

Построим дерево решений:
- Если $x_1 \leftrightarrow x_2 = 1$ (т. е. $x_1 = x_2$), то $(x_3 \leftrightarrow x_4) = 0$ (т. е. $x_3 
eq x_4$). Это даёт $2 	imes 2 = 4$ набора.
- Если $x_1 \leftrightarrow x_2 = 0$ (т. е. $x_1 
eq x_2$), то $(x_3 \leftrightarrow x_4) = 1$ (т. е. $x_3 = x_4$). Это даёт $2 	imes 2 = 4$ набора.

Итого: 8 решений первого уравнения. При этом $(x_3 \leftrightarrow x_4)$ принимает значение 0 в 4 случаях и значение 1 в 4 случаях.

**Второе уравнение:** $(x_3 \leftrightarrow x_4)$ и $(x_5 \leftrightarrow x_6)$ должны быть разными.

Для каждого значения $(x_3 \leftrightarrow x_4)$ из первого уравнения:
- Если $(x_3 \leftrightarrow x_4) = 0$, то $(x_5 \leftrightarrow x_6) = 1$, что даёт 2 набора для $(x_5, x_6)$.
- Если $(x_3 \leftrightarrow x_4) = 1$, то $(x_5 \leftrightarrow x_6) = 0$, что даёт 2 набора для $(x_5, x_6)$.

Система из двух уравнений: $4 	imes 2 + 4 	imes 2 = 16$ решений. При этом $(x_5 \leftrightarrow x_6)$ принимает значение 0 в 8 случаях и значение 1 в 8 случаях.

**Третье уравнение:** $(x_5 \leftrightarrow x_6)$ и $(x_7 \leftrightarrow x_8)$ должны быть разными.

Аналогично: $8 	imes 2 + 8 	imes 2 = 32$ решения. При этом $(x_7 \leftrightarrow x_8)$ принимает значение 0 в 16 случаях и значение 1 в 16 случаях.

**Четвёртое уравнение:** $16 	imes 2 + 16 	imes 2 = 64$ решения.

**Пятое уравнение:** $32 	imes 2 + 32 	imes 2 = 128$ решений.

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=10760)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=10762)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=10763)

Задание №23Алгоритмы и исполнителиЕГЭ по информатике