Сколько существует различных наборов значений логических переменных x1, x2, ..., x6, y1, y2, ..., y6, z1, z2, ..., z6, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) ∧ (x5→ x6) = 1
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1
(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) ∧ (z4→ z5) ∧ (z5 → z6) = 1
x6 ∧ y6 ∧ z6 = 0
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ..., x6, y1, y2, ..., y6, z1, z2, ..., z6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Заметим, что первые три уравнения однотипны. Если последняя переменная (x6, y6 или z6) равна нулю, то предыдущая переменная в данном уравнении тоже должна равняться нулю. Аналогично для всех предыдущих выражений в уравнении: если следствие равно нулю, то посылка также равна нулю, а если следствие равно единице, то посылка либо 0, либо 1. Таким образом, получаем древо решений, которое ветвится в тех случаях, когда следствие равно 1 (см. рис.).
Исходя из структуры дерева, делаем вывод, что количество решений уравнения из пяти выражений равно 6, если последняя переменная равна единице. Если же последняя переменная равна нулю, то имеем единственное решение уравнения.
Из последнего уравнения находим, что возможны семь вариантов значений x6, y6 и z6 (все, кроме 111). Выпишем количество решений для каждой комбинации x6, y6 и z6:
| x6, y6 и z6 | Количество решений |
|---|---|
| 110 | 6 · 6 · 1 = 36 |
| 101 | |
| 011 | |
| 100 | 6 · 1 · 1 = 6 |
| 010 | |
| 001 | |
| 000 | 1 |
Таким образом, система уравнений имеет 3 · 36 + 3 · 6 + 1 = 127 наборов решений.
Ответ: 127.