28.7.Ещё пример задания

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

(¬X₁  X₂)  (¬X₂  X₃)  (¬X₃  X₄)  (¬X₄  X₅)  (¬X₅  X₆) = 1

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

Решение:

1. перепишем уравнение, заменив знаки логических операций:

1. учитывая, что , заменяем все выражения в скобках на импликацию:

1. решение уравнения можно записать в виде шести двоичных знаков, которые обозначают соответственно, переменные

2. далее вспомним, что импликация дает ложное значение, если её первая часть (посылка) истинна, а вторая (следствие) ложно, поэтому из сразу следует, что

3. это значит, что в исходном выражении появится нуль, если в цепочке битов, соответствующей значениям переменных, появится комбинация 10, то есть предыдущее значение истинно, а следующее за ним – ложно

4. поэтому решениями этого уравнения будут все комбинации значений переменных, для которых в соответствующей битовой цепочке нет последовательности 10;

5. таких цепочек всего 7:

000000, 000001, 000011, 000111, 001111, 011111, 111111

1. таким образом, ответ: 7 решений.