Задание 23. Пример из демо-версии

1. Условие задачи.

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

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

 2. Набросок решения.  

Решение состоит из двух этапов. Сначала попытаемся описать, как устроены все наборы значений переменных, удовлетворяющие данной системе. Далее подсчитаем число таких наборов.

            2.1. Как устроено множество решений

           А. Предварительный этап – упрощаем уравнения.

В системе фигурируют логические функции от следующих выражений:

(x₁ ≡ x₂),   (x₃ ≡ x₄),  (x₅ ≡ x₆),  (x₇ ≡ x₈),   (x₉ ≡ x₁₀)

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

 Общая формула замены (k=1, 2, 3, 4, 5):

t_k = (x_2k-1 ≡ x_2k)

После замены получим:

Уравнения полученной системы имеют вид (k=1, 2, 3, 4):

(t_k  \/  t_k+1) /\ (¬t_k  \/ ¬ t_k+1 ) =1

            Это означает, что из каждых двух переменных t_k  и  t_k+1 ровно одна равна 1 и ровно одна равна нулю, т.е. эти переменные имеют разные значения. Таким образом, систему можно еще немного упростить и записать ее так:

            Б. Анализ системы.

В любом решении последней системы значения переменных чередуются. Поэтому такая система имеет ровно два решения: 01010 и 10101 (первая цифра – значение переменной t₁,  вторая - значение   t₂ и т.д.).

Далее, вспоминаем, что

t_k = x_2k-1 ≡ x_2k

(здесь k=1, 2, 3, 4, 5).

Поэтому каждому значению t_k соответствуют две пары значений переменных  x_2k-1 и x_2k:

             2.2. Подсчет числа решений

Каждому из двух решений системы для переменных t соответствует 2⁵ = 32 решения исходной системы. Поэтому исходная система имеет 2∙32 = 64 решения.

Ответ:64

Упражнение. Выпишите все решения. Это немного утомительно, но полезно.