Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∧ x2) ∨ (¬x1 ∧ ¬x2) ∨ (x2 ∧ ¬x3) ∨ (¬x2 ∧ x3) = 1
(x2 ∧ x3) ∨ (¬x2 ∧ ¬x3) ∨ (x3 ∧ ¬x4) ∨ (¬x3 ∧ x4) = 1
...
(x8 ∧ x9) ∨ (¬x8 ∧ ¬x9) ∨ (x9 ∧ ¬x10) ∨ (¬x9 ∧ x10) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений для первого уравнения.
Таким образом, первое уравнение имеет 6 решений.
Второе уравнение связано с первым только через переменные x2 и x3. На основании древа решений для первого уравнения выпишем пары значений переменных x2 и x3, которые удовлетворяют первому уравнению и укажем количество таких пар значений.
| Количество пар значений | x2 | x3 |
|---|---|---|
| ×1 | 1 | 1 |
| ×1 | 0 | 0 |
| ×2 | 1 | 0 |
| ×2 | 0 | 1 |
Поскольку уравнения идентичны с точностью до индексов переменных, древо решений второго уравнения аналогично первому. Следовательно, пара значений x2 = 1 и x3 = 0 порождает один набор переменных x2, ..., x4, удовлетворяющих второму уравнению. Поскольку среди наборов решений первого уравнения данных пар две, всего получаем 2 · 1 = 2 набора переменных x1, ..., x4, удовлетворяющих системе из двух уравнений. Рассуждая аналогично для пары значений x2 = 0 и x3 = 1, получаем 2 набора переменных x1, ..., x4. Пара x2 = 1 и x3 = 1 порождает два решения второго уравнения. Поскольку среди наборов решений первого уравнения данных пар две, получаем 2 · 1 = 2 набора переменных x1, ..., x4, удовлетворяющих системе из двух уравнений. Аналогично для x2 = 0 и x3 = 0 — 2 набора решений. Всего система из двух уравнений имеет 2 + 2 + 2 + 2 = 8 решений.
Проведя аналогичные рассуждения для системы из трёх уравнений, получаем 10 наборов переменных x1, ..., x5, удовлетворяющих системе. Для системы из четырёх уравнений существует 12 наборов переменных x1, ..., x6, удовлетворяющих системе. Система из восьми уравнений имеет 20 решений.
Ответ: 20.