«Методика изучения темы «Алгебра логики» при подготовке к ЕГЭ»

«Методика изучения темы «Алгебра логики» при подготовке к ЕГЭ»

учитель информатики МБОУ «Луховицкая средняя общеобразовательная школа № 2»

Петухова О. А.

26 февраля 2024 г.

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

Если посмотреть программу по информатике, то видно, что «Основы логики» изучаются в 8 классе (по УМК «Информатика и ИКТ» Босовой Л.Л.). На изучение данной темы отводится 5 уроков в разделе «Математические основы информатики». В 10 – 11 классах изучение этой темы на базовом уровне не предусмотрено ни в УМК Угриновича Н. Д., ни в УМК Семакина И. Г., только в программе Полякова К. Ю. на эту тему отводится 2 часа. Из этого видно, что вся подготовка к сдаче ЕГЭ по этому разделу ложится на консультации и дополнительные занятия.

На дополнительных занятиях теме «Основы логики» я уделяю пять занятий.

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

2. Составление запросов для поисковых систем с использованием логических выражений.

3. Основные понятия математической логики.

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

5. Решение систем логических уравнений.

Цель первого занятия:

1. повторить основные логические операции;

2. повторить принцип построения таблиц истинности для логических выражений;

3. повторить законы алгебры логики;

4. создать условий для систематизации знаний по теме «Основы логики»;

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

Задачи:

1. повторить теоретический материал по теме «Основы логики»

2. выработать умение применять последовательность действий построения таблиц истинности;

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

4. разобрать решение задания № 2.

Теоретический материал по теме «Основы логики»

В самом начале необходимо повторить отличие высказывания от не высказывания (Жирафы летят на север – высказывание; История – интересный предмет – не высказывание)

Следует привести примеры высказываний истинных и ложных.

Например: «Треугольник - это геометрическая фигура» — истинное высказывание.

«Париж — столица Китая» — ложное высказывание.

Научить выделять из сложных высказываний простые.

Например: Число 11 двузначное и простое – сложное высказывание, состоящее из простых – А = Число 11 двузначное, В = Число 11 простое.

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

1. Отрицание. Отрицанием высказывания Х называется высказывание, которое истинное высказывание делает ложным, а ложное – истинным.

Обозначается _{ }. Описывает работу логического элемента «Не».

2. Конъюнкция (логическое умножение). Конъюнкцией высказываний Х₁ и Х₂ называется высказывание F, которое истинно только тогда, когда оба высказывания Х₁ и Х₂ истинны. Обозначается F=Х₁ Х₂ (F=Х₁*Х₂, F=Х₁&Х₂), читается Х₁ и Х₂. Описывает работу логического элемента «И». Таблица истинности:

Обратить внимание учащихся, что логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)

3. Дизъюнкция (логическое сложение). Дизъюнкцией высказываний Х₁ и Х₂ называется высказывание F, которое ложно только тогда, когда оба высказывания Х₁ и Х₂ ложны. Обозначается F=Х₁ Х₂ (F=Х₁+Х₂), читается Х₁ или Х₂. Описывает работу логического элемента «ИЛИ». Таблица истинности:

Обратить внимание учащихся, что логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)

4. Импликация. Импликацией высказываний Х₁ и Х₂ называется высказывание F, которое ложно только тогда, когда условие истинно, а заключение ложно. Обозначается: F= Х₁ → Х₂ (Х₁ – условие, Х₂ – заключение) или F= Х₂ → Х₁ (Х₂ – условие, Х₁ – заключение).

Напомнить учащимся, что именно в этой операции важен порядок следования логических переменных, как в математике в действиях вычитание и деление.

5. Равнозначность (эквивалентность). Эквивалентностью высказываний Х₁ и Х₂ называется высказывание F, которое истинно только тогда, когда оба высказывания одновременно истинны или ложны. Обозначается Х₁↔Х₂.

Х₁↔Х₂=( Х₁ → Х₂)^( Х₂→ Х₁)

Приоритет действия: скобки, отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

После этого можно предложить учащимся выполнить следующие задания:

№ 1. Найти значения логических выражений:

Ответ: 1) 0 2) 0 3) 0 4) 0 5) 1

