Логика Разбор задач ЕГЭ В презентации использованы материалы с сайта К.Ю. Полякова kpolyakov.narod.rukpolyakov.narod.ru. - презентация

1 Логика Разбор задач ЕГЭ В презентации использованы материалы с сайта К.Ю. Полякова kpolyakov.narod.rukpolyakov.narod.ru

2 Содержание Логические операции Логические законы А3 – Построение таблиц истинности – Построение таблиц истинности A10 - Основные понятия математической логики- Основные понятия математической логики B12 – Составление запросов для поисковых систем – Составление запросов для поисковых систем B15 – Системы логических выражений – Системы логических выражений

3 В заданиях ЕГЭ используются следующие соглашения 1. Обозначения для логических операций: a) отрицание (инверсия, логическое НЕ) обозначается ¬ (¬А); b) конъюнкция (логическое умножение, И) обозначается (A B, A&B) c) дизъюнкция (логическое сложение, ИЛИ) обозначается (А В); d) следование (импликация) обозначается (А В=¬А B); e) тождество (эквиваленция)обозначается (A B=A B ¬А ¬B); f) исключающее ИЛИ обозначается (A B= ¬А B А ¬B) 2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если их значения совпадают 3. Приоритеты логических операций: инверсия, конъюнкция, дизъюнкция, импликация

4 Логические операции АВ A B АВ А¬A¬A АВ ¬A B АВAB ¬A ¬B A B АВ A B¬A B A ¬B Инверсия Конъюнкция ДизъюнкцияИмпликация Эквиваленция Исключающее ИЛИ

5 Логические законы Закон Для ИДля ИЛИ двойного отрицания непротиворечияисключения третьего исключения констант A 1 = A; A 0 = 0A 0 = A; A 1 = 1 повторения A A = A поглощения A (A + B) = AA A · B = A переместительный A B = B A сочетательный A (B C) = (A B) C распределительный A B C = (A B) (A C)A (B C) = A B A C исключения (склеивания) де Моргана

6 Задача 1. Решение логических задач средствами алгебры логики В соревновании планировали участвовать три атлета (А,В,С). После начала соревнований стало известно, что следующие высказывания являются истинными: 1. Атлет А участвует в соревновании, а атлет В – не участвует. 2. Неверно, что из двух атлетов В и С в соревнованиях участвует только один. Определите, какие атлеты в результате приняли участие в соревнованиях. В ответе укажите через запятую латинские буквы, обозначающие атлетов. Решение: Обозначим первое высказывание X, второе Y, а результат Z и запишем логическое выражение.

7 Решение задачи 1 Обозначим первое высказывание X, второе Y, а результат Z и запишем логическое выражение:

8 Решение задачи 1 Используя законы логики, упростим выражение: Ответ: В соревновании участвует атлет А и не участвуют атлеты В и С.

9 Задачи А3 Построение таблиц истинности логических выражений

10 Задача 1 Какое логическое выражение эквивалентно выражению A B B?: 1. A B2. A B3. A B4. A A AB A BA B AA B B Ответ: 4

11 Задача 2. Дан фрагмент таблицы истинности выражения F: XYZFF1F1 F2F2 F3F3 F4F Таблицы истинности функций F и F 1 равносильны. Ответ: 1 Каким выражением может быть F? 1. X Y Z2. X Y Z 3. X Y Z 4. X Y Z Строим таблицы истинности для выражений: F 1 = X Y ZF 2 = X Y Z F 3 = X Y Z F 4 = X Y Z

12 Задачи А10 Основные понятия математической логики

13 Задача 1 Для какого символьного выражения НЕВЕРНО высказывание: (вторая буква гласная) пятая буква согласная 1) abcde2) becde3) babas4) abcad A - (вторая буква гласная), В - пятая буква согласная Импликация ЛОЖНА, когда А – ИСТИНА, а В – ЛОЖЬ Выражение будет ложным когда А = вторая буква согласная, а В = пятая буква гласная. Этому соответствует только сочетание abcde Ответ: 1

14 Задача 2 Какое из приведённых имён удовлетворяет логическому условию: (первая буква согласная вторая буква согласная) (предпоследняя буква гласная последняя буква гласная)? 1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН4) МАРИЯ 1. Введем обозначение: А – первая буква согласная, В – вторая буква согласная, С – предпоследняя буква гласная, D – последняя буква гласная Выражение примет вид (А B) (C D)=1 2. Заменим импликацию базовыми операциями ( А B) ( C D)=1 3. Из логического выражения следует: (первая буква гласная вторая буква согласная) (предпоследняя буква согласная последняя буква гласная)=1 КРИСТИНА – (К – согласная Р – согласная) = (0 1)=1 (Н - согласная А – гласная) = (1 1)=11 1 = 1 МАКСИМ – (М – согласная А –гласная) = (0 0)=0 (И - гласная М – согласная) = (0 0)=00 0 = 0 СТЕПАН – (С – согласная Т –согласная) = (0 1)=1 (А - гласная Н – согласная) = (0 0)=01 0 = 0 МАРИЯ – (М – согласная А –гласная) = (0 0)=0 (И - гласная Я – согласная) = (0 1)=10 1 = 0

