Презентация по информатике Методика обучения теме «Логика» в профильном курсе. Решение задач ЕГЭ 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