Сколько различных решений имеет система уравнений

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1
(x2 ˅ x3) ˄ ((x2 ˄ x3) → x4) = 1
(x3 ˅ x4) ˄ ((x3 ˄ x4) → x5) = 1
(x4 ˅ x5) ˄ ((x4 ˄ x5) → x6) = 1
(x5 ˅ x6) ˄ ((x5 ˄ x6) → x7) = 1
(x6 ˅ x7) ˄ ((x6 ˄ x7) → x8) = 1
(x7 ˅ x8) = 1

где x1,x2,…,x8 – логические переменные? В ответе не нужно перечислять все различные  наборы  значений  переменных,  при  которых  выполнено  данное равенство. В качестве ответа нужно указать количество таких наборов.

Решим систему с помощью битовых цепочек. Битовая цепочка — это набор единиц и нулей для переменных x1...x8, при которых система будет истинна.

Цепочки строятся по определенным правилам, которые можно вывести из системы. Рассмотрим первое уравнение:

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1

Для получения истины выражение (x1 ˅ x2) обязательно должно быть истинно, то есть в уравнении не может быть двух подряд идущих нулей.

Кроме этого, выражение ((x1 ˄ x2) → x3) тоже должно быть истинно. Ложным оно будет в том случае, если x1 и x2 будет равны 1, а x3 — 0. То есть после двух подряд идущих единиц не может быть нуля.

Каждое следующее уравнение связано с предыдущим:

(x1 ˅ x2) ˄ ((x1 ˄ x2) → x3) = 1
(x2 ˅ x3) ˄ ((x2 ˄ x3) → x4) = 1

То есть два правила, которые мы вывели, применяются не только к каждому уравнению, но и ко всей цепочке.

Первая очевидная цепочка для набора иксов — все единицы:

x1 1
x2 1
x3 1
x4 1
x5 1
x6 1
x7 1
x8 1

Рассмотрим цепочки, в которых может быть только один нуль. По правилу нуля не может быть после двух единиц:

x1 1 0 1
x2 1 1 0
x3 1 1 1
x4 1 1 1
x5 1 1 1
x6 1 1 1
x7 1 1 1
x8 1 1 1

Рассмотрим цепочки с двумя нулями. По правилу два нуля не могут находиться рядом:

x1 1 0 1 0 1
x2 1 1 0 1 0
x3 1 1 1 0 1
x4 1 1 1 1 0
x5 1 1 1 1 1
x6 1 1 1 1 1
x7 1 1 1 1 1
x8 1 1 1 1 1

Построим оставшиеся цепочки:

x1 1 0 1 0 1 0 1 0 1
x2 1 1 0 1 0 1 0 1 0
x3 1 1 1 0 1 0 1 0 1
x4 1 1 1 1 0 1 0 1 0
x5 1 1 1 1 1 0 1 0 1
x6 1 1 1 1 1 1 0 1 0
x7 1 1 1 1 1 1 1 0 1
x8 1 1 1 1 1 1 1 1 0

Получается, что для данной системы существует 9 различных решений.

Ответ: 9