Решение заданий формата ЕГЭ по теме «Логика»

Решение заданий формата ЕГЭ по теме «Логика»

по курсу вариативного учебного модуля

«Методика подготовки к государственной итоговой аттестации по отдельным темам курса информатики и ИКТ в форме ЕГЭ»

Слушатель:

Шпак Наталия Петровна

учитель информатики

МБОУ «Гимназия №5 г. Сергиева Посада»

г.Сергиев Посад

Московской области

В материалах КИМ по информатике задания по теме «Логика» представлены в заданиях №2, №17, №18 и №23. Разбор заданий надо начинать с заданий базового уровня (№2, №17) и заканчивать заданиями повышенного уровня сложности (№18, №23). В данной работе представлена методика изучения задания №2 и №18.

Решение задания№2. В соответствии со спецификацией экзамена, проверяемым элементом задания №2является умение строить таблицы истинности и логические схемы. Задание №2 предусматривает проверку основных понятий алгебры логики, знание базовых операций, а также навыков преобразования простых логических выражений. Задание №2 не вызывает сложность у обучающихся, но требует обязательного рассмотрения.

Общий алгоритм решения задания №2:

преобразовать (переписать) на понятный ученику язык;

упростить, если необходимо выражение, применив законы алгебры логики;

использовать метод рассуждения или записать СКНФ\СДНФ функции.

Задания учителю необходимо составлять таким образом, чтобы постепенно переходить от простого к более сложному, от простых преобразований к сложным.

Теоретическая часть. При выполнении данного задания необходимо обратить внимание ученика на то, что:

таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных;

если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений;

количестворазных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 2³=8 строчек, если заданы только 6 из них, то можно найти 2^8-6=2²=4разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)

логическая сумма A + B + C + … равна 0 тогда и только тогда, когда все слагаемые одновременно равны нулю

логическое произведение A · B · C · … равно 1 тогда и только тогда, когда все сомножители одновременно равны единице

логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A истинна, а B ложно;

эквивалентность АB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1.

если функция на наборах равна 1, то её можно записать в виде СДНФ (совершенно дизъюнктивная нормальная формата), инвертируя при этом те переменные, которые равны 0.

если функция на наборах равна 0, то её можно записать в виде СКНФ (совершенно конъюнктивная нормальная формата), инвертируя при этом те переменные, которые равны 1.

Функцию, заданную в виде ДНФ(КНФ) (дизъюнктивная \конъюнктивная нормальная форма) можно привести к СДНФ(СКНФ), используя известные тождества алгебры логики:

a ∙ 1 = a и .

Примеры заданий.

Какое выражение соответствует F?

1) ¬X  ¬Y  ¬Z 2) X  Y  Z3) X  ¬Y  ¬Z

4) X  ¬Y  ¬Z

Решение:

перепишем ответы в других обозначениях, на понятном языке ученику:
1) 2) 3) 4)

в столбце F есть единственная единица для комбинации , простейшая функция, истинная (только) для этого случая, имеет вид , она есть среди приведенных ответов (ответ 3)

Пример 2. Дан фрагмент таблицы истинности выражения F.

Одно из приведенных ниже выражений истинно при любых значениях переменных x1, x2,x3, x4, x5. Укажите это выражение.

1) F(x1,x2,x3,x4,x5)x1

2) F(x1,x2,x3,x4,x5)x2

3) F(x1,x2,x3,x4,x5)x3

4) F(x1,x2,x3,x4,x5)x4

Решение:

во всех заданных ответа записана импликация, она ложна только тогда, когда левая часть (значение функции F) истинна, а правая – ложна.

выражение 1 ложно для набора переменных в третьей строке таблицы истинности, где F(…) = 1 и , оно не подходит

выражение 2 ложно для набора переменных в третьей строке таблицы истинности, где F(…) = 1 и , оно не подходит

выражение 3 истинно для всех наборов переменных, заданных в таблице истинности

выражение 4 ложно для набора переменных в первой строке таблицы истинности, где F(…) = 1 и , оно не подходит. Ответ: 3.

