Методики решения систем логических уравнений со многими переменными Мельникова Д.Ю., учитель информатики МАОУ «Физико-технический лицей 1» г. Саратова

Спецификация контрольных измерительных материалов для проведения в 2014 году единого государственного экзамена по информатике и ИКТ

Кодификатор элементов содержания и требований к уровню подготовки выпускников общеобразовательных учреждений для проведения единого государственного экзамена по информатике и ИКТ Перечень элементов содержания, проверяемых на едином государственном экзамене по информатике и ИКТ: Высказывания, логические операции, кванторы, истинность высказывания Перечень требований к уровню подготовки, проверяемому на едином государственном экзамене по информатике и ИКТ: Вычислять логическое значение сложного высказывания по известным значениям элементарных высказываний

Необходимые знания Обозначения, таблицы истинности, свойства логических операций ( конъюнкция, дизъюнкция, инверсия, эквиваленция, исключающее «или») Приоритет логических операций Законы алгебры логики Формулы представления импликации, эквиваленции, исключающего «или»:

Некоторые приемы Замены переменных для независимых повторяющихся выражений Наблюдения закономерностей роста количества решений при добавлении переменных/уравнений Правила комбинаторики (правила суммы и произведения) Нет единого алгоритма решения!

B15 (октябрь 2011) Сколько различных решений имеет система уравнений ¬ (x1 x2) /\ ¬ (x2 x3) =1 ¬ (x2 x3) /\ ¬ (x3 x4) =1... ¬ (x8 x9) /\ ¬ (x9 x10) =1 где x1, x2,..., x10 – логические переменные? ¬ (x1 x2) =1 ¬ (x2 x3) =1 … ¬ (x9 x10) =1 x1 x2=0 x2 x3=0 … x9 x10 = x1x2 x2x3 … x9x10

В15 (декабрь 2011) Сколько существует различных наборов значений логических переменных x1, x2,..., x9 которые удовлетворяют всем перечисленным ниже условиям? (¬x1 /\ ¬x2 /\ x3) \/ (¬x1 /\ x2 /\ ¬x3) \/ (x1 /\ ¬x2 /\ ¬x3) = 1 (¬x2 /\ ¬x3 /\ x4) \/ (¬x2 /\ x3 /\ ¬x4) \/ (x2 /\ ¬x3 /\ ¬x4) = 1... (¬x7 /\ ¬x8 /\ x9) \/ (¬x7 /\ x8 /\ ¬x9) \/ (x7 /\ ¬x8 /\ ¬x9) = 1 где x1, x2,..., x9 логические переменные? В ответе не нужно перечислять все различные наборы значений переменных x1, x2,..., x9 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

(¬x1 /\ ¬x2 /\ x3) \/ (¬x1 /\ x2 /\ ¬x3) \/ (x1 /\ ¬x2 /\ ¬x3) = 1 (¬x2 /\ ¬x3 /\ x4) \/ (¬x2 /\ x3 /\ ¬x4) \/ (x2 /\ ¬x3 /\ ¬x4) = 1... (¬x7 /\ ¬x8 /\ x9) \/ (¬x7 /\ x8 /\ ¬x9) \/ (x7 /\ ¬x8 /\ ¬x9) = 1 x1 x2 x3 x4 x5 x6 x7 x8 x

19/04/ вариант 4 вариант

x1x2x3 x4 x

y1y2y3y4 y *6=36 решений

y1 y2 y3 y4 y x1 x2 x3 x4 x решений 5 решений =31 3 вариант

x 1 x2 x3 x4 x y1 y2 y3 y4 y решений 1 решение =31 4 вариант

Пример

Делаем замену:х1=a b х2=c d х3=e f х4=g h х5=i j (х1х2)(х2х3)(х3х4)(х4х5) (х5х1) =1 x1 x2 x3 x4 x5 х решения для х1,х2, х3,х4,х5:

a b=1 c d=1 e f=1 g h=1 i j=1 a b=0 c d=0 e f=0 g h=0 i j=0 2 решения Правило суммы Правило произведения

... Пример Решение... X1X X2X X X X i всего решений в дереве решений на каждом i+1 уровне добавляются по 2 решения – в случае X i =X i-1

Пример Решение … …

X1X1 X1X X2X X1X1 X2X X3X … X если X i =X i-1, то X i+1 выбирается 2мя способами, 0 и 1 если X iX i-1, то X i+1 выбирается однозначно, равным X i

i число решений е уравнение – 6 решений На шаге подключения переменной X4 и второго уравнения получается 10 решений На шаге подключения переменной X5 и третьего уравнения получается 16 удвоенная последовательность Фибоначчи: 2, 4, 6, 10, 16, 26, …, в которой каждый следующий элемент равен сумме двух предыдущих … X1X1 X2X X3X X Наблюдение закономерности роста кол-ва решений, догадка

x1x1 x2x2 x3x Метод отображений (Мирончик Ел. А., Мирончик Ек. А.) x 1 x 2 x 2 x …

x1x2x1x2 x2x3x2x3 x3x4x3x4 x4x5x4x5 x5x6x5x6 x6x7x6x7 x7x8x7x8 x8x9x8x9 x 9 x = 178 решений x 1 x 2 x 2 x

Сколько различных решений имеет система уравнений X1 X2 X3 = 1 X2 X3 X4 = 1... X8 X9 X10 = 1 x1x1 x2x2 x3x x 1 x 2 x 2 x Метод отображений (Мирончик Ел. А., Мирончик Ек. А.)

x1x2x1x2 x2x3x2x3 x3x4x3x4 x4x5x4x5 x5x6x5x6 x6x7x6x7 x7x8x7x8 x8x9x8x9 x 9 x x 1 x 2 x 2 x = 73 решения

Источники информации [Электронный ресурс] К.Ю. Поляков. Логические уравнения // Информатика, 14, 2011, с Метод отображения, Мирончик Е.А., МБ НОУ «Лицей 111», г. Новокузнецк РЕШУ ЕГЭ. Образовательный портал для подготовки к экзаменам. Каталог заданий. Системы логических уравнений. p1ai/test?theme=264 [Электронный ресурс] 1