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

1 Муниципальное Бюджетное Нетиповое Общеобразовательное Учреждение "Лицей №111", г. Новокузнецк, 2 Муниципальное Бюджетное Нетиповое Общеобразовательное Учреждение "Лицей №111", г. Новокузнецк
В данной статье описан метод решения и оптимального оформления задания на определения количества решений логических уравнений. Существующие методы решения сводятся к построению длинной цепочки рассуждений, которая изменяется в зависимости от типов уравнений входящих в систему. Предлагаемый авторами метод позволяет свести вероятность ошибки при решении такого рода задач к минимуму.

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

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

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

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

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

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

Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено три переменных. Зная x1и x2,можем найти все возможные значения x3, удовлетворяющие первому уравнению. То есть, зная пару (x1x2) и определив значение x3, мы найдем пару (x2x3), которая, в свою очередь, приведет к паре (x3x4) и так далее. На каждом шаге имеем множество исходных пар из набора (00, 01, 10, 11) и множество полученных пар из такого же набора (00, 01, 10, 11). Исходное множество пар отображается само в себя. Построим такое отображение.

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

 

x1

x2

x3

0

0

0

1

1

0

1

1

0

1

1

0

1

 

Пара 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.

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

Пара

Количество пар

x1,x2

x2,x3

x3,x4

x4,x5

x5,x6

x6,x7

x7,x8

x8,x9

x9,x10

00

1

1

1

1

1

1

1

1

1

01

1

2

3

5

8

13

21

34

55

10

1

2

4

7

12

20

33

54

88

11

1

2

4

7

12

20

33

54

88

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

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

Тип выступления  Устное выступление и публикация
Уровень образования  Среднее (полное) общее
Ключевые слова  Система, логика, решение, метод, граф, пара
Презентация доклада  Загрузить