№ 2. Даны высказывания:

А = {5 3}, B = {2 = 3}, C = {4

Определить истинность составных высказываний

(А&В)&С→(А↔С) (В&С)

Ответ: 1

После этого следует вспомнить понятие таблицы истинности и повторить алгоритм построения таблиц истинности.

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

1. Определить количество строк по формуле 2ⁿ, где n – количество переменных.

2. Определить количество столбцов по формуле количество переменных + количество логических операций.

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

4. Заполнить столбцы входных переменных наборами значении.

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

Далее следует построить несколько таблиц истинности:

1. А^Вv ¬С^А

   А	В	С	¬С	(А^В)	(¬С^А)	(А^В)V (¬С^А)
   0	0	0	1	0	0	0
   0	0	1	0	0	0	0
   0	1	0	1	0	0	0
   0	1	1	0	0	0	0
   1	0	0	1	0	1	1
   1	0	1	0	0	0	0
   1	1	0	1	1	1	1
   1	1	1	0	1	0	1

2. ¬B&(A˅B˅C)

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

Задание № 2 в последнее время усложнилось. Для его решения может понадобиться понятия СДНФ и СКНФ, а значит, на подготовительных занятиях необходимо изучить данный теоретический материал.

1. Для записи логических функций используют конъюнктивную и дизъюнктивную формы. Элементарной конъюнкцией (ЭК) называется конъюнкция (логическое произведение) отдельных переменных с отрицанием или без отрицания.

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

Например:

Э К: Х*У, Х*У, Х*У*Z. ЭД: Х+У, Х+У, Х+У+Z.

Запись упрощают, используя тождества: Х*Х*Х=Х, Х+Х+Х=Х, Х*Х=0, Х+Х=1.

2. Конъюнктивная нормальная форма (КНФ) – это форма, в которой функция представлена в виде конъюнкции (логического умножения) элементарных дизъюнкций. Пример:

Дизъюнктивная нормальная форма (ДНФ) – это форма, в которой функция представлена в виде дизъюнкции (логического сложения) элементарных конъюнкций. Пример:

( Х*У)+(Х*Z)+(Х*У*Z).

Алгоритм приведения к ДНФ и КНФ.

1. если в формуле имеется импликация надо применить

а →в ~ а + в

1. ( а^в) ~ а в

1. а в ~ а ^ в

2. если ДНФ не получилось, то применить 1-й дистрибутивный закон:

(а + в) * с ~ (а * с) + (в * с).

1. если КНФ не получилось, то применить 2-й дистрибутивный закон:

(а * в) + с ~ (а + с)*(в + с).

1. а + а ~ а

2. а * а ~ а

П ример:

– ДНФ.

– КНФ.

3. Для записи логических функцией используют совершенную дизъюнктивную нормальную форму (СДНФ) и совершенную конъюнктивную нормальную форму (СКНФ).

СДНФ (СКНФ) называется ДНФ (КНФ) каждая элементарная конъюнкция (дизъюнкция) которой содержит все переменные данной формулы.

Особенности СДНФ и СКНФ каждая содержит все переменные.

Алгоритм перехода:

1 . от ДНФ к СДНФ: не достающею переменную u добавляем в элементарную конъюнкцию в виде (u + u) и применяем 1-ый дистрибутивный закон.

Пример:

 

2. от КНФ к СКНФ: не достающею переменную u добавляем в элементарную конъюнкцию в виде (u * u) и применяем 2-ый дистрибутивный закон.

Пример:

 СДНФ и СКНФ удобно находить по таблицам истинности.

СДНФ:

1. элементарных конъюнкций столько, сколько наборов значений, на которых функция принимает значение 1.

2. если в наборе переменная принимает значение 1 (0), то она входит в элементарную конъюнкцию без отрицания (с отрицанием).

СКНФ:

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

2. если в наборе переменная принимает значение 0 (1), то она входит в элементарную дизъюнкцию без отрицания (с отрицанием).

Пример:

СДНФ=(а * в * с)+(а * в * с) + (а * в * с)

СКНФ=(а+в+с)*(а+в+с)* (а + в + с)*(а + в + с)*(а + в + с)

Составление таблицы истинности по СДНФ, СКНФ:

1. Привести выражение к СДНФ, заменить в каждой конъюнкции переменную 1, а её отрицание 0, каждому полученному набору сопоставить в таблице истинности 1, а остальным 0.

Пример:

А *(В+С)=А*В+А*С=(А*В*(С+С))+(А*С*(В+В))=

А*В*С+А*В*С+А*С*В+А*С*В =А*В*С+А*В*С + А*В*С

1 1 1 1 1 0 1 0 1

Задания для закрепления.

Привести выражение к СДНФ и составить таблицу истинности.

_ _ _ _ _ _ _ _ _ _ _

А*С+В*С=А*С*(В+В)+В*С*(А+А)=А*С*В+А*С*В+В*С*А+В*С*А= А*В*С+А*С*В+В*С*А

1 1 1 1 1 0 0 1 0

_ _ _ _ _ _ _ _ _

А*В+ А= А*В+А*(В+В)=А*В+А*В+А*В

1 0 0 1 0 0

Ответ:

Способы решения задания ЕГЭ № 2

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

1. X	Y	Z	F
   0	1	0	0
   1	1	0	1
   1	0	1	0

   С имволом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

1) X  ¬Y  Z 2) X  Y  Z 3) X  Y  ¬Z 4) ¬X  Y  ¬Z

