Системы логических уравнений. Метод отображений

Задание на определение количества вариантов решения системы уравнений, с большим количеством неизвестных встречаются в ЕГЭ. Один из способов решения одного из вариантов задания B14 ЕГЭ по информатике широко описан в литературе. Однако можно отметить такие его недостатки как:

·         отсутствие наглядности;

·         обилие в рассуждениях фраз: аналогично, легко заметить, если … то, пусть и т.д.;

·         трудность проверки и поиска ошибок.

Учитывая, что решение происходит в стрессовой обстановке, необходимо свести вероятность ошибки «по невнимательности» к нулю. Поэтому авторы предлагают оригинальный способ решения.

Рассмотрим систему логических уравнений.

Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено три переменных. Зная x₁и x_2,можем найти все возможные значения x₃, удовлетворяющие первому уравнению. То есть, зная пару (x₁, x₂) и определив значение x₃, мы найдем пару (x₂, x₃), которая, в свою очередь, приведет к паре (x₃, x₄) и так далее. На каждом шаге имеем множество исходных пар из набора (00, 01, 10, 11) и множество полученных пар из такого же набора (00, 01, 10, 11). Исходное множество пар отображается само в себя. Построим такое отображение.

Сначала построим таблицу, в которой в первых двух столбцах переберем все варианты x₁,x₂, а в третий столбец впишем только такие значения x₃, которые приведут первое уравнение к верному равенству. По таблице строим правило отображения множества пар само в себя.

Пара 00 дает две пары – пару 00 и пару 01. Пара 01 также приводит к двум парам – 10 и 11. Пара 10 даст только одну пару 01. И из пары 11 получается две пары – 10 и 11. На каждом следующем шаге пары будут образовываться по такому же правилу. Получаем ориентированный граф.

На каждом этапе количество пар 01 будет определяться суммой количества пар 00 и 10 на предыдущем этапе. Пусть Fэто функция, вычисляющая количество пар на следующем шаге. Получаем:

F(00) = F(00), в пару 00 входит одна стрелка от 00.

F(01) = F(00) + F(10), в пару 01 входят стрелки, ведущие от 00 и 10.

F(10) = F(01) + F(11), в пару 10 входят стрелки, ведущие от 01 и 11.

F(11) = F(01) + F(11), в пару 11 входят стрелки, ведущие от 01 и 11.

Остается построить таблицу для вычисления количества пар на каждом этапе.

На последнем шаге получили одну пару 00, 55 пар 01, по 88 пар 10 и 11. Итого 1+55+88+88=232 набора, x₁,x₂, x₃, … x₁₀ приводящих систему логических уравнений к решению. Получаем 232 решения.

Обратим внимание, что данный метод позволяет значительно усложнить круг решаемых задач, добавляя особые условия (например, , ) или меняя правила построения уравнений в системе (например, у уравнений стоящих на четных местах в правой части поставить 1, а на нечетных 0).