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

Содержание План подготовки к ЕГЭ Базовые знания по теме «Логика» Методика решения некоторых логических задач Дополнительная литература и сайты по теме ЕГЭ, задача B15

Особенности решения Руководствоваться здравым смыслом при решении логических задач. Правильно распределить время на экзамене (лучше решить С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

Источники дополнительных сведений ФИПИ Открытый сегмент ЕГЭ КИМ ЕГЭ по информатике 27.html 27.html Сайт на Яндексе