Пример 3.Логическая функция F задаётся выражением (x  ¬y  ¬z)  (¬x y). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x,y,z?

В ответе напишите буквы x,y,z в том порядке, в котором идут соответствующие им столбцы.

Способы решения:

1. Метод рассуждения.

Чтобы функция была равна 1, нужно чтобы каждая скобка была равна 1.

Уравнение имеет 3 решения: 00, 01 и 11. Подставим найденные решения в первую скобку и найдем полный набор решений . Ответ: zyx

2. Представление в виде СКНФ и СДНФ.

Исходная функцию задана в виде КНФ, которую можно привести к СКНФ, используя известные тождества алгебры логики: , и распределительный закон для операции «И» .

Вторую дизъюнкцию дополним недостающей переменной z:

Применим правило образования СКНФ: для тех наборов переменных, на которых функция СКНФ равна нулю, необходимо инвертировать не переменные, которые равны единицы.

Ответ: zyx

Вывод: Если учащиеся хорошо знают законы алгебры логики и умет упрощать выражения, а также хорошо владеют навыками записи СКНФ и СДНФ функции, то они прекрасно решат задание№2.

Решение задания№18. В соответствии со спецификацией экзамена, задание №18предусматривает проверку знаний основных понятий и законов алгебры логики, навыков преобразования логических выражений, построения таблиц истинности.

Рекомендуемая схема выполнения задания №18

Преобразование логических выражений

Определение элементарных высказываний.

Замена переменных (при необходимости).

Раскрытие импликации или эквиваленции.

Построение таблиц истинности.

Преобразование с использованием законов алгебры логики.

Применение метода решения

Запись ответа

Задание №18 представлено в двух видах:

задания с отрезками и множествами;

задания с битовыми операциями и делителями.

Задания с отрезками и множествами.

Теоретическая часть. Связь логики и теории множеств:

пересечение множеств соответствует умножению логических величин, а объединение – логическому сложению;

пустое множество  – это множество, не содержащее ни одного элемента, оно играет роль нуля в теории множеств;

универсальное множество  – это множество, содержащее все возможные элементы заданного типа (например, все целые числа), оно играет роль логической единицы: для любого множества целых чисел X справедливы равенства X + I = I и X · I = X (для простоты мы используем знаки сложения и умножения вместо знаков пересечения  и объединения  множеств)

дополнениемножестваX – это разность между универсальным множеством I и множеством X (например, для целых чисел – все целые числа, не входящие в X)

пусть требуется выбрать множество A так, чтобы выполнялось равенство A + X = I; в этом случае множество A должно включать дополнение , то есть

пусть требуется выбрать множество A так, чтобы выполнялось равенство , в этом случае множество должно включать дополнение , то есть

Примеры заданий

Пример1. На числовой прямой даны два отрезка: 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]

Решение:

обозначим высказывания буквами

A: x  А, P: x  P, Q: x  Q

тогда получаем, переходя к более простым обозначениям:

Z = (A→P) + Q

представим импликацию: и получаем

это значит, что Z =1 тогда и только тогда, когда справедлива формула , значит A=P+Q

построим отрезкиP иQ и увидим , что А [2,14], а значит только отрезок [3,11] лежит внутри отрезка [2,14]

Ответ: 2.

Пример 2.Элементами множества А являются натуральные числа. Известно, что выражение

