Мастер-класс Логические задачи Подготовка к ЕГЭ Задача B15 Автор: Лимаренко Андрей Иванович, учитель информатики гимназии 446

Особенности решения Руководствоваться здравым смыслом при решении логических задач. Правильно распределить время на экзамене (лучше решить С1, чем В15) Задание сложное, его невозможно формализовать, в каждом задании – свой путь решения

План подготовки к ЕГЭ Нельзя начинать решать задачи на логику (А3, А10, В15) без повторения тем: «Информация и её кодирование» - А9, А11, В1, В4, В10 «Системы счисления» - А1, В8

Основные знания по теме «Логика» Базовые логические операции НЕ, И, ИЛИ Ане А ABА и B ABА или B Дополнительные логические операции AB А B AB AB Исключающее ИЛИИмпликацияЭквивалентность

Основные знания по теме «Логика»

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

I. Простая задача, решаемая методом рассуждений: Сколько различных решений имеет уравнение (K L M) (¬L ¬M N) = 1 N-любое (0 или 1) KLMN 0010(1) K-любое, L=0, M=0, N=1, всего два решения Примеры решения задач Итого 7 х 2 = 14 решений KLMN Есть только одно совпадающее решение K=1, L=0, M=0, N=1 Сколько будет решений, если заменить ?

II. Задача, решаемая методом рассуждений: Сколько различных решений имеет уравнение (X 1 X 2 ) (X 2 X 3 ) (X 3 X 4 ) (X 4 X 5 ) = 1 Все скобки должны быть равны 1 Х1Х1 Х2Х2 Х3Х3 Х4Х4 Х5Х Операция импликации дает только одно решение = 0, когда 1 0, то есть нельзя, чтобы после 1 был 0 Примеры решения задач Вывод: Количество решений на единицу больше количества переменных (6 реш.) Если X 1 …X 10, то количество решений будет равно 11

III. Задача, решаемая с помощью замены переменных: Сколько различных решений имеет система уравнений ((x 1 x 2 ) (x 3 x 4 )) (¬(x 1 x 2 ) ¬(x 3 x 4 )) =1 ((x 3 x 4 ) (x 5 x 6 )) (¬(x 3 x 4 ) ¬(x 5 x 6 )) =1 ((x 5 x 6 ) (x 7 x 8 )) (¬(x 5 x 6 ) ¬(x 7 x 8 )) =1 ((x 7 x 8 ) (x 9 x 10 )) (¬(x 7 x 8 ) ¬(x 9 x 10 )) =1 Примеры решения задач t 1 = (x 1 x 2 ) t 2 = (x 3 x 4 ) t 3 = (x 5 x 6 ) t 4 = (x 7 x 8 ) t 5 = (x 9 x 10 ) Произведем замену: Перепишем уравнения, заметим, что уравнения = 1, когда t1 t2 ( t 1 t 2 ) ( ¬ t 1 ¬ t 2 ) =1 ( t 2 t 3 ) ( ¬ t 2 ¬ t 3 ) =1 ( t 3 t 4 ) ( ¬ t 3 ¬ t 4 ) =1 ( t 4 t 5 ) ( ¬ t 4 ¬ t 5 ) =1

Поскольку значения переменных в скобках должны быть разными, они будут чередоваться: Примеры решения задач t 1 = (x 1 x 2 ) t 2 = (x 3 x 4 ) t 3 = (x 5 x 6 ) t 4 = (x 7 x 8 ) t 5 = (x 9 x 10 ) Для каждой комбинации из 5-ти значений t 1 … t 5 существует по 2 решения: если t 1 = 0, то x 1 =1, x 2 =0 или x 1 =0, x 2 =1 если t 1 = 1, то x 1 =1, x 2 =1 или x 1 =0, x 2 =0 ( t 1 t 2 ) ( ¬ t 1 ¬ t 2 ) =1 ( t 2 t 3 ) ( ¬ t 2 ¬ t 3 ) =1 ( t 3 t 4 ) ( ¬ t 3 ¬ t 4 ) =1 ( t 4 t 5 ) ( ¬ t 4 ¬ t 5 ) =1 t1t1 t2t2 t3t3 t4t4 t5t Получим 2 решения: То есть 2 варианта по 5 переменным дают 2 5 =32 решения, 32+32=64

IV. Задача, в которой есть два несвязанных между собой уравнения: Сколько различных решений имеет система уравнений Примеры решения задач (X 1 X 2 ) (X 2 X 3 ) (X 3 X 4 ) (X 4 X 5 ) =1 (Z 1 Z 2 ) (Z 2 Z 3 ) (Z 3 Z 4 ) =1 Количество решений первого уравнения – 6, второго – 5, т.е. на 1 больше количества переменных (см. задачу I): Х1Х1 Х2Х2 Х3Х3 Х4Х4 Х5Х Z1Z1 Z2Z2 Z3Z3 Z4Z Значит количество решений системы уравнений можно найти простым перемножением: 6*5=30 решений. ИЛИ

