Question

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

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

$(
eg y_1 \lor y_2) \land (
eg y_2 \lor y_3) \land (
eg y_3 \lor y_4) = 1$

$(y_1 	o x_1) \land (y_2 	o x_2) \land (y_3 	o x_3) \land (y_4 	o x_4) = 1$

Accepted Answer

15

Answer

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

**Анализ первого условия.**

Цепочка импликаций $(x_1 	o x_2) \land (x_2 	o x_3) \land (x_3 	o x_4) = 1$ истинна, когда нет перехода вида $1 	o 0$. Это означает, что как только встречается единица, все последующие переменные должны быть единицами. Допустимые наборы для $(x_1, x_2, x_3, x_4)$:
- $0000$
- $0001$
- $0011$
- $0111$
- $1111$

Всего 5 наборов.

**Анализ второго условия.**

Преобразуем $(
eg y_1 \lor y_2) \land (
eg y_2 \lor y_3) \land (
eg y_3 \lor y_4) = 1$.

Каждый дизъюнкт $
eg y_i \lor y_{i+1}$ эквивалентен импликации $y_i 	o y_{i+1}$. Таким образом, второе условие имеет ту же структуру, что и первое. Допустимые наборы для $(y_1, y_2, y_3, y_4)$:
- $0000$
- $0001$
- $0011$
- $0111$
- $1111$

Всего 5 наборов.

**Анализ третьего условия.**

Условие $(y_1 	o x_1) \land (y_2 	o x_2) \land (y_3 	o x_3) \land (y_4 	o x_4) = 1$ означает, что для каждого $i$ импликация $y_i 	o x_i$ истинна. Это верно, когда $y_i = 0$ или $x_i = 1$ (или оба). Иными словами, если $y_i = 1$, то обязательно $x_i = 1$.

**Подсчёт совместимых пар.**

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

- $x = 0000$: $y$ может быть только $0000$ (так как $y_i = 1$ требует $x_i = 1$). Количество: 1.
- $x = 0001$: $y_1 = y_2 = y_3 = 0$, $y_4 \in \{0, 1\}$. Допустимые $y$: $0000, 0001$. Количество: 2.
- $x = 0011$: $y_1 = y_2 = 0$, $y_3, y_4 \in \{0, 1\}$ с условием $y_3 	o y_4$. Допустимые $y$: $0000, 0001, 0011$. Количество: 3.
- $x = 0111$: $y_1 = 0$, $y_2, y_3, y_4 \in \{0, 1\}$ с условием цепочки. Допустимые $y$: $0000, 0001, 0011, 0111$. Количество: 4.
- $x = 1111$: $y_1, y_2, y_3, y_4 \in \{0, 1\}$ с условием цепочки. Допустимые $y$: $0000, 0001, 0011, 0111, 1111$. Количество: 5.

Общее количество наборов: $1 + 2 + 3 + 4 + 5 = 15$.

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