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

Разделы: Информатика


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

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

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

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

Содержание этапов урока

Виды и формы работы

I. Организационный момент. Приветствие.
II. Мотивационное начало урока. Постановка проблемы.
III. Объяснение нового материала. Использование подготовленной презентации. Решение проблемы
IV. Этап общения, систематизации знаний и закрепление изученного. Решение задач по карточкам.
V. Подведение итогов, домашнее задание. Выставление оценок. Домашнее задание.

ХОД УРОКА

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

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

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

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

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

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

Функциональная  схема:

 

Таблица  истинности:
X Y
1 1 0 0 0
1 0 0 1 1
0 1 1 0 1
0 0 1 1 1

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

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

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

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

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

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

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

X Y F
0 0 1
0 1 0
1 0 1
1 1 1

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

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

Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.  (Слайд 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. Упрощаем формулу, применяем законы логики (если это необходимо).

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

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

X

Y

0 0 1 1
0 1 0 0
1 0 1 1
1 1 0 1

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

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

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

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

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