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

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

X₁ → X₂ → X₃ → X₄ → X₅ → X₆ = 1

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

Решение (вариант 1, табличный метод, динамическое программирование):

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

2. операции, имеющие одинаковый приоритет, выполняются слева направо, то есть первой выполняется импликация X₁ → X₂, а последней – последняя импликация

((((X₁ → X₂) → X₃) → X₄) → X₅) → X₆

1. каждая логическая переменная может принимать значение «истина» (1) или «ложь» (0)

2. для набора из 6 независимых логических переменных существует 2⁶ =64 разных комбинаций значений этих переменных

3. рассмотрим первую импликацию, X₁ → X₂; она дает в трёх случаях 1, и в одном – 0:

   X1	X2	X1 → X2
   0	0	1
   0	1	1
   1	0	0
   1	1	1

4. посмотрим, как меняется количество решений, если «подключить» следующую переменную;

• если X₁=0, то X₁ → X₂ =1 (из нулей получаются единиц)

• если X₁=1, то X₁ → X₂ =0 при X₂ =0 и X₁ → X₂ =1 при X₂ =1 (из единиц получаются нулей и единиц)

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

,

1. для одной переменной имеем 1 ноль и 1 единицу, поэтому начальные условия для расчёта:

1. составим таблицу, которую будем заполнять слева направо, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец таблицы для :

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

Решение (вариант 2, «с хвоста»):

1. те же рассуждения, что и в п. 1-4 решения по варианту 1

2. если X₆ =1, то левая часть уравнения равна 1, то есть равенство выполняется; комбинаций с X₆ =1 ровно половина от общего количества, то есть 32

3. теперь проверяем варианты с X₆ =0; сразу получаем, что для выполнения заданного уравнения нужно, чтобы (X₁ → X₂ → X₃ → X₄ → X₅)=0; иначе получим 1 → X₆ = 1 →0 = 0

4. проверим отдельно случаи X₅ =0 и X₅ =1

5. пусть X₆ = 0 и X₅ =1; в этом случае никогда не будет выполнено условие
   (X₁ → X₂ → X₃ → X₄ → X₅)=0, решений нет

6. пусть X₆ = X₅ =0; в этом случае условие (X₁ → X₂ → X₃ → X₄ → X₅)=0 выполняется только при (X₁ → X₂ → X₃ → X₄)=1; если X₄ =1, это условие всегда верно, поэтому получаем еще 8 решений – 8 комбинаций, где X₆ = X₅ =0 и X₄ =1 (1/8 всех комбинаций)

7. теперь рассмотрим случаи, когда X₆ = X₅ = X₄ =0; рассуждая аналогично, находим, что условие (X₁ → X₂ → X₃ → 0)=1 верно при (X₁ → X₂ → X₃)=0, это сразу дает X₃ =0 и
   (X₁ → X₂)=1

8. при всех известных значениях остальных переменных (X₆ = X₅ = X₄ = X₃ =0) условие
   (X₁ → X₂)=1 истинно в трёх случаях: (X₁,X­₂) =(0,0) , (0,1) и (1,1), это дает еще 3 решения

9. таким образом, ответ: 32 + 8 + 3 = 43 решения.

Решение (вариант 3, приведение к базису «И-ИЛИ-НЕ», Е.Н. Смирнова):

1. те же рассуждения, что и в п. 1-4 решения по варианту 1

2. заменяем импликацию по формуле ; на первом шаге получаем

1. далее по той же формуле

инверсию в первом слагаемом раскроем по закону де Моргана ( ):

1. сделав те же операции с оставшейся скобкой, получаем

1. и, применяя ту же формулу еще раз, получим уравнение

1. при остальные 5 переменных можно выбирать любым способом, это дает 2⁵ = 32 решения4⁴⁴⁴⁴⁴⁴

2. при и решений нет

3. при получаем 2³ = 8 решений при (можно выбирать , и произвольно)

4. при сразу находим, что , это дает еще 3 решения, при которых истинно выражение

5. таким образом, ответ: 32 + 8 + 3 = 43 решения.