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

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

X₁ → X₂  X₃  ¬X₄ = 1

X₃ → X₄  X₅  ¬X₆ = 1

X₅ → X₆  X₁  ¬X₂ = 1

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

Решение:

1. перепишем уравнения в более простом виде, заменим знаки  и  соответственно на (логические) сложение и умножение:

1. вспомним, что сначала выполняется логическое умножение, потом логические сложение и только потом – импликация, поэтому уравнения можно переписать в виде

1. раскрывая импликацию по формуле , получаем

1. далее замечаем, что , и , поэтому можно ввести новые переменные , и , и переписать уравнения в виде

1. пусть , тогда из первого уравнения сразу имеем и далее из второго ; при этом третье автоматически выполняется; получили одно решение

2. теперь пуст , тогда из последнего уравнения имеем , а из второго – , при этом первое уравнение справедливо

3. таким образом, система уравнений относительно переменных имеет два решения: (0,0,0) и (1,1,1)

4. теперь вернемся обратно к исходным переменным; значению соответствует единственный вариант ; значению соответствуют остальные 3 пары возможных значений

5. то же самое можно сказать про и : нулевое значение дает один набор соответствующих исходных переменных, а единичное – три

6. переменные , и независимы друг от друга, так как каждая из них составлена из разных X-переменных, поэтому Y-решение (0,0,0) (см. п. 7) дает только одно X-решение, а Y-решение (1,1,1) – 3·3·3=27 решений

7. всего решений 1 + 27 = 28.

Решение (метод отображений¹, решение А.Н. Носкина):

1. сначала построим таблицу, в которой переберем все варианты x₁, x₂, x₃, x₄, поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=2⁴); уберем из таблицы (желтая заливка) такие значения x₃, x₄, при которых первое уравнение не имеет решения.

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

(например, паре x₁x₂=10 соответствует только пара x₃x₄ = 10).

Внимание! Для пары x₁x₂ = 10 нет связей x₃x₄ = 00,10 и 11

1. теперь рассмотрим, как влияет на правило отображения третье уравнение. Для этого построим таблицу, в которой переберем все варианты x₁, x₂, x₅, x₆.

Уберем из таблицы (желтая заливка) такие значения x₆, при которых третье уравнение не имеет решения.

Анализ таблицы показывает, что еще исключаются 3 связи, а именно для пары

x₁x₂ = 00 нет связей с x₅x₆ = 10

x₁x₂ = 01 нет связей с x₅x₆ = 10

x₁x₂ = 10 нет связей с x₅x₆ = 10

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

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

   	x1x2	x3x4	x5x6
   00	1	3	9
   01	1	3	9
   10	1	1	1
   11	1	3	9

2. складываем все результаты: 9 + 9 + 1 + 9 = 28.

3. Ответ: 28.

1^ Метод отображений предложен Ел.А. Мирончик и Ек.А. Мирончик (http://kpolyakov.spb.ru/download/b15mirn.zip).