Question

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

$$
(x_1 	o x_2) \land (x_2 	o x_3) \land (x_3 	o x_4) \land (x_4 	o x_5) \land (x_5 	o x_6) = 1
$$

$$
(y_1 	o y_2) \land (y_2 	o y_3) \land (y_3 	o y_4) \land (y_4 	o y_5) \land (y_5 	o y_6) = 1
$$

$$
(
eg x_1 \lor y_1) \land (
eg x_2 \lor y_2) \land (
eg x_3 \lor y_3) \land (
eg x_4 \lor y_4) \land (
eg x_5 \lor y_5) \land (
eg x_6 \lor y_6) = 1
$$

Accepted Answer

28

Answer

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

**Анализ первого уравнения (цепочка импликаций для $x$):**

Импликация $a 	o b$ ложна только при $a = 1$ и $b = 0$. Для цепочки $(x_1 	o x_2) \land (x_2 	o x_3) \land \ldots \land (x_5 	o x_6)$ быть истинной, недопустимо, чтобы в последовательности встречалась пара $(1, 0)$. Это означает, что после первой единицы все последующие переменные должны быть единицами.

Допустимые наборы для $x_1, \ldots, x_6$: $000000$, $100000$, $110000$, $111000$, $111100$, $111110$, $111111$ — всего **7 наборов**.

**Анализ второго уравнения (цепочка импликаций для $y$):**

По той же логике допустимые наборы для $y_1, \ldots, y_6$: $000000$, $100000$, $110000$, $111000$, $111100$, $111110$, $111111$ — всего **7 наборов**.

**Анализ третьего уравнения (связь между $x$ и $y$):**

Условие $(
eg x_i \lor y_i) = 1$ для каждой позиции $i$ означает, что пара $(x_i, y_i)$ не может быть $(1, 0)$. Допустимые пары: $(0, 0)$, $(0, 1)$, $(1, 1)$.

Следствие: если $y_i = 0$, то обязательно $x_i = 0$.

**Подсчёт совместимых наборов:**

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

Набор $y$ имеет вид: $k$ нулей, затем $6 - k$ единиц (где $k = 0, 1, \ldots, 6$).

Для такого $y$:
- На первых $k$ позициях (где $y_i = 0$) требуется $x_i = 0$.
- На последних $6 - k$ позициях (где $y_i = 1$) переменная $x_i$ может быть $0$ или $1$, но с ограничением цепочки импликаций.

Допустимые наборы $x$ при условии, что первые $k$ позиций равны $0$: это наборы вида $0^k 1^j 0^{6-k-j}$ для $j = 0, 1, \ldots, 6 - k$. Таких наборов $6 - k + 1$.

Суммируя по всем 7 допустимым наборам $y$ (соответствующим $k = 0, 1, \ldots, 6$):

$$
\sum_{k=0}^{6} (6 - k + 1) = 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
$$

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

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

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