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

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

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

¬(X₃  X₄)  (X₅  X₆) = 1

¬(X₅  X₆)  (X₇  X₈) = 1

¬(X₇  X₈)  (X₉  X₁₀) = 1

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

Решение:

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

2. заметим, что при обозначениях , , , и мы получаем систему из 4 уравнений и 5 независимыми переменными; эта система уравнений относится к типу, который рассмотрен в предыдущей разобранной задаче:

¬Y₁  Y₂ = 1

¬Y₂  Y₃ = 1

¬Y₃  Y₄ = 1

¬Y₄  Y₅ = 1

1. как следует из разбора предыдущей задачи, такая система имеет 5+1 = 6 решений для переменных Y₁ … Y₅

2. теперь нужно получить количество решений в исходных переменных, X₁ … X₁₀; для этого заметим, что переменные Y₁ … Y₅ независимы;

3. предположим, что значение Y₁ известно (0 или 1); поскольку , по таблице истинности операции «эквивалентность» (истина, когда два значения одинаковы), есть две соответствующих пары (X₁;X₂) (как для случая Y₁ = 0, так и для случая Y₁ = 1)

4. у нас есть 5 переменных Y₁ … Y_5, каждая их комбинация дает 2 пары (X₁;X₂), 2 пары (X₃;X₄), 2 пары (X₅;X₆), 2 пары (X₇;X₈) и 2 пары (X₉;X₁₀), то есть всего 2⁵ = 32 комбинации исходных переменных

5. таким образом, общее количество решений равно 6 ·32 = 192

6. ответ: 192 решения

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

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

1. анализируя таблицу, строим правило отображения пар переменных (например, паре x₁x₂=00 соответствуют пара x₃x₄= 00 и 11, и наоборот, для пары x₁x₂=00 нет связей x₃x₄= 01 и 10).

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

1. таким образом, ответ: 80+ 16 + 16 + 80 = 192 решения.

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