Методика проведения практикума-интенсива по решению задач ЕГЭ по разделу "Алгебра логики"
методическая разработка по информатике и икт (10, 11 класс) на тему

Бергер Полина Григорьевна, учитель информатики и ИКТ высшей квалификационной категории
МБОУ «Гимназия № 96», г. Казань, Республика Татарстан

МЕТОДИКА ПРОВЕДЕНИЯ ПРАКТИКУМА-ИНТЕНСИВА
ПО РЕШЕНИЮ ЗАДАЧ ЕГЭ

ПО РАЗДЕЛУ «ОСНОВЫ АЛГЕБРЫ ЛОГИКИ»

Логика - это Бог мыслящих.

Л. Фейхтвангер.

Введение

Раздел «Основы алгебры логики» - один из сложнейших в курсе информатики. В КИМ ЕГЭ по информатике присутствуют задания базового и повышенного уровня сложности, для решения которых требуются глубокие теоретические познания и хорошо сформированные практические навыки.  Выпускники, изучающие информатику на базовом уровне, при подготовке к ЕГЭ сталкиваются с объективными  трудностями. Во-первых, в учебниках базового уровня эта тема рассматривается в усеченном варианте и поверхностно в рамках тем «Базы данных» и «Электронные таблицы». Во-вторых, сложность задач за последние годы резко возросла, о чем свидетельствует значительное снижение результатов сдачи ЕГЭ по информатике. Так, по данным Минобрнауки, средний тестовый балл понизился с 63,5 в 2013 г. до 57,2 в 2014 г. и 54 балла в 2015 г. С заданием №18 «Проверка истинности логического выражения» в 2015 году справились менее 15% выпускников. С заданием №23 «Системы логических уравнений» в 2015 году справились менее 5 % выпускников [1, 2].

В настоящее время в сети Интернет широко представлены материалы по подготовке к ЕГЭ по информатике, где дается обширный материал по теории, разбор типовых задач, а также предлагаются тесты on-line. Однако учащимся и учителям необходимы методические материалы, в которых в сжатой форме разбираются оптимальные методы решения и тематические подборки заданий с ключами для экспресс-подготовки к экзамену по информатике.

Данная методическая разработка предназначена для учителей, которые обучают информатике на базовом уровне и готовят учеников ЕГЭ по предмету. Она содержит методические рекомендации и дидактические материалы для проведения занятий в формате практикума-интенсива по разделу «Основы алгебры логики». Материалы для практикума будут интересны и полезны выпускникам при  подготовке к экзаменам и при углубленном изучении раздела «Основы алгебры логики».

При подготовке учащихся к ЕГЭ по информатике учитель информатики зачастую сталкивается с их неумением самостоятельно решать задачи по разделу «Основы алгебры логики». В приведенной ниже таблице перечислены вопросы, стоящие перед учителем, и способы их разрешения.

Табл.1

Проанализировав ошибки учащихся при решении задач ЕГЭ по теме «Основы алгебры логики», мы обозначили следующие проблемы и наметили пути их решения.

Табл.2

Для решения этих проблем было принято решение разработать серию занятий в формате практикума-интенсива.

Методика подготовки и проведения практикума-интенсива [4]:

1. Учитель готовит опорный конспект по теме практикума.
2. Накануне каждый ученик получает опорный конспект и задание выучить ту его часть, которая пригодится на практикуме.
3. В начале практикума обязательна разминка – опрос по теории или разбор домашнего задания в высоком темпе, обучающий тест.
4. Практика в решении задач проводится с помощью специальной подборки задач, состоящей из 2-х вариантов задач различных типов возрастающей сложности.
5. Учитель заранее распечатывает 2 варианта работы: сначала задачу из 1-го варианта решают у доски, при этом обсуждаются эффективные приемы решения, затем учащимся предлагается самостоятельно решить подобную задачу из 2-го варианта.
6. Задание на дом содержит задачи повышенной сложности.

Алгоритм изучения условия задачи для определения проверяемых умений учащихся и выбора вспомогательных материалов

Обзор задач демо-версии ЕГЭ-2016 года по теме «Основы алгебры логики» 
(см. Приложение 2)

1. Тема «Составление таблицы истинности логической функции»
   (задание №2)

