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