15 Задачи В12 Составление запросов для поисковых систем с использованием логических выражений

16 Задача 1 В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Запрос 1 принтеры & сканеры & продажа 2 принтеры & сканеры 3 принтеры | сканеры 4 принтеры | сканеры | продажа 1. Меньше всего страниц в первом запросе, т.к. должны одновременно присутствовать и принтеры, и сканеры, и продажа. 2. На втором месте второй запрос – одновременно принтеры и сканеры. 3. На третьем месте третий запрос – на странице присутствует либо принтеры, либо сканеры, либо оба вместе. 4. На четвертом месте четвертый запрос – либо принтеры, либо сканеры, либо продажа, либо два из них, либо три. ОТВЕТ: 1234 Решение Вариант 1 - рассуждение с использованием свойств операций «И» и «ИЛИ»

17 Вариант 2 – используя таблицы истинности Запишем запросы в виде логических выражений: А – принтеры. В – сканеры. С - продажи. 1. X 1 = A B C 2. X 2 = A В 3. X 3 = A В 4. X 4 = A B C ABCX1X1 X2 X2 X3X3 X4X Всего единиц:1267 Чем больше единиц, тем больше информации получаем по запросу Ответ: 1234

18 Вариант 3 - используя диаграммы Эйлера-Венна 1. X 1 = A B C 2. X 2 = A В 3. X 3 = A В 4. X 4 = A B C Сравнивая диаграммы, находим последовательность областей в порядке увеличения. Каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!) Ответ: 1234 AB С A B С A B С A B С X 1 = A B CX 2 = A ВX 3 = A ВX 4 = A B C

19 Задача 2 В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Найдено страниц (в тысячах) Шахматы | Теннис 7770 Теннис 5500 Шахматы & Теннис 1000 Какое количество страниц (в тысячах) будет найдено по запросу Шахматы? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

20 Решение задачи 2 1. Шахматы | Теннис: N1+N3+N2= Шахматы&Теннис: N2= Теннис: N1+N2=5500 => N1 = N2 = = 4500 (только теннис) 4. Шахматы: N3+N2 Из 1: N3+N2=7770-N1 = 7770 – 4500 = 3270 Ответ: 3270 Воспользуемся диаграммами Эйлера-Венна

21 Задачи В15 Системы логических выражений

22 Задача 1 Сколько решений имеет система уравнений? ¬(x1 x2) (x3 x4) =1 ¬(x3 x4) (x5 x6) =1 ¬(x5 x6) (x7 x8) =1 ¬(x7 x8) (x9 x10) =1 В ответе не нужно перечислять все различные наборы значений x1, x2,... x9, x10, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

23 Решение задачи 1 Введем замену переменных:? A = x1x2; B = x3x4; C = x5 x6; D = x7x8; E = x9x10 Переменные А … Е - независимы ¬ A B=1 ¬ B C=1 ¬ C D=1 ¬ D E=1 Операция «ИЛИ» истинна тогда, когда хотя бы один из аргументов ИСТИНА. AB A B ¬ A B ¬A B=1 – ложно при А=1 и В=0 Рассмотрим первое уравнение ¬ A B=1

24 Решение задачи 1 ¬ A B=1 ¬ B C=1 ¬ C D=1 ¬ D E=1 ABCDE Из ¬ B C=1: ¬B C – ложно при B=1 и C=0. Если В=0 – С=0, С=1; В=1 – С= Из уравнения ¬A B=1 видно: Если А=0, то В может принимать значения 0 или 1, Если А=1, то В=1 Система уравнений для переменных А … Е дает 6 операций Из ¬ C D=1: ¬C D – ложно при C=1 и D=0. Если C=0 – D=0, D=1; C=1 – D=1 Из ¬ D E=1: ¬D E – ложно при D=1 и E=0. Если D=0 – E=0, E=1; В=1 – С=1