а)        Преобразуем логическую функцию, применив сначала распределительный закон, а затем формулу исключения импликации:

(¬z)∧x ∨ x∧y = x∧ ((¬z) ∨ y) = x∧ (z → y);

б)         Анализируем приведенную таблицу истинности:

• Чего меньше в столбце значений F: единиц или нулей? Единиц.
•  В каких случаях выражение x∧ (z → y) истинно? Когда х и импликация (z → y) истинны. Значит, переменная, которая истинна при истинности F, - это х (переменная 3).
• Замечаем, что что на наборе 101 х – истина, а F – ложь. Это означает, что (z → y) – ложь, а это возможно только при z = 1 и
  y= 0.
• Вывод: переменной 1 соответствует z, а переменной 2 – y.
• Запишем ответ: zyx

2. Тема «Поиск информации в Интернете» (задание №17)

• Строим диаграммы Эйлера-Венна для 3-ёх множеств: Гомер, Илиада и Одиссея; нумеруем каждую область цифрами от 1 до 7  и выделяем искомую область;
• Гомер & Илиада – пересечение этих множеств (5 + 7); Гомер & (Одиссея | Илиада) – пересечение множества Гомер с объединением множеств Одиссея и Илиада (4 + 5 + 7); Гомер & Одиссея – их пересечение (4 + 7);
• Составим систему уравнений, обозначив через Ni количество запросов соответствующей области:
  N5 + N7 =200

N4 + N5 + N7 = 470

N4 + N7 = 355

• Найдем N4  из 2-го уравнения: 470 - N5 + N7 = 470 – 200 = 270;
• Искомое количество запросов N7 = 355 – 270 = 85.

3. Тема «Проверка истинности логического выражения» (задание №18)

• Введем обозначения: P = x & 25 ≠ 0; Q = x & 17 ≠ 0; A = x & A ≠ 0.
• Перепишем исходную формулу в виде: P → (Q → A) = 1.
• Преобразуем логическое выражение, используя формулу исключения имплиации: ¬ P ∨ Q ∨ A = 1.
• А будет принимать наименьшее значение, когда выражение ¬ P ∨ Q будет ложно.
• ¬ P ∨ Q = 0 при P = 1; Q = 0.
• Переведем числа 25 и 17 в двоичную систему счисления, представив их в виде суммы степеней числа 2:

2510 = 16 + 8 + 1 = 24 + 23 + 20 = 110012;

1710 = 16 + 1 = 24 + 20 = 100012.

• Составим таблицу истинности, где число x – разрядное слагаемое двоичной системы счисления из множества {1, 2, 4, 8, 16, 32}:

• В столбце A  проставляем 1 в тех строках, где P = 1 и Q = 0.
• Из таблицы видно, что А содержит двоичный разряд на позиции, соответствующей числу 8. Это искомое число.

4. Тема «Решение систем логических уравнений» (задание №23)

Для решения данной системы логических уравнений используем метод замены независимых переменных.

• Обозначим: z1 = (x1 ≡ y1); z2 = (x2 ≡ y2); z3 = (x3 ≡ y3); z4 = (x4 ≡ y4);
  z5= (x5 ≡ y5); z6 = (x6 ≡ y6); z7 = (x7 ≡ y7); z8 = (x8 ≡ y8); z9 = (x9 ≡ y9);
• Перепишем систему:

¬ z1 ≡ z2

¬ z2 ≡ z3

. . .

¬ z8 ≡ z9

• Заполним таблицу истинности, предположив сначала, что z1 = 0
  (1- строка), а затем z1 = 1:

• Возвращаемся к замене. Zi – это эквиваленция. По свойству эквиваленции zi = 0 в 2-ух случаях, когда xi и yi различны, и zi = 1 также в 2-ух случаях, когда xi и yi имеют одинаковые значения.
• Перемножив количество вариантов в первой строке, получим:

2*2*2*2*2*2*2*2*2 = 29 =  512;

• Аналогично во второй строке таблицы получим еще 512 вариантов.
• Итого в сумме 1024 решения.