(x{2, 4, 6, 8, 10, 12}) → (((x{4, 8, 12, 116})  ¬(xA)) → ¬(x{2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение:

обозначим отдельные высказывания буквами

A: x  А, P: x  P, Q: x  Q

перейдем к более простым обозначениям, раскроем импликацию, применим закон де Моргана

тогда А= – это все натуральные числа, которые входят одновременно в = {4, 8, 12, 116} и = {2, 4, 6, 8, 10, 12}, а это {4, 8, 12}

сумма этих чисел равна 24

Ответ: 24.

Задания с битовыми операциями

Теоретическая часть. Для решения этих задач удобно применять метод, предложенный А.В. Здвижковой.

Введём обозначения Это означает, что если истинно , то это равносильно тому, что истинно . Для сокращения записи вместо будем писать просто . Пусть в двоичной записи числа K бит с номером i, обозначаемый как k_i, равен 1. Если при этом для некоторого x выполнено условие , то соответствующий i-й бит в двоичной записи числа x равен нулю, так как должно выполняться условие .

Для преобразования выражений полезно следующее свойство:

где «or» означает поразрядную дизъюнкцию между двумя числами

Самый важный результат можно сформулировать так:

Условие для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

Для упрощения выражений полезен следующий результат:

Условие при любых натуральных K, M и N ложно для некоторых натуральных значений x.

Метод, предложенный А.В. Здвижковой заключается в следующем:

Упростить заданное выражение, сведя его к импликации, в которой нет инверсий

Применить полученные выше результаты для нахождения всех подходящих значений неизвестного числа a, включая минимальное и максимальное значения

Пример 3. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение

( (x & 28  0)  (x & 45  0))  ((x & 48 =0) (x & a0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменнойx)?

введём обозначения: Z₂₈ = (x & 28 = 0), Z₄₅ = (x& 45 = 0), Z₄₈ = (x& 48 = 0), A = (x&a= 0)

перепишем исходное выражение и преобразуем его, используя свойство импликации:

перейдем к импликации, используя закон де Моргана:

преобразуем выражение в правой части по формуле , выполнив поразрядную дизъюнкцию (операцию ИЛИ):

28 = 011100

45 = 101101

or 45 = 111101 = 61

получаем

для того, чтобы выражение нужно, чтобы двоичная запись числа 48ora содержала все единичные биты числа 61. Таким образом, с помощью числа a нужно добавить те единичные биты числа 61, которых «не хватает» в числе 48:

48 = 110000

a = **11*1

61 = 111101

поскольку нас интересует минимальное значениеa, все биты, обозначенные звездочкой, можно принять равными нулю, получается A = 2³ + 2² + 2⁰ = 13

Ответ: 13.

Пример 4. Обозначим через ДЕЛ(n,m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

(ДЕЛ(x,А)  ДЕЛ(x, 12))  (ДЕЛ(x, 42)  ¬ДЕЛ(x, 12))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменнойх)?

Решение.

введём обозначения: Z_А = ДЕЛ(x,А) ,Z₁₂ = ДЕЛ(x, 12), Z₄₂ = ДЕЛ(x, 42)

2) перепишем исходное выражение и преобразуем его, используя свойство импликации

3) для того, чтобы выражение нужно, чтобы делители числа А дополняли делители числа 12 до числа 42: делители 12 - 3,2, числа 42 - 2,3,7, значит делители числа А-7.

Ответ: 7.

Задания для самостоятельной работы

Логическая функция F задаётся выражением . На рисунке приведён фрагмент таблицы истинности функции F. Определите, какому столбцу таблицы истинности функции Fсоответствует каждая из переменных x,y,z.

В ответе напишите буквы x,y,z в том порядке, в котором идут соответствующие им столбцы.

На числовой прямой даны два отрезка: P = [25, 37] и Q = [32, 50]. Отрезок A таков, что формула

( (xA)  ¬(xQ)) → ( (xP)  (xQ))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Какова наибольшая возможная длина отрезка A?

Определите наименьшее натуральное число A, такое что выражение

(X & 56 0)  ((X& 48 = 0)  (X& A  0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменнойX)?

Обозначим через ДЕЛ(n,m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

(¬ДЕЛ(x,А)  ДЕЛ(x, 6))  ¬ДЕЛ(x, 3)

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменнойх)?

Список электронных ресурсов.

1. Сайт Полякова К. http://kpolyakov.spb.ru

2. Тематические тесты http://ege.yandex.ru

3. Решу ЕГЭ https://inf-ege.sdamgia.ru

4. http://www.informatika-1332.ru

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/306690-reshenie-zadanij-formata-egje-po-teme-logika