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

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

(x₁  x₂)  (x₃  x₄) = 1

(x₃  x₄)  (x₅  x₆) = 1

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

Решение (метод замены переменных):

1. используем замену переменных (заметим, что каждая из новых переменных независима от других, это важно!):

Y₁ = x₁  x₂, Y₂ = x₃  x₄, Y₃ = x₅  x₆

тогда система запишется в виде

Y₁  Y­₂ = 1

Y₂  Y­₃ = 1

1. можно объединить эти уравнения в одно

(Y₁  Y­₂)  (Y₂  Y­₃) = 1

для того, чтобы это равенство было выполнено, ни одно из импликаций не должна быть ложной, то есть в битовой цепочке, составленной из значений переменных Y₁, Y­₂, Y­₃, не должно быть последовательности «10»; вот все возможные варианты:

1. теперь вернемся к исходным переменным; импликация x₁  x₂ дает 0 при одном наборе исходных переменных (x₁,x₂) = (1,0) и 1 при трёх наборах (x₁,x₂) = {(0,0), (0,1), (1,1)}

2. учитывая, что каждая из новых переменных Y₁, Y­₂, Y­₃, независима от других; для каждой строки полученной таблицы просто перемножаем количество вариантов комбинация исходных переменных:

   Y1	Y2	Y3	вариантов
   0	0	0	1*1*1=1
   0	0	1	1*1*3=3
   0	1	1	1*3*3=9
   1	1	1	3*3*3=27

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

4. Ответ: 40.

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

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

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

(например паре x₁x₂=00 соответствуют пары x₃x₄ = 00,01 и 11).

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

   	x1x2	x3x4	x5x6
   00	1	4	13
   01	1	4	13
   10	1	1	1
   11	1	4	13

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

3. Ответ: 40.