Question

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

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

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

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

В ответе укажите количество таких наборов.

Accepted Answer

121

Answer

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

Обозначим:
- $y_1 = x_1 \lor 
eg x_2$
- $y_2 = x_3 \lor 
eg x_4$
- $y_3 = x_5 \lor 
eg x_6$
- $y_4 = x_7 \lor 
eg x_8$

Система принимает вид:
$$y_1 	o y_2 = 1, \quad y_2 	o y_3 = 1, \quad y_3 	o y_4 = 1$$

Импликация $a 	o b$ ложна только при $a = 1, b = 0$. Цепочка трёх импликаций истинна, если не встречается переход «$1 	o 0$». Это означает, что последовательность $y_1, y_2, y_3, y_4$ имеет вид: сначала нули (возможно, их нет), затем единицы (возможно, их нет).

Допустимые последовательности $(y_1, y_2, y_3, y_4)$:
- $(0, 0, 0, 0)$ — 1 вариант
- $(0, 0, 0, 1)$ — 1 вариант
- $(0, 0, 1, 1)$ — 1 вариант
- $(0, 1, 1, 1)$ — 1 вариант
- $(1, 1, 1, 1)$ — 1 вариант

Итого 5 допустимых последовательностей.

Для каждой переменной $y_i$ подсчитаем количество пар $(x_{2i-1}, x_{2i})$, дающих нужное значение:

Для $y = x_1 \lor 
eg x_2$:
- $y = 0$: нужно $x_1 = 0$ и $x_2 = 1$ → 1 пара
- $y = 1$: остальные 3 пары $(0,0), (1,0), (1,1)$ → 3 пары

Аналогично для $y_2, y_3, y_4$.

Подсчитаем количество наборов для каждой последовательности:

| $(y_1, y_2, y_3, y_4)$ | Количество наборов |
|---|---|
| $(0, 0, 0, 0)$ | $1 	imes 1 	imes 1 	imes 1 = 1$ |
| $(0, 0, 0, 1)$ | $1 	imes 1 	imes 1 	imes 3 = 3$ |
| $(0, 0, 1, 1)$ | $1 	imes 1 	imes 3 	imes 3 = 9$ |
| $(0, 1, 1, 1)$ | $1 	imes 3 	imes 3 	imes 3 = 27$ |
| $(1, 1, 1, 1)$ | $3 	imes 3 	imes 3 	imes 3 = 81$ |

Сумма: $1 + 3 + 9 + 27 + 81 = 121$.

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