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