Решение:

Можно заметить, что в каждом выражении один вид логических операций: дизъюнкция или конъюнкция. Вспомнить, что логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю и логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице.

Первое выражение не подходит для 3 строки, второе – для 2 строки, четвертое – для 1 строки

Ответ: 3

1. Дан фрагмент таблицы истинности выражения 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

Решение:

Рассуждения аналогичны 1заданию.

Первое выражение не подходит для 1 строки, третье – для 3 строки, четвертое – для 1 строки

Ответ: 2

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

X₁  ¬X₂  X₃  ¬X₄  ¬X₅  ¬X₆  ¬X₇

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

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

Решение:

Вспомнить, что логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю. Следовательно, существует только один набор, для которого логическое выражение будет ложно (0101111).

Ответ: 1

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

Так как всего наборов 128 (формула 2ⁿ, где n – количество переменных), один набор даст 0, то ответ 127.

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

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

1) x1 → (x2  x3  x4  x5  x6  x7)

2) x2 → (x1  x3  x4  x5  x6  x7)

3) x3 → (x1  x2  x4  x5  x6  x7)

4) x4 → (x1  x2  x3  x5  x6  x7)

Решение:

Импликация ложна только в одном случае 1 → 0 = 0.

Так как в первой строке х1=0 и х3=0 , то она не подходит ни для первого, ни для третьего выражений. Так как во второй строке х2=0, то она не подходит для второго выражения. Переменная х4 во всех строках равна 1 и каждая скобка равна 0, т. е. выражение 4 подходит.

Ответ: 4

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

Каким выражением может быть F?

1) x1  ¬x2  ¬x3  ¬x4  x5  x6  ¬x7  ¬x8

2) ¬x1  x2  x3  ¬x4  ¬x5  ¬x6  ¬x7  x8

3) x1  x2  ¬x3  x4  x5  ¬x6  ¬x7  ¬x8

4) ¬x1  ¬x2  ¬x3  ¬x4  ¬x5  ¬x6  ¬x7  ¬x8

Решение:

Второе и третье выражения не удовлетворяет 2 строке, четвертое – первой.

Ответ: 1

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

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x3 не совпадает с F.

Решение:

Полная таблица истинности выражения с 6 переменными содержит 2⁶ = 64 строки. В приведённой части таблицы в двух строках значение x3 совпадает с F, а в двух – не совпадает. В оставшихся 60 строках значения x3 могут не совпадает с F.

Следовательно 60 + 2 = 62

Ответ: 62

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

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение выражения x3  x4 не совпадает с F.

Решение:

Полная таблица истинности выражения с 6 переменными содержит 2⁶ = 64 строки.

В приведённой части таблицы в одной строке значение x3  x4 (в первой) совпадает с F, а в трех – не совпадает. В оставшихся 60 строках значения x3  x4 могут не совпадает с F.

Следовательно 60 + 3 = 63

Ответ: 63

