Question

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

$$\begin{align}
(x_1 	o (x_2 \land y_1)) \land (y_1 	o y_2) &= 1 \
(x_2 	o (x_3 \land y_2)) \land (y_2 	o y_3) &= 1 \
&\vdots \
(x_5 	o (x_6 \land y_5)) \land (y_5 	o y_6) &= 1 \
x_6 	o y_6 &= 1
\end{align}$$

Accepted Answer

28

Answer

Идея решения: проанализировать структуру цепочек импликаций для переменных $y$, затем для каждого допустимого набора $y$ подсчитать совместимые наборы $x$.

**Анализ переменных $y$:**

Из условий $y_i 	o y_{i+1} = 1$ для $i = 1, 2, \ldots, 5$ следует, что импликация ложна только при $y_i = 1$ и $y_{i+1} = 0$. Поэтому допустимые наборы $y$ имеют вид: сначала нули, затем единицы (т. е. $0^k 1^{6-k}$ для $k = 0, 1, \ldots, 6$).

Всего 7 допустимых наборов для $y$:
- $000000$
- $000001$
- $000011$
- $000111$
- $001111$
- $011111$
- $111111$

**Анализ переменных $x$ для каждого набора $y$:**

Для каждого уравнения $(x_i 	o (x_{i+1} \land y_i)) = 1$ (при $i = 1, \ldots, 5$) и финального условия $x_6 	o y_6 = 1$:

- Если $y_i = 0$, то $x_i 	o (x_{i+1} \land 0) = 1$ требует $x_i = 0$ (иначе $0 \land 0 = 0$ и импликация $1 	o 0$ ложна). При $x_i = 0$ переменная $x_{i+1}$ может быть любой.
- Если $y_i = 1$, то $x_i 	o (x_{i+1} \land 1) = 1$ требует: либо $x_i = 0$ (тогда $x_{i+1}$ любой), либо $x_i = 1$ (тогда $x_{i+1} = 1$).

Из последнего условия $x_6 	o y_6 = 1$: если $y_6 = 0$, то $x_6 = 0$; если $y_6 = 1$, то $x_6$ может быть любым.

**Подсчёт для каждого набора $y$:**

Обозначим позицию первой единицы в наборе $y$ как $k$ (если все нули, то $k = 7$). Тогда:
- Для позиций $i < k$: $y_i = 0 \Rightarrow x_i = 0$, $x_{i+1}$ свободен.
- Для позиций $i \geq k$: $y_i = 1$, и $x_i$ может быть 0 (тогда $x_{i+1}$ свободен) или 1 (тогда $x_{i+1} = 1$).

Количество допустимых наборов $x$ для каждого $y$:

| Набор $y$ | Позиция первой 1 | Кол-во наборов $x$ |
|---|---|---|
| $000000$ | 7 | 1 |
| $000001$ | 6 | 2 |
| $000011$ | 5 | 3 |
| $000111$ | 4 | 4 |
| $001111$ | 3 | 5 |
| $011111$ | 2 | 6 |
| $111111$ | 1 | 7 |

Общее количество: $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$.

![Рисунок](https://ege.sdamgia.ru/formula/svg/10/10bb84a14ac766daf4d699616c91da96.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/25/25dbced566d76718d875f07703f05181.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/50/506a4f75348dc2613e43e99932dcfef0.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/e6/e65de3fe96324ad630153ab9bab46a3b.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/57/57f4c70e176610002f592f5c5c9e6cb4.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/4e/4eade5d35481dc017c253d79f04499ac.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/58/5848f1251959c18cb6a794979f46900b.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/e2/e2971c4a6e30ba3787871700cc8d4efc.svg)

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