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

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

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

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

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

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

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

7 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 Сколько будет решений, если заменить ?

8 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

9 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

10 Поскольку значения переменных в скобках должны быть разными, они будут чередоваться: Примеры решения задач 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

11 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 решений. ИЛИ

12 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 В третьем уравнении есть связь между последними строками

13 Примеры решения задач (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 решений

14 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

15 Примеры решения задач ¬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 В итоге получим три простых уравнения

16 Примеры решения задач 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)

17 Примеры решения задач Система уравнений имеет 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 решений.

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