1. Каждое логическое выражение A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A  B?

Решение:

Полная таблица истинности выражения с 5 переменными содержит 2⁵ = 32 строки. По условию задачи в каждой таблице по 4 единицы и по 28 (32 – 4) нуля. Логическое выражение A  B равно нулю тогда и только тогда, когда A = 0 и B = 1. Минимально возможное число единиц будет тогда, когда там будет наибольшее число нулей, то есть в наибольшем количество строк одновременно A = 0 и B = 1. По условию A = 0 в 28 строках и B = 1 в 4 строках. Следовательно, выражение A  B может быть равно нулю не более чем в 4 строках, а единицы в 28 строках.

Ответ: 28

1. Логическая функция F задаётся выражением (a  b)  (a  ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

Решение:

В таблице функция F чаще всего принимает значение 1. Приведем исходное выражение (ДНФ) к виду СДНФ и составим по СДНФ таблицу истинности, затем определим расположение переменных а, в, с по столбцам.

З апишем выражение в более простом обозначении (а∙в)+(а∙с), добавим в каждую скобку недостающую переменную в виде х+х, т. к. х+х=1 и применим закон (а+в)∙с=(а∙с)+(в∙с).

т. к. а + а = а, то можно преобразовать к виду
_{ } - СДНФ

Заменим в каждой конъюнкции переменную 1, а её отрицание 0, каждому полученному набору сопоставить в таблице истинности 1, а остальным 0.

Сопоставим с заданной таблицей.

Вывод: в первом столбце с, во втором – в, в третьем – а.

Ответ: сва

Задания для самостоятельной подготовки

В конце занятия предложить учащимся дома выполнить следующие задания для закрепления данного материала.

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

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

1) (x2  x3  x4  x5  x6  x7)→ x1

2) (x1  x3  x4  x5  x6  x7)→ x2

3) (x1  x2  x4  x5  x6  x7)→ x3

4) (x1  x2  x3  x5  x6  x7)→ x4

Ответ: 3

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

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

1) x1  ¬x2  x3  ¬x4  x5  ¬x6  x7  x8  ¬x9  x10

2) ¬x1  x2  ¬x3  x4  ¬x5  x6  ¬x7  ¬x8  x9  ¬x10

3) x1  ¬x2  x3  ¬x4  x5  ¬x6  x7  x8  ¬x9  x10

4) ¬x1  x2  ¬x3  x4  ¬x5  x6  ¬x7  ¬x8  x9  ¬x10

Ответ: 2

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

Каким выражением может быть F?

1) x1  ¬x2  x3  ¬x4  x5  x6  x7  ¬x8

2) x1  x2  x3  ¬x4  ¬x5  ¬x6  x7  x8

3) ¬x1  x2  ¬x3  x4  x5  ¬x6  x7  ¬x8

4) x1  ¬x2  ¬x3  ¬x4  ¬x5  ¬x6  x7  ¬x8

Ответ: 3

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

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x2  x4 не совпадает с F.

Ответ: 61

1. Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц. Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A  B?

Ответ: 256

1. Логическая функция F задаётся выражением (a  ¬c)  (¬b  ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

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

Ответ: сва

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

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

2. Сайт решу ЕГЭ - https://inf-ege.sdamgia.ru

3. Решение заданий ЕГЭ по информатике с использованием элементов алгебры логики - http://festival.1september.ru/articles/508395/

4. Видео уроки: Простое решение задания №2. Таблицы истинности https://www.youtube.com/watch?v=L3Lfoql5KPs

5. Видео уроки: Задание 2 - https://www.youtube.com/watch?v=ZQ861fGf-Rw

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

1. Информатика. Углублённый уровень: учебник для 10 класса: в 2 ч. Ч. 1/ К. Ю. Поляков, Е. А. Еремин. – М.: БИНОМ. Лаборатьрия знаний, 2013. – 344 с. : ил.

2. Информатика: учебник для 8 класса / Л. Л. Босова, А. Ю. Босова. – 2-е изд., испр. – М . : БИНОМ. Лаборатория знаний, 2014. + 16 с. : ил.

Интернет ресурсы:

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

2. Сайт решу ЕГЭ - https://inf-ege.sdamgia.ru

17