Question

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

$$((x_1 \equiv x_2) \lor (x_3 \equiv x_4)) \land (
eg(x_1 \equiv x_2) \lor 
eg(x_3 \equiv x_4)) = 1$$

$$((x_3 \equiv x_4) \lor (x_5 \equiv x_6)) \land (
eg(x_3 \equiv x_4) \lor 
eg(x_5 \equiv x_6)) = 1$$

$$((x_5 \equiv x_6) \lor (x_7 \equiv x_8)) \land (
eg(x_5 \equiv x_6) \lor 
eg(x_7 \equiv x_8)) = 1$$

Accepted Answer

32

Answer

Идея решения: каждое уравнение имеет структуру $(A \lor B) \land (
eg A \lor 
eg B)$, что эквивалентно исключающему ИЛИ ($A \oplus B = 1$), то есть ровно одно из выражений должно быть истинно. Уравнения связаны через общие переменные, поэтому подсчитаем решения пошагово.

**Анализ одного уравнения**

Выражение $(A \lor B) \land (
eg A \lor 
eg B)$ истинно, когда $A$ и $B$ имеют разные значения (исключающее ИЛИ).

Для первого уравнения $(x_1 \equiv x_2) \oplus (x_3 \equiv x_4) = 1$:
- Выражение $(x_1 \equiv x_2)$ принимает значение 1 при $(x_1, x_2) \in \{(0,0), (1,1)\}$ — 2 варианта.
- Выражение $(x_1 \equiv x_2)$ принимает значение 0 при $(x_1, x_2) \in \{(0,1), (1,0)\}$ — 2 варианта.
- Аналогично для $(x_3 \equiv x_4)$ — 2 варианта при значении 1 и 2 варианта при значении 0.

Условие $A \oplus B = 1$ означает:
- либо $A = 1, B = 0$: 2 × 2 = 4 набора,
- либо $A = 0, B = 1$: 2 × 2 = 4 набора.

Итого: **8 решений** первого уравнения.

При этом $(x_3 \equiv x_4)$ принимает значение 0 в 4 наборах и значение 1 в 4 наборах.

**Система двух уравнений**

Второе уравнение $(x_3 \equiv x_4) \oplus (x_5 \equiv x_6) = 1$ связано с первым через $(x_3 \equiv x_4)$.

Для каждого значения $(x_3 \equiv x_4)$ (0 или 1):
- Если $(x_3 \equiv x_4) = 0$, то $(x_5 \equiv x_6)$ должно быть 1 → 2 × 2 = 4 набора $(x_5, x_6)$.
- Если $(x_3 \equiv x_4) = 1$, то $(x_5 \equiv x_6)$ должно быть 0 → 2 × 2 = 4 набора $(x_5, x_6)$.

В обоих случаях получаем 4 набора для $(x_5, x_6)$.

Первое уравнение даёт 8 наборов $(x_1, x_2, x_3, x_4)$, второе добавляет 4 набора $(x_5, x_6)$ для каждого значения $(x_3 \equiv x_4)$.

Система двух уравнений: $8 	imes 4 = 32$ решения.

При этом $(x_5 \equiv x_6)$ принимает значение 0 в половине наборов (16) и значение 1 в половине наборов (16).

**Система трёх уравнений**

Третье уравнение $(x_5 \equiv x_6) \oplus (x_7 \equiv x_8) = 1$ связано со второй системой через $(x_5 \equiv x_6)$.

Для каждого значения $(x_5 \equiv x_6)$ (0 или 1):
- Если $(x_5 \equiv x_6) = 0$, то $(x_7 \equiv x_8)$ должно быть 1 → 4 набора $(x_7, x_8)$.
- Если $(x_5 \equiv x_6) = 1$, то $(x_7 \equiv x_8)$ должно быть 0 → 4 набора $(x_7, x_8)$.

Система двух уравнений даёт 32 набора, третье добавляет 4 набора $(x_7, x_8)$ для каждого значения $(x_5 \equiv x_6)$.

Система трёх уравнений: $32 	imes 4 = 128$ решений.

Однако нужно учесть, что $(x_5 \equiv x_6)$ в 32 наборах распределяется поровну: 16 раз равно 0 и 16 раз равно 1. Для каждого случая добавляется 4 набора, итого $16 	imes 4 + 16 	imes 4 = 128$.

Пересчитаем внимательнее: из 32 решений второй системы в 16 случаях $(x_5 \equiv x_6) = 0$ (добавляем 4 набора с $(x_7 \equiv x_8) = 1$) и в 16 случаях $(x_5 \equiv x_6) = 1$ (добавляем 4 набора с $(x_7 \equiv x_8) = 0$).

Получаем: $16 	imes 4 + 16 	imes 4 = 32 	imes 2 = 64$ решения.

Проверим логику ещё раз: каждое уравнение вида $A \oplus B = 1$ имеет 8 решений (4 при $A=0, B=1$ и 4 при $A=1, B=0$). Три независимых пары переменных $(x_1, x_2)$, $(x_3, x_4)$, $(x_5, x_6)$, $(x_7, x_8)$ дают $2^4 = 16$ комбинаций для эквивалентностей. Условие $A \oplus B = 1$ выполняется для половины: $16 / 2 = 8$ комбинаций на первое уравнение, затем $8 	imes 4 = 32$ на две, затем $32 	imes 2 = 64$...

Пересчитаем по-другому: каждое уравнение требует, чтобы ровно одно из двух выражений эквивалентности было истинно. Для трёх уравнений с четырьмя парами переменных: $2^4 	imes (1/2)^3 = 16 	imes 1/8 = 2$... Это не совпадает.

Вернёмся к исходному подходу: первое уравнение — 8 решений. Второе уравнение для каждого значения $(x_3 \equiv x_4)$ добавляет 4 решения → $8 	imes 4 / 2 = 16$. Третье уравнение для каждого значения $(x_5 \equiv x_6)$ добавляет 4 решения → $16 	imes 4 / 2 = 32$.

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

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

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

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