Конспект урока в 10-м классе по информатике "Совершенная дизъюктивная нормальная форма и совершенная конъюктивная нормальная форма"

Цели и задачи урока:

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

Оборудование: Презентация, слайды, которые демонстрируются на экран с помощью проектора (Приложение 1).

План урока для учителя

ХОД УРОКА

I. Организационный момент. Приветствие учащихся

II. Мотивационное начало урока

Вспомним что такое логическая функция.
Логической функцией  n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Мы будем представлять логические функции одновременно в нескольких равноценных формах:

• логическая формула: алгебраическая (аналитическая) форма;
• таблица истинности: таблица состояний функции, в которой непосредственно указываются её значения для всех возможных комбинаций значений логических переменных;
• логическая схема: состоит из "логических элементов", условно изображающих те или иные логические функции.

Задание: построить по формуле  функциональную схему и  таблицу истинности. Дана формула :

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

III. Объяснение нового материала

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

Нам необходимо несколько дополнить понятия конъюнкции и дизъюнкции и ввести понятия ДНФ и КНФ.

• Простой конъюнкцией (элементарной) называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание).  Например, . (Слайд 2).
• Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, . (Слайд 3).
• Простой дизъюнкцией (элементарной) называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Например, . (Слайд 4).
• Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций.  Например, . (Слайд 5).

Мы знаем, как составлять таблицу истинности для логической функции. Попробуем решить обратную задачу. Так мы решим возникшую проблему – как от таблицы истинности перейти к логическому выражению – формуле, а на ее основе построить функциональную схему.  

Пусть дана таблица истинности для некоторой логической функции F(X,Y):

Здесь нам помогут СКНФ и СДНФ. Что это такое? (Учитель сообщает тему урока).

“Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма”.

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

Перечислим свойства совершенства для СДНФ:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.
2. Все логические слагаемые различны.
3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание.
4. Ни одно слагаемое не содержит одну и ту же переменную дважды.

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

Перечислим свойства совершенства для СКНФ:

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

Решение задачи. (Слайды 11, 12)

Алгоритм получения СДНФ по таблице истинности:

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1:

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно  0, то ее отрицание: для 1-й строки   , для 3-й строки , для 4-й строки .

3. Все полученные конъюнкции связать в дизъюнкцию:

4. Упрощаем формулу, применяем законы логики.

Алгоритм получения СКНФ по таблице истинности

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 0:

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

3. Все полученные дизъюнкции связать в конъюнкцию:

4. Упрощаем формулу, применяем законы логики (если это необходимо).

Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. СДНФ     и  СКНФ

Можем проверить, построив таблицу истинности по найденной формуле.

Теперь построим логическую схему:

IV. Этап общения, систематизации знаний и закрепление изученного

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

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

V. Подведение итогов, домашнее задание