Презентация по информатике на тему Решение логических задач при подготовке к ЕГЭ
Сергеенкова ИМ - 1191Автор: Сергеенкова И.М., учитель информатики.ГБОУ Школа № 1191Г. МоскваРешение логических задачпри подготовке к ЕГЭ
Для логических величин обычно используются три операции:Конъюнкция – логическое умножение (И) –and, &, ∧.Дизъюнкция – логическое сложение (ИЛИ) –or, |, v.Логическое отрицание (НЕ) – not, ¬.Что нужно знать для решения задач:4. Импликация - логическое следование А В5. Эквивалентность - логическое равенство А ВДополнительные логические операции:
Логические выражения можно преобразовывать в соответствии с законами алгебры логики:Законы рефлексивностиa ∨ a = aa ∧ a = aЗаконы коммутативностиa ∨ b = b ∨ aa ∧ b = b ∧ aЗаконы ассоциативности(a ∧ b) ∧ c = a ∧ (b ∧ c)(a ∨ b) ∨ c = a ∨ (b ∨ c)
Законы дистрибутивностиa ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)Закон отрицания отрицания¬ (¬ a) = aЗаконы де Моргана¬ (a ∧ b) = ¬ a ∨ ¬ b¬ (a ∨ b) = ¬ a ∧ ¬ bЗаконы поглощенияa ∨ (a ∧ b) = aa ∧ (a ∨ b) = a
Таблицы истинностиЛогические операции удобно описывать так называемыми таблицами истинности, в которых отражают результаты вычислений сложных высказываний при различных значениях исходных простых высказываний. Простые высказывания обозначаются переменными (например, A и B).
ДизъюнкцияКонъюнкцияИнверсияИмпликацияЭквивалентность
Сергеенкова ИМ - 1191Задание 1. Сколько различных решений имеет уравнение (K v L v M) ^ (¬L ^ ¬M ^ N) = 1, где K, L, M, N – логические переменные?Решение задачи № 1Высказывание (K v L v M) ^ (¬L ^ ¬M ^ N) истинно только в том случае, когда истинны оба высказывания (K v L v M) и (¬L ^ ¬M ^ N).Второе из этих высказываний, (¬L ^ ¬M ^ N), истинно только при L = 0, M = 0, N = 1.При найденных значениях L и M первое высказывание, (K v L v M), истинно, если K = 1.Ответ: уравнение имеет только одно решение.
Сергеенкова ИМ - 1191Задание 2. Сколько различных решений имеет уравнение (K ^ L) v (M ^ N) = 1, где K, L, M, N – логические переменные?
Сергеенкова ИМ - 1191Решение задачи № 2Высказывание (K ^ L) v (M ^ N) истинно, когда истинно хотя бы одно из высказываний (K ^ L), (M ^ N).Первое из этих высказываний, (K ^ L), истинно при K = 1, L = 1, а поскольку второе высказывание при этом может принимать любое значение, то для M и N следует учитывать четыре различных набора: (0, 0), (0, 1), (1, 0), (1, 1).Второе из этих высказываний, (M ^ N), истинно при M = 1, N = 1, а поскольку первое высказывание при этом может принимать любое значение, то для K и L следует учитывать четыре различных набора: (0, 0), (0, 1), (1, 0), (1, 1). Последний из этих наборов следует исключить, т.к. он уже учитывался ранее, когда M и N могли принимать любые значения. Ответ: таким образом, уравнение имеет 7 решений.
Сергеенкова ИМ - 1191Задание 3. Укажите значения переменных K, L, M, N, при которых логическое выражение (K -> M) v (L ^ K) v ¬N ложно.Ответ запишите в виде строки из четырех символов: значений переменных K, L, M, N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K =1, L = 1, M = 0, N = 1.
Сергеенкова ИМ - 1191Решение задачи 3.Высказывание (K -> M) v (L ^ K) v ¬N ложно, когда ложны все высказывания K -> M, L ^ K, ¬N.Первое из этих высказываний, K -> M, ложно, если K = 1, M = 0.Второе из этих высказываний, L ^ K, при K = 1 ложно, если L = 0.Третье из этих высказываний, ¬N, ложно, если N = 1.Таким образом, значения переменных, при которых логическое выражение, заданное в условии задачи, ложно: 1001. Ответ: 1001.
Задача 4Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?(x1->x2) / (x2->x3) / (x3->x4) / (x4->x5 ) = 1(y1->y2) / (y2->y3) / (y3->y4) / (y4->y5 ) = 1x1/y1 =1В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.Решение.
Решение задачи 4Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k] = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в наборе – значение x1, 2-я цифра в наборе – значение x2 и т.д.):00000, 00001, 00011, 00111, 01111, 11111Второе уравнение имеет 6 аналогичных решений (1-я цифра в наборе – значение y1, 2-я цифра в наборе – значение y2 и т.д.):00000, 00001, 00011, 00111, 01111, 11111Решение системы – пара таких наборов. Ввиду третьего уравнения, один наборов в паре должен быть набором 11111. Таких пар – 11: {11111, 11111}, 5 пар вида {11111, R} и 5 пар вида {R, 11111}, здесь R – один из наборов 00000, 00001, 00011, 00111, 01111.Ответ: 11
Замечание к задаче 4. На первый раз выпишем все решения явно:{11111, 00000}; {11111, 00001}; {11111, 00011}; {11111, 00111}; {11111, 01111};{11111, 11111}{00000, 11111}; {00001, 11111}; {00011, 11111}; {00111, 11111}; {01111, 11111};{11111, 11111}Написано 12 пар, но решений — 11. Выделенная жирным пара {11111, 11111} написана 2 раза!
Пример 5. Упростить выражения так, чтобы в полученных формулах не содержалось отрицания сложных высказываний. Решение:
Задание 6Для какого из указанных значений X истинно высказывание¬ ((X>2) → (X>3))? 1) 12) 23) 34) 4Решение:Высказывание истинно, если выражение в скобках ложно. Импликация ложна тогда и только тогда, когда посылка истинна, а следствие ложно. Посылка истинна в вариантах 3 и 4, однако вариант 4 не подходит, так как в таком случае следствие истинно. Следовательно ответ 3.
Задание 7Для какого из названий животных ложно высказывание: (Заканчивается на согласную букву) Λ (B слове 6 букв) → (Четвертая буква согласная)? 1) Страус2) Леопард3) Верблюд4) КенгуруРешение:В первую очередь выполняется логическое "И".Импликация ложна только тогда, когда посылка истина, а следствие ложно. Посылка {(Заканчивается на согласную букву) Λ (B слове 6 букв)} истина для варианта один, а следствие {(Четвертая буква согласная)} для него ложно. Следовательно, ответ 1.
Задание 8Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)? 1) A \/ B2) A /\ B3) ¬A \/ ¬B4) ¬A /\ BРешение:¬ (А \/ ¬B) = ¬ A /\ ¬ (¬B) = ¬ A /\ B. Правильный ответ 4.
Задание 9На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула ( (x ∈ А) → (x ∈ P) ) ∨ (x ∈ Q)тождественно истинна, то есть принимает значение 1 при любом значении переменной х. 1) [0, 3]2) [3, 11]3) [11, 15]4) [15, 17]
Решение задачи 9Введем обозначения:(x ∈ А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.Применив преобразование импликации, получаем:¬A∨P∨Q.Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Выражение P ∨ Q истинно на отрезке [2; 14]. Поскольку все выражение должно быть истинно для любого x, выражение ¬A должно быть истинно на множестве (−∞; 2) ∪ (14; ∞). Таким образом, выражение A должно быть истинно только внутри отрезка [2;14].Из всех отрезков только отрезок [3; 11] полностью лежит внутри отрезка [2; 14].Ответ: 2
Источники информации:http://2krota.ru/uploads/posts/2011-12/ZnaeteliVifakt-0020.jpghttp://www.inf1.info/image/logic-computer/logichttp://2012.ege-go.ru/zadania/grb/b15/b15-answ/#B15.1http://infolike.narod.ru/logic.htmlhttp://www.ido.rudn.ru/nfpk/inf/inf7.htmlhttp://inf.reshuege.ru/test?theme=233