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

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

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

(X₂  X₃)  (¬X₂  ¬X₃)  (X₃  X₄)  (¬X₃  ¬X₄) = 1

...

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

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

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

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

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

...

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

...

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

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

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

3. очевидно, что в первой и последней строчках таблицы, где , значения X₃ могут быть любыми, то есть каждая из этих строчек дает два решения; в то же время во второй и третьей строках, где , мы сразу получаем, что для выполнения первого равнения необходимо , то есть, эти две строчки дают по одному решению:

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

4. заметим, что количество решений для каждой строчки исходной таблицы (с двумя переменными) определялось лишь тем, равны значения в двух последних столбцах (X₂ и X₁) или не равны;

5. переставим строки так, чтобы сверху стояли те строки, в которых X₂ = X₃:

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

6. также заметим, что в новой таблице в четырех строках значения X₂ = X₃, а в остальных 2-х эти переменные не равны;

7. поэтому на следующем шаге (при подключении четвертой переменной и третьего уравнения) 4 первые строки дадут по 2 варианта (всего 4·2=8) решений, из них 4 штуки с равными X­₄ и X₃, и 4 варианта, где X­₄ и X₃ не равны

8. две нижние строки, где X₂  X₃, дадут 2 варианта, где X­₄ и X₃ равны

9. в общем виде: если на шаге i в таблице решений есть

n_i строк, где значения в двух самых левых столбцах таблицы равны, и …

m_i строк, где значения в двух самых левых столбцах таблицы не равны,

то на следующем шаге будет (n_i+m_i) строк с равными значения в двух самых последних столбцах и n_i строк с неравными значениями

1. эту последовательность можно записать в виде таблицы (i – число задействованных переменных):

   i			всего решений
   3	4	2	6
   4	4 +2=6	4	10
   5	6+4=10	6	16
   6	10+6=16	10	26
   7	16+10=26	16	42
   8	26+16=42	26	68
   9	42+26=68	42	110
   10	68+42=110	68	178

2. таким образом, для системы с 10 переменными общее количество решений равно
   110 + 68 = 178

3. ответ: 178 решений

Решение (использование дерева для представления решения):

1. идея представления множества решений в виде дерева использовалась, например, в решениях О.А. Тузовой (Санкт-Петербург, школа № 550) и М.В. Демидовой (г. Пермь, гимназия №17); как верно отметила О.А. Тузова, предложенный выше табличный метод по сути представляет собой компактную запись дерева

2. так же, как и в предыдущем варианте решения, перейдем к равносильной системе уравнений

...

1. все переменные логические, в принятых обозначениях каждая из них может быть равна 1 или 0; для X₁ получаем два варианта, которые можно представить в виде

1. при этом X­₂ может быть любым, то есть, имеем всего 4 варианта

1. теперь рассматриваем переменную X₃; если X₁ = X₂, то уравнение выполняется при любом X₃; если X₁  X₂, то это уравнение сразу дает X₃ = X₂; дерево получается уже неполным, число решений первого уравнения – 6:

1. рассуждая аналогично, находим, что на следующем шаге (подключение переменной X₄ и второго уравнения) получается 10 решений, затем – 16 и т.д.; в результате получается удвоенная последовательность Фибоначчи (2, 4, 6, 10, 16, 26, …), в которой каждый следующий элемент равен сумме двух предыдущих:

   i	число решений
   3	6
   4	10
   5	16
   6	26
   7	42
   8	68
   9	110
   10	178

2. в некоторых вариантах такой подход рассматривался совместно с методом декомпозиции: сначала предполагаем, что X₁ = 0 и находим все решения для этого варианта; затем находим все решения при X₁ = 1; после этого общее количество решений вычисляется как сумма полученных двух чисел

3. ответ: 178 решений