V. Добавим в предыдущую систему еще одно уравнение, связывающее первые два: Примеры решения задач (X 1 X 2 ) (X 2 X 3 ) (X 3 X 4 ) (X 4 X 5 ) = 1 (Z 1 Z 2 ) (Z 2 Z 3 ) (Z 3 Z 4 ) = 1 (X 1 Z 1 ) = 1 Количество решений первого уравнения – 6, второго – 5, т.е. на 1 больше количества переменных (см. задачу I). Х1Х1 Х2Х2 Х3Х3 Х4Х4 Х5Х Z1Z1 Z2Z2 Z3Z3 Z4Z В третьем уравнении есть связь между последними строками

Примеры решения задач (X 1 X 2 ) (X 2 X 3 ) (X 3 X 4 ) (X 4 X 5 ) = 1 (Z 1 Z 2 ) (Z 2 Z 3 ) (Z 3 Z 4 ) = 1 (X 1 Z 1 ) = 1 Последнее уравнение накладывает дополнительное условие – переменные X 1, Z 1 не могут одновременно = 0. Х1Х1 Х2Х2 Х3Х3 Х4Х4 Х5Х Z1Z1 Z2Z2 Z3Z3 Z4Z Итого = 11 Однако, одну из комбинаций мы посчитали 2 раза, значит 11 – 1 = 10 решений

VI. Задача, в которой применяется упрощение логических уравнений: Сколько различных решений имеет система уравнений Примеры решения задач X 1 X 2 X 3 ¬X 4 = 1 X 3 X 4 X 5 ¬X 6 = 1 X 5 X 6 X 1 ¬X 2 = 1 1. Расставим порядок действий (добавим скобки): X 1 ( X 2 X 3 ¬X 4 ) = 1 X 3 ( X 4 X 5 ¬X 6 ) = 1 X 5 ( X 6 X 1 ¬X 2 ) = 1 2. Раскроем импликацию по формуле: ¬X 1 X 2 X 3 ¬X 4 = 1 ¬X 3 X 4 X 5 ¬X 6 = 1 ¬X 5 X 6 X 1 ¬X 2 = 1 1.НЕ ¬ 2.И 3.ИЛИ 4. A B = ¬A B

Примеры решения задач ¬X 1 X 2 X 3 ¬X 4 = 1 ¬X 3 X 4 X 5 ¬X 6 = 1 ¬X 5 X 6 X 1 ¬X 2 = 1 ¬X 1 X 2 = ¬(X 1 ¬X 2 ) ¬X 3 X 4 = ¬(X 3 ¬X 4 ) ¬X 5 X 6 = ¬(X 5 ¬X 6 ) 3. Далее замечаем, что можно применить закон де Моргана ¬(X 1 ¬ X 2 ) (X 3 ¬X 4 ) = 1 ¬(X 3 ¬ X 4 ) (X 5 ¬X 6 ) = 1 ¬(X 5 ¬ X 6 ) (X 1 ¬X 2 ) = 1 4. В получившихся уравнениях произведем замену переменных, чтобы сократить их количество. Y 1 = ¬(X 1 ¬X 2 ) Y 2 = ¬(X 3 ¬X 4 ) Y 3 = ¬(X 5 ¬X 6 ) Y 1 ¬ Y 2 = 1 Y 2 ¬ Y 3 = 1 Y 3 ¬ Y 1 = 1 В итоге получим три простых уравнения

Примеры решения задач 5. Рассуждаем: Y 1 ¬ Y 2 = 1 Y 2 ¬ Y 3 = 1 Y 3 ¬ Y 1 = 1 Пусть Y 1 = 0, тогда из первого уравнения следует Y 2 = 0, а далее из второго Y 3 = 0, Третье автоматически выполняется Пусть Y 1 = 1, тогда из последнего уравнения имеем Y 3 = 1, а из второго Y 2 = 1, Первое автоматически выполняется Система уравнений имеет два решения: (1, 1, 1) и (0, 0, 0) 6. Вернемся обратно к исходным переменным. При Y 1 = 0 уравнение ¬(X 1 ¬X 2 ) имеет только одно решение: X 1 = 1, X 2 = 0. Значению Y 1 = 1 соответствуют остальные три пары решений (0, 0), (0, 1) и (1, 1)

Примеры решения задач Система уравнений имеет 1+27 = 28 решений 7. То же самое получим и для Y 2, Y 3 : нулевое значение дает один набор соответствующих исходных переменных, а единичное – три. 8. Переменные Y 1, Y 2, Y 3 независимы друг от друга, поэтому Y-решение (0, 0, 0) дает только одно X-решение 1*1*1=1, а Y-решение (1, 1, 1) дает 3*3*3 = 27 решений.

Источники дополнительных сведений ФИПИ Открытый сегмент ЕГЭ КИМ ЕГЭ по информатике ml ml Сайт на Яндексе Блог Константина Полякова: Сайт РешуЕГЭ