Объем данной статьи не позволяет подробно разобрать решения всех приведенных задач. В своей работе мы опираемся на материалы популярного сайта К.Ю. Полякова[6], сайта distan-school.ru, а также на рекомендации по выбору оптимальных способов выполнения заданий ЕГЭ Чупина Н.А. [3]. Назовем лишь некоторые приемы и методы решения систем логических уравнений:

1. Метод рассуждений;
2. Метод независимой замены переменных;
3. Упрощение логических выражений;
4. Метод отображения;
5. Метод битовых цепочек.

Заключение и выводы

Данная методика в течение 2013-14 г., 2014-15, 2015 16 уч.г.г. была апробирована в классах физико-математического профиля МБОУ «Гимназия №96» Вахитовского района города Казани Республики Татарстан. Ее эффективность подтверждают следующие данные:

• повысилось качество знаний по изучаемой теме (с 71% до 86%);
• средний балл ЕГЭ в 2014 г. составил 74 балла;

Методика проведения практикумов-интенсивов по решению задач ЕГЭ демонстрировалась на мастер-классах для слушателей курсов повышения квалификации учителей информатики и заслужила положительные отзывы учителей-практиков. Данные мастер-классы проводились в рамках инновационной деятельности автора по теме «Применение современных педагогических технологий на уроках информатики по решению задач повышенной сложности» в рамках республиканской инновационной площадки «Актуальные проблемы реализации ФГОС общего образования» на базе Приволжского межрегионального центра повышения квалификации и профессиональной подготовки работников образования Казанского (Приволжского) Федерального университета.

Список источников и литературы

1. В.Р. Лещинер Методические рекомендации по некоторым аспектам совершенствования преподавания информатики и ИКТ (www.fipi.ru/sites/default/files/document/1410157306/informatika_i_ikt.pdf)
2. В.Р. Лещинер, М.А. Ройтберг Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по ИНФОРМАТИКЕ и ИКТ, М, 2015 (http://fipi.ru/ege-i-gve-11/analiticheskie-i-metodicheskie-materialy )
3.  Чупин Н.А. Подготовка к ЕГЭ по информатике: оптимальные способы выполнения заданий/ Н.А. Чупин. – Ростов н/Д: Феникс, 2013. – 105 [1] с.: ил. – (Абитуриент).
4. Бергер П.Г. Методика проведения практикума-интенсива по решению задач ЕГЭ по разделу «Основы информатики», сетевое издание «Образование: эффективность, качество, инновации», №»3, 2015 г. effektiko.ru/journal?p=7579
5. Материалы сайта http://distan-school.ru
6. Материалы сайта  http://kpolyakov.spb.ru

Приложение 1: ОПОРНЫЙ КОНСПЕКТ ПО ТЕМЕ «АЛГЕБРА ЛОГИКИ»

• логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
• логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
• логическое следование (импликация) А→В равна 0 тогда и только тогда, когда  A (посылка) истинна, а B (следствие) ложно
• эквивалентность А≡B  равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1

  ---

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Законы склеивания:

• Закон контрапозиции:                                         (A → B) = (¬B → ¬A).
• Формула для исключения импликации:                 A → B = ¬А V B
• Формула для исключения эквиваленции:                
  A ≡ B = A & B V ¬A & ¬B = (¬A V B) & (A V ¬B)
• Формула для исключения сложения по модулю 2:         
  A ⊕ B = ¬A & B V A & ¬B = (A V B) & (¬A V ¬B)

ПОСТРОЕНИЕ ТАБЛИЦ ИСТИННОСТИ

Приоритет логических операций в сложном логическом выражении:

1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквивалентность.

Для изменения указанного порядка выполнения операций используются скобки.

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:
   КОЛИЧЕСТВО СТРОК = 2N + СТРОКА ДЛЯ ЗАГОЛОВКА, где N - количество простых высказываний.
2. Определить количество столбцов:
   КОЛИЧЕСТВО СТОЛБЦОВ = КОЛ-ВО ПЕРЕМЕННЫХ + КОЛ-ВО ЛОГИЧЕСКИХ ОПЕРАЦИЙ;
3. Определить количество переменных (простых выражений);
4. Определить количество логических операций и последовательность их выполнения.
5. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.

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

Приложение 2: Облако понятий по разделу «Основы алгебры логики»

Приложение 3: Задания демо-версии ЕГЭ-2016 по разделу
«Основы алгебры логики»

1. Тема «Составление таблицы истинности логической функции»
(задание №2)

2. Тема  «Поиск информации в Интернете» (задание №17)

3. Тема  «Проверка истинности логического выражения» (задание №18)

4. Тема «Решение систем логических уравнений» (задание №23)

Ответы к заданиям демо-версии ЕГЭ-2016 г. по разделу «Основы алгебры логики»:

Приложение 4: Обучающий тест по теме «Основы алгебры логики»

I. Логические операции

а) Приведите в соответствие названия логических операций и логических связок:

б) Свойства логических операций

Укажите название логической операции, для которой истинно утверждение и соответствующий ей знак:

1) Результат этой логической операции всегда равен нулю, кроме случая, когда все входные переменные истинны.

2) Результат этой логической операции всегда равен нулю, кроме случая, когда все входные переменные ложны.

3) Результат этой логической операции всегда равен единице, кроме случая, когда первый операнд равен единице, а второй равен нулю.

4) Результат этой одноместной логической операции всегда противоположен значению входной переменной.

5) Результат этой логической операции равен единице, если обе входные переменные имеют одинаковые значения.

6) Результат этой логической операции равен единице, если обе входные переменные имеют разные значения.

в) Расположите знаки логических операций через запятую в порядке уменьшения их приоритетаю

II. Таблицы истинности

а) Сколько строк (не считая заголовка) и столбцов будет в таблице истинности для логической функции?

F=(A∧¬B)V(¬A∧B)V¬C

б) Сколько единиц в результирующем столбце этой логической функции F?

в) Заполните таблицу истинности

III. Законы алгебры логики

Заполните таблицу:

IV. При каких значениях логических переменных K,L,M,N верно логическое равенство?

(KVM)→(MV¬LVN)=0

V. Сколько различных решений имеет логическое уравнение?

((J∧¬J)V¬KVL)∧M=1

VI. Системы логических уравнений

Определить количество решений системы логических уравнений и перечислите наборы логических переменных X1..X5:

(X1→X2)=1

(X2→X3)=1

……………

(X4→X5)=1

Ответы к обучающему тесту:

I. Логические операции

а) Логические операции и логические связки

б) Свойства логических операций

1) Конъюнкция (&, ∧, · )

2) Дизъюнкция (V, +)

3) Импликация (→)

4) Инверсия (¬)

5) Эквиваленция (≡, ∼, ↔)

6) Исключающее ИЛИ (⊕)

в) В порядке уменьшения приоритета

¬, ∧, V, ⊕, →, ≡

II. Таблица истинности

а)         8 и 10

б)         6

в)

III. Законы алгебры логики

IV. 1010

V. 6

VI. 6 решений:         00000, 00001, 00011, 00111, 01111, 11111.

Приложение 5: Проверочная работа по теме «Алгебра логики»

1. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Сколько страниц (в тысячах) будет найдено по запросу

Равелин

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

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

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7

2) ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7

3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ x6 ∧ x7

4) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7

3. Дано логическое выражение, зависящее от 7 логических переменных:

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ ¬X5 ∨ ¬X6 ∨ ¬X7

Сколько существует различных наборов значений переменных, при которых выражение ложно?

1)  1         2) 2        3) 127        4) 128

4. Дано логическое выражение, зависящее от 5 логических переменных:

(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)

Сколько существует различных наборов значений переменных, при которых выражение истинно?

1) 0                2) 30                 3) 31                 4) 32

5. Сколько различных решений имеет уравнение

((K ∨ L) → (L ∧ M ∧ N)) = 0

6) Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?

(x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) ∨ (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) = 1

(x3 ∧ ¬x4) ∨ (¬x3 ∧ x4) ∨ (x5 ∧ x6) ∨ (¬x5 ∧ ¬x6) = 1

...

(x7 ∧ ¬x8) ∨ (¬x7 ∧ x8) ∨ (x9 ∧ x10) ∨ (¬x9 ∧ ¬x10) = 1

Ключи к проверочной работе:

Ключи к практической работе (см Приложение 6)

Приложение 6. Практическая работа по решению задач по разделу «Основы алгебры логики»