Перед нами задача: создать логическое устройство, которое имеет несколько входов и один выход. На входы подаются сигналы 0 или 1. Такие сигналы могут обозначать, к примеру, значения поданного голоса при голосовании. 0 обозначает «я против», 1 обозначает «я - за». Сигнал на выходе должен показать итоговый результат голосования - да / нет, в зависимости от поданных голосов. Интересно было бы рассмотреть полный процесс создания такого логического устройства. Но прямо сейчас, на этом уроке, мы можем изучить теоретические расчёты, которые предваряют техническое изготовление логического устройства.
Цель урока: познакомить учащихся с задачами инженерного характера: как построить оптимальное логическое устройство по словесному описанию его работы.
Задачи
Обучающие:
- научить формализовать условия содержательной текстовой задачи и представлять их в виде таблицы истинности;
- получить СДНФ и СКНФ по полученной таблице истинности (совершенная дизъюнктивная нормальная форма - СДНФ и совершенная конъюнктивная нормальная форма - СКНФ);
- упростить СДНФ (или СКНФ) с целью обеспечения оптимальности функциональных схем, их реализующих;
- построить функциональную схему в соответствии с реализуемой структурной формулой;
- проверить соответствие логической схемы реализуемой структурной формуле.
Развивающая
- Учить видеть структуру там, где она есть, и быть готовым работать со структурой адекватными методами.
Воспитательная
- Поднять ценность теории алгебры логики ибо она применима на практике.
Тип урока: урок получения новых знаний, приближенных к инженерной теории.
Вид урока: урок закрепления изучаемого материала.
Планируемые результаты
- Мы узнаем: алгоритм построения функциональной схемы по таблице истинности.
- Мы научимся: формализовать текстовое содержание задачи ради построения таблицы истинности.
- Мы сможем: построить оптимальную функциональную схему на основе упрощенной структурной формулы.
Оборудование и средства обучения: доска, мел, конспекты лекций, у каждого ученика и учителя есть методическое пособие Лыскова В.Ю. Логика в информатике / В.Ю.Лыскова, Е.А.Ракитина. - 2-е изд. - М.: Лаборатория Базовых Знаний, 2006, распечатки бланков централизованного тестирования по информатике 2006 года для каждого ученика и учителя.
План урока
1 этап. Организационный этап.
2 этап. Объявление темы и актуализация знаний.
3 этап. Формирование новых знаний: образцы решения задач и обсуждение.
4 этап. Домашнее задание.
Ход урока
1 этап. Организационный этап
Здравствуйте. Присаживайтесь. Отметим отсутствующих и приступим к уроку.
2 этап. Объявление темы и актуализация знаний
Сегодняшнее число. Тема урока «Оптимальное логическое устройство: его функциональная схема и структурная формула».
Что такое функциональная схема и что такое структурная формула - эти понятия не вызывают затруднений, надеюсь. Давайте их проговорим. Кто желает?
(Ответ должен быть проговорен вслух.
Ответ:
Схема соединения логических элементов называется функциональной схемой.
Структурная формула - это форма описания функции, реализуемой логическим устройством.
Логическое устройство - цепочка из логических элементов, в которой выходы одних элементов являются входами других.)
Теперь, что такое оптимальность? Давайте подумаем. Ваш вариант ответа?
(Ответ:
«Оптимальность - это достижение наилучшего результата в данных условиях при минимальных затратах времени и усилий участников», - гласит Словарь терминов по общей и социальной педагогике.)
Сегодня нам понадобятся знания логических элементов, алгоритм составления СДНФ и СКНФ, а также ваши хорошие навыки упрощения логических выражений.
Проведем короткую проверочную работу в качестве «разминки».
(Учитель раздает карточки проверочной работы - учащиеся письменно отвечают на вопросы. Двоих вызывает к доске - выполнять проверочную работу. Остальные пишут на местах.)
Вопросы проверочной работы:
- Нарисуйте логические элементы и подпишите их названия.
- Дана таблица истинности для двух переменных.
|
X |
Y |
F(X, Y) |
|
0 |
0 |
0 |
|
0 |
1 |
1* |
|
1 |
0 |
1* |
|
1 |
1 |
0 |
По этой таблице составить СДНФ и СКНФ.
Результаты на доске учитель проверяет сразу. И сообщает оценки сразу.
(Правильные ответы:
1. Логические значения 0 и 1 - это цифровые сигналы. Они поступают, преобразовываются и выходят из так называемых логических элементов. Логические элементы выполняют дизъюнкцию, конъюнкцию, инверсию; логические устройства выполняют: сложение по модулю 2, эквивалентность, импликацию, коимпликацию, элемент Вебба (или-не), элемент Шеффера (и-не). Смотри Рисунок 1.
Рисунок 1
2. Обратимся к Методическому пособию Лысковой В.Ю., где описаны алгоритмы получения СДНФ и СКНФ. Привожу фрагмент пособия, чтобы материал урока был целостным. «Существует алгоритм, позволяющий по известной таблице истинности построить схему устройства. В основе алгоритма лежит теорема алгебры логики: любую функцию, кроме констант 0 и 1, можно представить в виде СДНФ, так и СКНФ. Совершенная дизъюнктивная нормальная форма - СДНФ и совершенная конъюнктивная нормальная форма - СКНФ.
Алгоритм получения СДНФ по таблице истинности.
1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1:
|
X |
Y |
F(X, Y) |
|
0 |
0 |
0 |
|
0 |
1 |
1* |
|
1 |
0 |
1* |
|
1 |
1 |
0 |
2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, о ее отрицание:
3. Все полученные конъюнкции связать в дизъюнкцию:
3 этап. Формирование новых знаний: образцы решения задач и обсуждение результатов
Задача 1 «Устройство для голосования». (Из Методического пособия Лысковой В.Ю., стр. 97. Задачу перепечатываю.)
«Пусть в некотором конкурсе решается вопрос о допуске того или иного участника к следующему туру тремя членами жюри: P, Q, R. Решение положительно тогда и только тогда, когда хотя бы двое членов жюри высказываются за допуск, причем среди них обязательно должен быть председатель жюри Q. Необходимо разработать устройство для голосования, в котором каждый член жюри нажимает на одну из кнопок - «За» или «Против», а результат голосования всех трех членов жюри определяется по тому, загорится (решение принято) или нет (решение не принято) сигнальная лампочка.
Формально это можно выразить так: требуется составить функциональную схему устройства, которое на выходе выдавало бы 1, если участник допускается к следующему туру, и 0, если не допускается.»
Решение
1. Нужно рассмотреть всевозможные комбинации голосов жюри. Если голос «против», то будем обозначать его нулем. Если голос «за», то обозначим его единицей. Жюри состоит из трех человек. Значит, надо составить все трехбитные двоичные коды. Их будет 8.
Затем напротив каждого кода записать вывод - допускается или нет участник к следующему туру. Работу жюри представим в виде таблицы истинности:
|
P |
Q |
R |
F(P, Q, R) |
Решение |
|
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
допускается |
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
1 |
допускается |
|
1 |
1 |
1 |
1 |
допускается |
2. Если мы хотим построить формулу некоторой функции по таблице истинности, то необходимо получить СДНФ или СКНФ по таблице истинности. Для этого берем таблицу истинности нашей задачи
|
P |
Q |
R |
F(P, Q, R) |
Решение |
|
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
* |
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
1 |
* |
|
1 |
1 |
1 |
1 |
* |
и отмечаем звездочкой в столбце Решение три строки, в которых F(P, Q, R) = 1. Записываем для этих строк конъюнкции всех переменных и объединяем конъюнкции в СДНФ. Смотри Рисунок 2.
Рисунок 2
Мы провели упрощение СДНФ. Вместо первоначальных десяти логических операций осталось две.
3. Для самоконтроля проведем работу по формированию и преобразованию СКНФ. Запишем для строк таблицы, которые оканчиваются нулями, дизъюнкции переменных и свяжем полученные дизъюнкции в конъюнкцию. Получим СКНФ. Смотри Рисунок 3.
Рисунок 3
Мы провели упрощение СКНФ. Видим, что полученные СДНФ и СКНФ эквивалентны.
4. Теперь нарисуем функциональную схему устройства по структурной формуле: 
. Смотри Рисунок 4.
Рисунок 4
В полученной схеме задействовано всего 2 логических элемента: дизъюнктор и конъюнктор.
5. Докажем, что функциональная схема соответствует СДНФ. Для этого построим таблицы истинности и для функциональной схемы и для структурной формулы и сравним их. Смотри Рисунок 5.
Рисунок 5
|
P |
Q |
R |
Выход (1) |
Выход (2) |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
|
P |
Q |
R |
P v R |
Q&(P v R) |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
Последние столбцы обеих таблиц совпадают. Это значит, что построенная функциональная схема соответствует структурной формуле, то есть соответствует СДНФ.
Решение завершено.
Давайте выработаем полезный алгоритм построения оптимальной функциональной схемы по таблице истинности. Так и назовем его - Полезный алгоритм.
Полезный алгоритм
1. Строим саму таблицу истинности по условиям задачи.
2. По таблице истинности строим СДНФ или СКНФ в зависимости от того, каких строк меньше в последнем столбце таблицы. Если меньше 1, значит, строим СДНФ. Если меньше 0, то строим СКНФ.
3. Этап необязательный. Можно построить обе совершенные формы и убедиться, что они эквивалентны.
4. Провести упрощение СДНФ и/или СКНФ.
5. Нарисовать функциональную схему, соответствующую полученной логической формуле.
Задача 2 «Будь эффективным!» (Задача А5 из бланков централизованного тестирования 2006 года по информатике.) Давайте закрепим свои знания и умения в вопросе «прочтения» функциональных логических схем.
Есть схема устройства. Смотри Рисунок 6.
Рисунок 6
Какую логическую функцию реализует функция F?
1) 1
2) А
3) В
4) 0
Решение
Будем определять структурную формулу по заданной функциональной схеме. Посмотрим на финальный логический элемент схемы - это конъюнктор. У него два входа. Распишем по отдельности формулы для первого и второго входа, затем логически перемножим их.
На первом входе конъюнктора. Смотри Рисунок 7.
Рисунок 7
На втором входе конъюнктора. Смотри Рисунок 8.
Рисунок 8
Теперь выполним финальную конъюнкцию. Смотри Рисунок 9.
Рисунок 9
Мы получили, что в предложенной схеме сигнал на выходе будет совпадать с сигналом А на входе.
Ответ: 2.
Прошу обратить особое внимание на изображение функциональной схемы.
Во-первых, увидьте особую эстетику изображения функциональной схемы: линии - параллельные и перпендикулярные, образуют строгий рисунок схемы.
Во-вторых, удобство восприятия схемы обеспечивается симметричным расположением логических элементов.
В-третьих, логические элементы подписаны.
И четвертое, схема «растет» и «читается» слева направо: в крайней левой позиции есть входы, в крайней правой позиции - выход F функциональной схемы.
Эти четыре замечания назовем Правилами изображения функциональных схем, и к следующему уроку выучим эти Правила назубок.
Перейдем к домашнему заданию.
4 этап. Домашнее задание
1. Выучить наизусть Полезный алгоритм и Правила изображения функциональных схем.
2. Из методического пособия Лысковой задача 2 на стр. 112 - аналог классной задачи «Устройство для голосования».
3. Из распечаток ЦТ 2006 задача А5 - аналог классной задачи «Будь эффективным!»
Если ко мне вопросов нет, то всем спасибо и до следующей встречи.