Презентация«Подготовка к ЕГЭ Задача А3,А10,В12,B15»
Логические задачи Подготовка к ЕГЭЗадача А3,А10,В12,B15 Автор: Керженова М.З. Содержание План подготовки к ЕГЭБазовые знания по теме «Логика»Методика решения некоторых логических задачДополнительная литература и сайты по теме ЕГЭ Основные знания по теме «Логика» Базовые логические операции НЕ, И, ИЛИ А не А 0 1 1 0 A B А и B 0 0 0 0 1 0 1 0 0 1 1 1 A B А или B 0 0 0 0 1 1 1 0 1 1 1 1 Дополнительные логические операции A B А B 0 0 0 0 1 1 1 0 1 1 1 0 A B А B 0 0 1 0 1 1 1 0 0 1 1 1 A B А B 0 0 1 0 1 0 1 0 0 1 1 1 Исключающее ИЛИ Импликация Эквивалентность Основные знания по теме «Логика» Приоритет логических операций : вычисление в скобках НЕ, И, ИЛИ, исключающее ИЛИ импликация эквивалентность Основные знания по теме «Логика» Замена операций через И, ИЛИ и НЕ: Формулы де Моргана: Построение таблиц истинности логических выражений* Разбор задачи A3 Задание А3. Задача. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?1) (X Y) ¬Z 2) ¬X Y Z 3) X Y ¬Z 4) X ¬Y Z X Y Z F 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 X Y Z (X Y) ¬Z ¬X Y Z X Y ¬Z X ¬Y Z F 1 0 0 (1 0) ¬0=1 ¬1 0 0=0 1 0 ¬0=0 1 ¬0 0=1 1 1 0 1 (1 0) ¬1=0 ¬1 0 1=1 1 0 ¬1=0 1 ¬0 1=1 0 1 1 1 (1 1) ¬1=0 ¬1 1 1=1 1 1 ¬1=0 1 ¬1 1=1 0 0 1 0 (0 1) ¬0=1 ¬0 1 0=1 0 1 ¬0=0 0 ¬1 0=0 1 Решение:нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данныхесли для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции FИз полученной таблицы видно, что F соответствует выражение 1: (X Y) ¬Z (выделено зеленым). Значения остальных выражений не совпадают с F (выделено розовым). № области x1 x2 x3 x4 x5 x6 x7 F 1 1 1 0 1 1 1 1 0 2 1 0 1 0 1 1 0 0 3 0 1 0 1 1 0 0 1 Каким из приведённых ниже выражений может быть F? ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7 ¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7 x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7 x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7 Дан фрагмент таблицы истинности выражения F. Разбор задачи A3 Построение таблиц истинности логических выражений* x1 x2 x3 x4 x5 x6 x7 F F=¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7(вариант 1) F=x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7(вариант 3) 1 1 0 1 1 1 1 0 0Λ1Λ1Λ1Λ1Λ0Λ0=0 1Λ0Λ0Λ0Λ1Λ1Λ0=0 1 0 1 0 1 1 0 0 0Λ0Λ0Λ0Λ1Λ0Λ1=0 1Λ1Λ1Λ1Λ1Λ1Λ1=1 0 1 0 1 1 0 0 1 1Λ1Λ1Λ1Λ1Λ1Λ1=1 Решение:Сначала определим, как связаны переменные в F: с помощью конъюнкции (Λ) или дизъюнкции (V).Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3. Получили вариант 1: ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7 Разбор задачи A10На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула ( (x ∈ А) → (x ∈ P) ) \/ (x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. [0, 3][3, 11][11, 15][15, 17] Вариант ответа Интервал A Значения x для проверки(границы интервала) ((x ∈ А) → (x ∈ [2, 10]) ) \/ (x ∈ [6, 14]) 1 [0, 3] 0, 3 (1→0)V0=0(1→1)V0=1 2 [3, 11] 3, 11 1(1→0)V1=1 3 [11, 15] 11, 15 1(1→0)V0=0 4 [15, 17] 15, 17 0(1→0)V0=0 Решим уравнение: ( (x ∈ А) → (x ∈ P) ) \/ (x ∈ Q)=1 методом подстановки. В уравнение вместо P, Q впишем сами отрезки: [2, 10] и [6, 14]. (x ∈ А)=1 для всех вариантов. Задание А10. Задача: Для какого имени истинно высказывание:¬ (Первая буква имени гласная → Четвертая буква имени согласная)?1) ЕЛЕНА2) ВАДИМ3) АНТОН4) ФЕДОР Решение (рассуждения):Запишем выражение: ¬ (1Г → 4С) 1перед выражением стоит отрицание, при котором высказывание истинно, значит без отрицания выражение в скобках должно быть ложно: 1Г → 4С 0импликация ложна, если ее первая часть («посылка») истинна, а вторая («следствие») – ложна: 1Г 1 4С 0первое условие истинно, когда первая буква гласная, то есть для ответов 1 и 3второе условие «четвертая буква согласная» ложно тогда, когда четвертая буква гласная, то есть, для ответа 3: 4Г 1таким образом, для варианта 3 исходное условие в целом истинноответ: 1. Запрос Найдено страниц(в тысячах) Фрегат | Эсминец 3400 Фрегат & Эсминец 900 Фрегат 2100 Разбор задачи B12В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Решение:Изобразим запросы в виде диаграмм Эйлера-Венна.Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э". Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200. I. Простая задача, решаемая с методом рассуждений:Сколько различных решений имеет уравнение (K L M) (¬L ¬M N) = 1 N-любое (0 или 1) K L M N 0 0 1 0(1) 0 1 0 0(1) 0 1 1 0(1) 1 0 0 0(1) 1 0 1 0(1) 1 1 0 0(1) 1 1 1 0(1) K-любое, L=0, M=0, N=1, всего два решения Примеры решения задач Итого 7 х 2 = 14 решений K L M N 0 0 0 1 1 0 0 1 Есть только одно совпадающее решениеK=1, L=0, M=0, N=1 Сколько будет решений, если заменить → ? Задание В 15. Задача. Сколько различных решений имеет уравнение (M N) ((N K) (¬L M))0, где K,L,M,N - логические переменные. K L M N M N N K ¬L M (N K) (¬L M) (M N) ((N K) (¬L M))0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 Решение (вариант 2, составление таблицы истинности):нужно для каждой строчки подставить значения K,L,M,N и вычислить значение функции для четырех комбинаций K,L,M,N результат будет ложным. Ответ: 4. II. Задача, решаемая с методом рассуждений:Сколько различных решений имеет уравнение (X1 X2)(X2 X3)(X3 X4)(X4 X5) = 1 Все скобки должны быть равны 1 Х1 Х2 Х3 Х4 Х5 1 0 0 0 0 0 2 0 0 0 0 1 3 0 0 0 1 1 4 0 0 1 1 1 5 0 1 1 1 1 6 1 1 1 1 1 Операция импликации дает только одно решение = 0, когда 1 0,то есть нельзя, чтобы после 1 был 0 Примеры решения задач Вывод:Количество решений на единицу больше количества переменных (6 реш.)Если X1…X10, то количество решений будет равно 11 III. Задача, решаемая с помощью замены переменных:Сколько различных решений имеет система уравнений ((x1 ≡ x2) (x3 ≡ x4)) (¬(x1 ≡ x2) ¬(x3 ≡ x4)) =1((x3 ≡ x4) (x5 ≡ x6)) (¬(x3 ≡ x4) ¬(x5 ≡ x6)) =1((x5 ≡ x6) (x7 ≡ x8)) (¬(x5 ≡ x6) ¬(x7 ≡ x8)) =1((x7 ≡ x8) (x9 ≡ x10)) (¬(x7 ≡ x8) ¬(x9 ≡ x10)) =1 Примеры решения задач t1 = (x1 ≡ x2) t2 = (x3 ≡ x4) t3 = (x5 ≡ x6) t4 = (x7 ≡ x8)t5 = (x9 ≡ x10) Произведем замену: Перепишем уравнения, заметим, что уравнения = 1, когда t1 ≠ t2 ( t1 t2 ) ( ¬ t1 ¬ t2) =1( t2 t3 ) ( ¬ t2 ¬ t3) =1( t3 t4 ) ( ¬ t3 ¬ t4) =1( t4 t5 ) ( ¬ t4 ¬ t5) =1 Поскольку значения переменных в скобках должны быть разными, они будут чередоваться: Примеры решения задач t1 = (x1 ≡ x2) t2 = (x3 ≡ x4) t3 = (x5 ≡ x6) t4 = (x7 ≡ x8)t5 = (x9 ≡ x10) Для каждой комбинации из 5-ти значений t1 … t5 существует по 2 решения:если t1 = 0, то x1 =1, x2 =0или x1 =0, x2 =1если t1 = 1, то x1 =1, x2 =1или x1 =0, x2 =0 ( t1 t2 ) ( ¬ t1 ¬ t2) =1( t2 t3 ) ( ¬ t2 ¬ t3) =1( t3 t4 ) ( ¬ t3 ¬ t4) =1( t4 t5 ) ( ¬ t4 ¬ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Получим 2 решения: То есть 2 варианта по 5 переменным дают 25=32 решения, 32+32=64 Источники дополнительных сведений ФИПИ http://www.fipi.ru/viewОткрытый сегмент ЕГЭ http://www.fipi.ru/view/sections/160/docs/КИМ ЕГЭ по информатике http://www.fipi.ru/view/sections/226/docs/627.html Сайт на Яндексе www.ege.yandex.ru