Презентация по информатике Методика обучения теме «Логика» в профильном курсе. Решение задач ЕГЭ 17, 18

Методика обучения теме «Логика» в профильном курсе. Решение задач ЕГЭ 17, 18Коровина Е.А. Что нужно знать? Решение задач 1) Формулировка задачи: Элементами множества А являются натуральные числа. Известно, что выражение(x Î {2, 4, 6, 8, 10, 12}) → (((x Î {3, 6, 9, 12, 15})   ¬(x Î A)) → ¬(x Î {2, 4, 6, 8, 10, 12}))истинно (т. е. принимает значение 1) при любом значении переменной х.Определите наименьшее возможное значение суммы элементов множества A. Решение:Введем обозначения:P ≡ (x Î {2, 4, 6, 8, 10, 12});Q ≡ (x Î {3, 6, 9, 12, 15}) ;A ≡ (x Î A).Преобразовав исходное выражение, получаем:P → ((Q  ¬A) → ¬P)= P → (¬(Q  ¬A)  ¬P)= =P → (¬ Q  A  ¬P)= ¬ P  ¬ Q  A  ¬P= ¬ P  ¬ Q  A Поскольку, ¬ P  ¬ Q  A = 1, то А должно быть истинным везде, где ложно (¬ P  ¬ Q ), тогда минимально допустимое множество:А𝑚𝑖𝑛= ¬(¬ P  ¬ Q ) = P  Q (P  Q) обозначает пересечение двух множеств P и Q, т.е. множество 6, 12.Соответственно, А𝑚𝑖𝑛=6, 12.Сумма элементов множества А равна 6+12=18.Ответ: 18  2) Формулировка задачи: Элементами множества А являются натуральные числа. Известно, что выражение¬(x Î {2, 4, 6, 8, 10, 12})  (¬(x Î {3, 6, 9, 12, 15}) → (x Î A))истинно (т. е. принимает значение 1) при любом значении переменной х.Определите наименьшее возможное значение произведения элементов множества A. Решение:Введем обозначения:P ≡ (x Î {2, 4, 6, 8, 10, 12}) ;Q ≡ (x Î {3, 6, 9, 12, 15}) ;A ≡ (x Î A).Преобразовав исходное выражение, получаем:¬ P  (¬ Q → A) = ¬ P  Q  A = 1 Поскольку, ¬ P  Q  A = 1, то А должно быть истинным везде, где ложно (¬ P  Q ), тогда минимально допустимое множество:А𝑚𝑖𝑛= ¬(¬ P  Q ) = P  ¬ Q (P  ¬ Q) – это множество чисел, принадлежащих множеству Р и не принадлежащих множеству Q, т.е. множество 2, 4, 8, 10.Соответственно, А𝑚𝑖𝑛=2, 4, 8, 10.Произведение элементов множества А равно 2*4*8*10=640.Ответ: 640  3) Формулировка задачи: Сколько различных решений имеет уравнение(K  L  M)  (¬L  ¬M  N) = 1где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. Решение:Дизъюнкция истинна, когда хотя бы одно из выражений истинно.(K  L  M) = 1 или (¬L  ¬M  N) = 1 Логические переменные L и M являются зависимыми друг от друга, переменные K и N – независимы. Каждое выражение является конъюнкцией логических переменных и истинно, только в том случае, когда истинны все высказывания, входящие в данное выражение. Значит, для выражения (K  L  M) = 1 существует единственный вариант решения, когда K=1, L=1, M=1, но независимая переменная N может принимать любое значение (либо 1, либо 0), следовательно вариантов решения уже 1*2=2.Подобным образом находим варианты решения выражения (¬L  ¬M  N) = 1, учитывая, что переменная K тоже независима и может принимать любое значение. Получаем тоже 2 варианта решения. Складывая все полученные результаты, получаем 2+2=4. Ответ: уравнение имеет 4 решения 4) Формулировка задачи: Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формулаДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Решение:Введём обо­зна­че­ния: A = ДЕЛ(x, А), D14 = ДЕЛ(x, 14), D21 = ДЕЛ(x, 21).Введём мно­же­ства:A — мно­же­ство на­ту­раль­ных чисел, для ко­то­рых вы­пол­ня­ет­ся усло­вие A,D14 — мно­же­ство на­ту­раль­ных чисел, для ко­то­рых вы­пол­ня­ет­ся усло­вие D14,D21 — мно­же­ство на­ту­раль­ных чисел, для ко­то­рых вы­пол­ня­ет­ся усло­вие D21. Исходное выражение принимает вид:А (D14  D21) = 1.Преобразуем данное выражение:А (D14  D21) = ¬ А  D14  D21=1.Составим таблицу истинности:{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}Значения xD14 D21D14  D21¬ ААА (D14  D21) = =¬ А  D14  D21 14100101210101012810010142111ЛюбоеЛюбое 156100101 Порядок заполнения таблицы:Заполняем значения х, входящие в состав множеств D14 и D21 , заполняем значения логического выражения (D14  D21 ), заполняем единицами значения выражения А (D14  D21) = ¬ А  D14  D21, т.к. по условию дано, что это выражение истинно,Заполняем значения ¬ А,Заполняем значения А. По условию задачи необходимо найти наименьшее натуральное число из множества А, значит, выбираем первый вариант решения, где значение А может быть любым. В данном случае, это число 42.Ответ: 42 4) Формулировка задачи: Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение(X & 102 <> 0)  ((X & 36 = 0)  (X & A <> 0))тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)? Решение:Упростим выражение (заменим импликации дизъюнкциями):(X & 102 <> 0)  ((X & 36 = 0)  (X & A <> 0)) = = (X & 102 <> 0)  ((X & 36 <> 0)  (X & A <> 0)) = = (X & 102 = 0)  ((X & 36 <> 0)  (X & A <> 0)) = = (X & 102 = 0)  (X & 36 <> 0)  (X & A <> 0).Для того, чтобы выражение (X & 102 = 0)  (X & 36 <> 0)  (X & A <> 0) было истинно достаточно, чтобы хотя бы одно из логических выражений было истинно. Рассмотрим первой выражение (X & 102 = 0):Найдем все значения х, при которых (X & 102 = 0) истинно. Для этого переведем 102 в двоичную систему счисления: 102 = 11001102. Проанализируем поразрядную конъюнкцию числа 11001102 с числом Х2Вывод: выражение не получит истину для чисел Х, у которых в двоичной системе счисления есть 1, 2, 5, 6 биты равные «1»{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}Номер бита (разряда)6543210Пронумеруйте биты (разряды) в двоичном числе 11001102102 = 1100110Если в числе Х 0, 3, 4, 7 и т.д. биты равны «1» или «0», то после поразрядной конъюнкции все равно на месте 0, 3, 4, 7 и т.д. будут нули.Если в числе Х 1, 2, 5, 6 биты равны «1», .то после поразрядной конъюнкции на этих местах будут единицы. Следовательно, мы не получим 0, как нужно по условию (X & 102 = 0) .Х=1111111 Рассмотрим второе выражение (X & 36 <> 0)Только для 1, 2, 5 и 6 битов, равных «1» (для всех остальных чисел Х, первое слагаемое даст истину).Для этого переведем 36 в двоичную систему счисления: 36 = 1001002. Проанализируем поразрядную конъюнкцию числа 1001002 с числом Х2Вывод: выражение не получит истину для чисел Х, у которых в двоичной системе счисления есть 1 и 6 биты равные «1»{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}Номер бита (разряда)6543210Пронумеруйте биты (разряды) в двоичном числе 1100110236 = 0100100Если в числе Х 2 и 5 биты равны «1» , то после поразрядной конъюнкции все равно на 2 и 5 месте будут единицы.Если в числе Х 1, и 6 биты равны «1», .то после поразрядной конъюнкции на этих местах будут единицы. Следовательно, мы получим 0, а по условию (X & 36 <> 0) .Х=11**11* Все неучтенные биты нужно добавить в третье логическое выражение (X & A <> 0).Так как у нас остались неучтенными биты 2 и 5, то в числе А обязательно 2 и 5 биты должны быть равны «1».А = 1001002= 36 (это минимальное число А).Ответ: 36