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

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

(X₂  X₁)  (X₂  X₃)  (¬X₂ ¬ X₃)= 1

(X₃  X₁)  (X₃  X₄)  (¬X₃ ¬ X₄)= 1

...

(X₉  X₁)  (X₉  X₁₀)  (¬X₉ ¬ X₁₀)= 1

(X₁₀  X₁) = 0

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

Решение (табличный метод):

1. количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2. перепишем уравнения, используя более простые обозначения операций

...

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

...

1. первое уравнение выполняется, когда есть X₂ равно X₁ или X₃

2. по таблице истинности находим 6 вариантов (для удобства мы будем записывать сначала столбец для X₁, а потом для всех остальных в обратном порядке):

обратите внимание, что в каждой строчке в первых двух столбцах должно быть по крайней мере одно значение, равное значению в третьем столбце (который выделен желтым)

1. добавим еще одно уравнение и еще одну переменную X­₄:

   X1	X4	X3	X2
   0	?	0	0
   0	?	1	0
   0	?	1	1
   1	?	0	0
   1	?	0	1
   1	?	1	1

2. чтобы «подключить» второе уравнение, нужно использовать то же самое правило: каждой строчке в первых двух столбцах должно быть, по крайней мере, одно значение, равное значению в третьем столбце (который выделен желтым); это значит, что в первой и последней строчках (где X­₁ = X₃) значение X₄ может быть любое (0 или 1), а в остальных строчках – только строго определенное:

   X1	X4	X3	X2
   0	0	0	0
   0	1	0	0
   0	1	1	0
   0	1	1	1
   1	0	0	0
   1	0	0	1
   1	0	1	1
   1	1	1	1

3. таким образом, количество решений при подключении очередного уравнения к системе возрастает на 2!

4. подключили X₅ – получили 10 решений, X₆ – получили 12 решений, X₇ – получили 14 решений, X₈ – получили 16 решений, X₉ – получили 18 решений, X₁₀ – получили 20 решений.

5. остается одно последнее уравнение (X₁₀  X₁) = 0, из которого следует, что X₁₀ не равен X­₁

6. из таблицы следует, что только в первой и последней строчках значения первой и последней переменных совпадают, то есть из полученных 20 решений нужно отбросить 2

7. таким образом, получается 20 – 2 = 18 решений

8. ответ: 18 решений