Question

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

$(y_1 	o (y_2 \land x_1)) \land (x_1 	o x_2) = 1$

$(y_2 	o (y_3 \land x_2)) \land (x_2 	o x_3) = 1$

$\ldots$

$(y_6 	o (y_7 \land x_6)) \land (x_6 	o x_7) = 1$

$y_7 	o x_7 = 1$

Accepted Answer

36

Answer

Идея решения: применить метод отображений, анализируя переходы между парами $(x_i, y_i)$ и $(x_{i+1}, y_{i+1})$ на основе условий истинности.

Рассмотрим, какие пары $(x_{i+1}, y_{i+1})$ допустимы для каждой пары $(x_i, y_i)$.

Для пары $(x_i, y_i)$ условие $(y_i 	o (y_{i+1} \land x_i)) \land (x_i 	o x_{i+1}) = 1$ требует:
- $y_i 	o (y_{i+1} \land x_i) = 1$
- $x_i 	o x_{i+1} = 1$

Проанализируем каждый случай:

**Пара $(0, 0)$:** Обе импликации истинны при любых значениях следующей пары. Переход возможен в $(0, 0)$, $(0, 1)$, $(1, 0)$, $(1, 1)$ — 4 варианта.

**Пара $(0, 1)$:** Первая импликация $1 	o (y_{i+1} \land 0)$ требует $y_{i+1} = 0$. Вторая импликация $0 	o x_{i+1}$ всегда истинна. Переход возможен только в $(0, 0)$ — 0 вариантов (так как $y_{i+1} = 0$, но нужно $y_{i+1} \land 0 = 0$, что даёт ложь). Фактически, пара $(0, 1)$ не может быть промежуточной.

**Пара $(1, 0):** Первая импликация $0 	o (y_{i+1} \land 1)$ всегда истинна. Вторая импликация $1 	o x_{i+1}$ требует $x_{i+1} = 1$. Переход возможен в $(1, 0)$ и $(1, 1)$ — 2 варианта.

**Пара $(1, 1):** Первая импликация $1 	o (y_{i+1} \land 1)$ требует $y_{i+1} = 1$. Вторая импликация $1 	o x_{i+1}$ требует $x_{i+1} = 1$. Переход возможен только в $(1, 1)$ — 1 вариант.

Построим таблицу количества путей, заканчивающихся в каждой паре на позиции $i$:

| Пара | Позиция 1 | Позиция 2 | Позиция 3 | Позиция 4 | Позиция 5 | Позиция 6 | Позиция 7 |
|---|---|---|---|---|---|---|---|
| $(0, 0)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| $(0, 1)$ | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| $(1, 0)$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| $(1, 1)$ | 1 | 3 | 6 | 10 | 15 | 21 | 28 |

На позиции 1 все четыре пары возможны (по одному пути каждая).

Для позиции 2:
- $(0, 0)$: из $(0, 0)$ — 1 путь
- $(0, 1)$: из $(0, 0)$ — 1 путь, но условие не позволяет — 0 путей
- $(1, 0)$: из $(0, 0)$ и $(1, 0)$ — 1 + 1 = 2 пути
- $(1, 1)$: из $(0, 0)$, $(1, 0)$ и $(1, 1)$ — 1 + 1 + 1 = 3 пути

Продолжая по правилам переходов, получаем таблицу выше.

Для последней позиции 7 нужно учесть условие $y_7 	o x_7 = 1$:
- $(0, 0)$: $0 	o 0 = 1$ ✓ — 1 путь
- $(0, 1)$: $1 	o 0 = 0$ ✗ — 0 путей
- $(1, 0)$: $0 	o 1 = 1$ ✓ — 7 путей
- $(1, 1)$: $1 	o 1 = 1$ ✓ — 28 путей

Общее количество решений: $1 + 0 + 7 + 28 = 36$.

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

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