Задание: Сколько различных решений имеет система уравнений
(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