25 Решение задачи 1 (продолжение) Предположим, что значение А известно (0 или 1) Операция «Эквиваленция» истинна, когда два значения одинаковы Две соответствующих пары (X1;X2) (как для случая X1=X2 = 0, так и для случая X1=X2 = 1). Инверсия «Эквиваленции» - X1X2 тоже имеет две пары: (X1=0 и X2=1) или (X1=1 и X2=0) Аналогично: - Для В имеется две пары (X3;X4), (X3=0 и X4=1) или (X3=1 и X4=0) - Для С имеется две пары (X5;X6), (X5=0 и X6=1) или (X5=1 и X6=0) - Для D имеется две пары (X7;X8), (X7=0 и X8=1) или (X7=1 и X8=0) - Для Е имеется две пары (X9;X10), (X9=0 и X10=1) или (X9=1 и X10=0) Переменных 5. Из формулы Хартли N=2 i, 2 5 = 32 комбинации исходных переменных для одного решения системы для переменных А…Е. Так как решений для переменных А…Е шесть, то общее количество решений равно 6 ·32 = 192 Ответ: 192 решения Рассмотрим первую переменную: A= (x1 x2);

26 Задача 2 Сколько существует различных наборов значений логических переменных x1, x2,... x9, x10, которые удовлетворяют всем перечисленным ниже условиям? ((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 В ответе не нужно перечислять все различные наборы значений x1, x2,... x9, x10, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

27 Решение задачи 2 Введем замену переменных:? A=x1 x2; B=x3 x4; C=x5 x6; D=x7 x8; E=x9 x10 (A B) (¬A ¬B) =1=>A ¬B ¬A B => A B (B C) (¬B ¬C) =1=> B ¬C ¬B C => B C (C D) (¬C ¬D) =1=> C ¬D ¬C D => C D (D E) (¬D ¬E) =1=> D ¬E ¬D E => D E A B=1 B C=1 C D=1 D E=1 ABCDE Переменные А … Е - независимы Логическая операция «Исключающее ИЛИ» истинна тогда, когда один из аргументов ИСТИНА, но не оба вместе. Система уравнений для переменных А … Е дает 2 операции

28 Решение задачи 2 (продолжение) Рассмотрим первую переменную: A=x1 x2; Предположим, что значение А известно (0 или 1); поскольку операция «Эквиваленция» истинна, когда два значения одинаковы, то есть две соответствующих пары (X1;X2) (как для случая X1=X2 = 0, так и для случая X1=X2 = 1) Аналогично: - для переменной В имеется две пары (X3;X4), (X3=X4 = 0, X3=X4= 1) - для переменной С имеется две пары (X5;X6), (X5=X6 = 0, X5=X6 = 1) - для переменной D имеется две пары (X7;X8), (X7=X8 = 0, X7=X8 = 1) - для переменной Е имеется две пары (X9;X10) (X9=X10= 0, X9=X10 = 1) Переменных 5. Из формулы Хартли N=2 i, 2 5 = 32 комбинации исходных переменных для одного решения системы для переменных А…Е. Так как решений для переменных А…Е два, то общее количество решений равно 2 ·32 = 64 Ответ: 64 решения

29 Задача 3 Сколько различных решений имеет система уравнений? x1 x2 x3 x4 = 1 x3 x4 x5 x6 = 1 x5 x6 x7 x8 = 1 x7 x8 x9 x10 = 1 где x1,x2,…,x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

30 Решение задачи 3 x1x2Y Рассмотрим в уравнении x1 x2 x3 x4 = 1 первую часть: x1 x2 Введем обозначения: I – номер уравнения Ni – всего решений для i-того уравнения с учетом предыдущих Рi – решения, когда x 2i-1 =0, x 2i =0; x 2i-1 =1, x 2i =0; x 2i-1 =1, x 2i =1; (по 3 решения) Ti – решения, когда x 2i-1 =0, x 2i =1 (по 1 решению) Чтобы x1 x2 x3 x4 = 1 нужно чтобы: x1 x2 = 1, тогда Y= x3 x4 может быть 0 или решения или x1 x2 = 0, тогда Y= x3 x4 может быть решение Итого: 3+1=4 решения IPiTiNi 1314 Для x 1 и x 2 : x3x4Y вторая часть: x3 x4

31 Решение задачи 3 (продолжение) x1x2 х 3 х 3x Рассмотрим уравнение x1 x2 x3 x4=1 При х 1=0, х 2=1, х 3=0, х 4=0 - ложно х 1=0, х 2=1, х 3=1, х 4=0 - ложно х 1=0, х 2=1, х 3=1, х 4=1 – ложно Их не рассматриваем При x1=0 и x2=1 – 1 решение: х 1=0, х 2=1, х 3=0, х 4=1 При x1 = 0 и x2=0 – 3+1 решение: х 1=0, х 2=0, х 3=0, х 4=0 х 1=0, х 2=0, х 3=0, х 4=1 х 1=0, х 2=0, х 3=1, х 4=0 х 1=0, х 2=0, х 3=1, х 4=1 При x1 = 1 и x2=0, а также при x1 = 1 и x2=1 уравнение имеет по 3+1 решению (3*3)+4=13 IPiTiNi P 1 =3, T 1 =1, N 1 =4 P 2 =9, T 2 =4, N 2 =13

32 Решение задачи 3 (продолжение) x1x2x3x4x5x Рассмотрим уравнение x3 x4 x5 x6 = 1: При x3 = 0 и x4=1 – 4 решение: х 3=0, х 4=0, х 5=0, х 6=1 х 3=0, х 4=1, х 5=0, х 6=1 х 3=1, х 4=0, х 5=0, х 6=1 х 3=1, х 4=1, х 5=0, х 6=1 При x3 = 0 и x4=0 – 3+1 решение: х 3=0, х 4=0, х 5=0, х 6=0 х 3=0, х 4=0, х 5=0, х 6=1 х 3=0, х 4=0, х 5=1, х 6=0 х 3=0, х 4=0, х 5=1, х 6=1 При x1 = 1 и x2=0, – 3+1 решение при x1 = 1 и x2=1, – 3+1 решение P 3 =(3*3*3)+13=27+13=40 В таблицe только решения для x3=0 и x4=0 Для х 3=1 и х 4=0, а также для х 3=1 и х 4=1 – добавится по 3*3 строки в таблице. Всего 3*3*3=27 строк IPiTiNi P i =3 i ; T i =N i-1 =T i-1 +P i-1 ; N i =P i +T i

33 Решение задачи 3 (продолжение) Для уравнения x5 x6 x7 x8 = 1(с учетом 1-2) : P 4 = 3 4, Т 4 = N 3 = 40, N 4 = 81+40=121 Для уравнения x7 x8 x9 x10 = 1(с учетом 1-3) : P 5 = 3 5, Т 5 = N 4 = 121, N 5 = =364 Итого: 364 IPiTiNi

34 Задача 4 Сколько различных решений имеет система уравнений? (x1 x2) (x2 x3) (x3 x4) (x4 x5) = 1 (у 1 у 2) (у 2 у 3) (у 3 у 4) (у 4 у 5) = 1 x1 у 1 = 1 где x1,x2,…,x5, у 1,у 2,…,у 5 – логические переменные. В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство.

35 Решение задачи 4 ( x1 x2) ( x2 x3) ( x3 x4) ( x4 x5) = 1 ( y1 y2) ( y2 y3) ( y3 y4) ( y4 y5) = 1 Для x1 x2 ( y1 y2) : Если x1=0, то х 2=0 или х 2=1 (y1=0, то y2=0 или y2=1) Если х 1=1, то х 2=1 (y1=1, то y2=1) Аналогично для x2 x3; x3 x4; x4 x5 y2 y3; y3 y4; y4 y5 Для x1 у 1 = 1 x1=1 – 5 решений y1=1 – 5 решений x1=1 и y1=1 – 1 решение Всего: = 11 решений Х1Х2Х3Х4Х Х1/Y Аналогичная таблица для переменных y1, y2, y3,y4, y5 Импликация x1 x2 ложна, когда х 1=1, а х 2=0 В базовых операциях: x1 x2 = x1 x2

36 Задача 5 Сколько различных решений имеет система уравнений? x1 x2 x3 x4 x5 = 0 у 1 у 2 у 3 у 4 у 5 = 0 x1 у 5 = 1 где x1,x2,…,x5, у 1,у 2,…,у 5 – логические переменные. В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство.

37 Решение задачи 5 ((( x1 x2) х 3 ) х 4 ) х 5 ((х 1 x2) х 3 ) х 4 ) х 5 ((( x1 x2) х 3 ) х 4 ) х 5 =0 Импликация ложна, когда ((( x1 x2) х 3 ) х 4 )=1, а х 5 =0 Операции, имеющие одинаковый приоритет, выполняются слева направо, то есть первой выполняется импликация X 1 X 2, а последней – последняя импликация (((X 1 X 2 ) X 3 ) X 4 ) X 5 Импликация x1 x2 ложна, когда х 1=1, а х 2=0 В базовых операциях: x1 x2 = x1 x2

38 Решение задачи 5 (продолжение) х 1 х 2 х 3 х 4 х 1 х 3 х 4 ABC A= х 1 х 2, B= х 1 х 2 х 3, C= ( х 1 х 2 х 3) х 4

39 Решение задачи 5 (продолжение) х 1 х 2 х 3 х 4 х 1 х 3 х 4 ABC Оставляем в таблице только строки, в которых С=1 Для уравнения у 1 у 2 у 3 у 4 у 5 = 0 получаем аналогичную таблицу y5 =0

40 Решение задачи 5 (продолжение) ¬x y Оставляем в таблице только строки, в которых С=1 Для уравнения у 1 у 2 у 3 у 4 у 5 = 0 получаем аналогичную таблицу Ответ: 66

41 Информационные ресурсы – сеть творческих учителей kpolyakov.narod.ru – сайт К.Ю. Полякова kpolyakov.narod.ru – сайт Дмитрия Тарасова сайт ФИПИ