МЕТОДИЧЕСКАЯ РАЗРАБОТКА Урока «Совершенные Нормальные Формы. Общее понятие и назначение. Правила построения СДНФ (СКНФ) по таблице истинности» по дисциплине: «Архитектура ЭВМ и ВС»

Министерство образования Тверской области

ГБПОУ «Ржевский колледж»

машиностроительный техникум»

МЕТОДИЧЕСКАЯ РАЗРАБОТКА

Урока «Совершенные Нормальные Формы.

Общее понятие и назначение. Правила построения СДНФ (СКНФ) по таблице истинности»

Дисциплина: «Архитектура ЭВМ и ВС»

Преподаватель: Петрова Алла Николаевна

Ржев-2010/2011 уч. год

Одобрена

Предметной (цикловой)

комиссией специальных дисциплин

Председатель:

Преподаватель РМТ

Степанова Л. Е.

Составитель:

Преподаватель РМТ: Петрова А. Н.

Рецензенты:

Преподаватели РМТ

Степанова Л. Е., Лякина И. И.

МЕТОДИЧЕСКАЯ РАЗРАБОТКА

Урока по дисциплине «Архитектура ЭВМ и ВС»

«Совершенные Нормальные Формы. Общее понятие и назначение. Правила построения СДНФ (СКНФ) по таблице истинности»

Тема урока:

О, сколько нам открытий чудных

Готовят просвещенья дух

И опыт, сын ошибок трудных,

И гений, парадоксов друг,

И случай, бог - изобретатель

А.С.Пушкин

Тип урока: урок обобщения, систематизации знаний для изучения нового материала

Цель урока: Обобщение, систематизация знаний по темам логических основ ЭВМ, в частности, по теме: «Логические элементы ЭВМ. Построение таблиц истинности для вентилей, логических выражений и функциональных схем ЭВМ». Изучение материала для работы с Совершенными Нормальными Формами, исследование возможности:

• получения новой логической функции, эквивалентной исходной;

• замены с помощью СДНФ (СКНФ) одних логических элементов другими, равнозначными по результату.

Задачи урока:

• Продолжить формирование знаний логических основ ЭВМ, необходимых, в дальнейшем, для освоения материала по функциональным схемам таких устройств ЭВМ как: полусумматор, сумматор, шифратор, дешифратор и других, не менее важных устройств ЭВМ;

• Обеспечить закрепление изученного материала;

• Продолжить работу по овладению методами исследования доказательной базы булевой алгебры;

• Продемонстрировать возможности применения информационных технологий на уроках архитектуры ЭВМ;

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

Наглядные пособия и оснащение урока:

• Презентация (Тема урока, схема урока, задачи-загадки с целью мониторинга усвояемости текущего и предыдущих уроков по дисциплине;

• мультимедийные компьютерные средства(ноутбук, проектор, интерактивная доска)

План урока

1. Организационный этап (2 мин).

2. Актуализация знаний

3. Решение задач (20 мин).

4. Изложение нового материала (15 мин).

5. Закрепление материала (21 мин).

6. Тестирование (18 мин).

7. Итоги урока (3 мин).

8. Домашнее задание (3 мин).

Ход урока:

1. Организационный этап

   Деятельность преподавателя

   Деятельность

   студентов

   1. Приветствие, вступительное слово;

   2. Проверка отсутствующих по классному журналу

   Преподаватель дисциплины:

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

   Слушают.

   
   

2. Актуализация знаний

Деятельность преподавателя

Деятельность

студентов

Экспресс-опрос:

1. Что такое простое логическое высказывание и какие предложения не могут быть логическими высказываниями? (Слайд № 5)

2. Что такое составное логическое высказывание? (Слайд № 6)

2. Что такое логическая переменная? (Слайд № 7)

2. Назовите основные логические операции (связки) и правила к ним; (Слайд № 8)

2. X=27₁₀ Y=35₁₀ Найти С₁₀=XY

(Слайд № 9)

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

   К = 2ⁿ,

   где n - количество входных переменных

   
   Что такое таблица истинности и от чего зависит количество оценок входных переменных? (Слайд № 10)

2. УГО каких вентилей изображено на рисунке? (Слайд № 11)

2. Что такое функциональная схема? (Слайд № 12)

Слушают.

Отвечают на вопросы, оформленные слайдами презентации:

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

В

Это именованное логическое высказываниеысказывание, состоящее из нескольких простых высказываний, соединенных знаками логических операций (связками), называется составным логическим высказыванием

Функциональной схемой называется электронная схема, состоящая из элементарных (базисных) логических элементов.

Функциональная схема - это аппаратная реализация логической функции на вентилях.

3. Решение задач

   Материал, необходимый для дальнейшей работы, повторили, вспомнили как выглядят логические элементы согласно ГОСТа, а сейчас вам будут предложены задачи, в которых также используются знакомые вам логические элементы, но их УГО выглядят несколько иначе, так как реализованы они с помощью компьютерной технологии электронных таблиц Ms Excel. Итак,

   задача 1 "Торшер" (Слайд № 12)

   Купили как-то на распродаже торшер с двумя переключателями - ВКЛ/ВЫКЛ. Принесли домой, включили… Странное дело - торшер не включается, лампочка не горит!... Посмотрели, лампочка - нормальная, не сгоревшая. Нажали кнопку ВЫКЛ, торшер включился…

   Напутали что-то изготовители в переключателях, но что?

   Внимательно ознакомьтесь с условием задачи на слайде презентации.

   
   

   задача 2 "Игрушка" (Слайд № 13)

   Маленькой Анечке подарили игрушку - мудрую-премудрую сову с книжкой. На корешке книги располагались четыре разноцветные кнопочки, при нажатии на которые вырабатывались сигналы, поступающие на беспроводное устройство, связанное с непонятным логическим элементом, подсоединенным к глазам мудрой совы. Проанализируйте сигналы кнопок, реакцию глаз совы и определите "хитрый" элемент.

   Решение второй задачи потребует от вас особенной собранности и внимания. При активизации задачи в Excel вам необходимо записать значения сигналов в качестве оценок таблицы истинности логической функции F(А, В). Сама функция принимает значение 1(истина), если глаза игрушки-совы открыты и значение 0(ложь), если глаза игрушки-совы закрыты

   
   

   В третьей задаче требуется определить уже не один логический элемент, а структуру функциональной схемы, состоящей из двух логических элементов:

   задача 3 "Баба-яга" (Слайд № 14)

   Однажды баба-яга услышала по телевизору, что диаметр луны ежегодно уменьшается на 4 см. Забеспокоилась баба-яга и решила экономить лунный свет. Пригласила змея Горыныча и попросила его сделать такую схему, чтобы она могла включать, выключать лунный свет и изменять его яркость по своему усмотрению. Принялся Горыныч за дело, но не смог выполнить просьбу бабы-яги, да и сам не понял что за схему он смастерил:

   - нажмешь кнопку А - луна включается;

   - нажмешь кнопку В - луна выключается;

   - нажмешь кнопку С - луна опять включается!

   Такая задача трудная! А все потому, что не знал Горыныч ничего о вентилях. Так, что же это за схема???

   Указание к решению: луна "включается"при значении

   F(A,B,C)=1, луна "выключается" при значении

   F(A,B,C)=0

   Слушают.

   Анализируют просмотр активизируемой в Excel задачи, решают, отвечают.

   Выходы переключателей подсоединены к инвертору.

   
   

   Анализируют просмотр активизируемой в Excel задачи, разрабатывают таблицу истинности, определяют название логического элемента и сообщают ответ

   А

   В

   F

   0

   0

   0

   0

   1

   1

   1

   0

   1

   1

   1

   0

   
   

   Согласно таблице итинности, искомый "хитрый" элемент - это вентиль Исключающее ИЛИ

   
   

   Анализируют просмотр активизируемой в Excel задачи.

   (Если ответ затягивается, можно дать подсказку: построить таблицу истинности для логической функции 3-х параметров F(A,B,C) =ABC, т. е. получить следующую таблицу истинности

   А

   В

   С

   F

   0

   0

   0

   0

   0

   0

   1

   1

   0

   1

   0

   1

   0

   1

   1

   Тогда правильным

   ответом следует услышать:0

   1

   0

   0

   1

   1

   0

   1

   0

   1

   1

   0

   0

   1

   1

   1

   1

   Функциональная схема состоит из двух вентилей Исключающего ИЛИ

4. Изложение нового материала

   Деятельность преподавателя

   Деятельность

   студентов

   Итак, мы повторили весь материал, необходимый для понимания новой темы - ключевой темы, очень важной в тематике функциональных схем. Для начала задам вот такой вопрос, вопрос-тест: (Слайд № 16) ²

   Вопрос-тест

   Каким образом можно доказать равнозначность двух разных логических функций (высказываний)?:
   a) Подставить цифровые значения в каждую из функций;
   b) Попросить помощи в Интернете;
   c) Просчитать таблицы истинности для каждой из сравниваемых функций;
   d) Погадать на ромашке

   Ответ - с, и это правильный ответ! Поэтому, если я сейчас буду утверждать, что импликацию логических переменных А, В можно записать в виде логической функции +В, т.е. AB=+В и докажу это сравнением двух таблиц истинности для левой и правой частей равенства, вы, безусловно поверите и правильно сделаете! (показать Слайд № 17) ²

   Но откуда и как появилась правая часть равенства, которая, и это очевидно, эквивалентна левой части равенства?

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

   Проблема заключается в том, что одна и та же логическая функция может быть записана различным образом. Например, функция F(x₁,x₂) может быть записана следующими эквивалентными выражениями:

   F(X₁,X₂) = + +

   F(X₁,X₂) = +

   F(X₁,X₂) = Х1(+)

   Эквивалентность выражений легко проверить подстановкой в них соответствующих логических значений входных переменных Х1 и Х2. (показать Слайд № 18) 

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

   Таким образом, можно закончить решение первой задачи выводом: (показать Слайд № 19) ²

   • ВЫВОД 1: Для получения новой логической функции, эквивалентной исходной применяются две совершенные нормальные формы:

     1. Совершенная Дизъюнктивная Нормальная Форма (СДНФ);

     2. Совершенная Конъюнктивная Нормальная Форма (СКНФ)

   Задача вторая: Овладеть знанием правил записи СДНФ и СКНФ по таблицам истинности

   Правила достаточно простые: (показать Слайд № 20) ²

   1. ПРАВИЛО ЗАПИСИ СДНФ логической функции ПО ТАБЛИЦЕ ИСТИННОСТИ:

   Для всех наборов переменных, на которых функция принимает единичные значения (F=1), записать конъюнкции, инвертируя те переменные, которым соответствуют нулевые значения. Затем конъюнкции соединить знаками дизъюнкции.

   Например, F(X1,X2,X3)=1 на наборах 001,010. СДНФ функции: не(Х1)не(Х2)Х3 + не(Х1) Х2не(Х3)

   
   

   2. ПРАВИЛО ЗАПИСИ СКНФ логической функции ПО ТАБЛИЦЕ ИСТИННОСТИ:

   
   Для всех наборов переменных, на которых функция принимает нулевые значения (F=0), записать дизъюнкции, инвертируя те переменные, которым соответствуют единичные значения. Затем дизъюнкции соединить знаками конъюнкции.

   Например, F(X1,X2,X3)=0 на наборах 001,010. СКНФ функции: (Х1+Х2+не(Х3))( Х1+не(Х2)+Х3)

   Задача третья: научиться применять полученные знания о совершенных нормальных формах

   Вернемся к исходной логической функции F_(А,В)=AB и на ее примере реализуем одно из правил:

   (показать Слайд № 21) ²

   A

   F=AàB

   В результирующем столбце с заголовком F=AB на наборе 10 логическая функция принимает нулевое значение. Существует негласное правило согласно которому следует выбирать:Дизъюнк-
   ция

   0

   0

   1

   0

   1

   1

   1

   0

   0

   +В

   1

   1

   1

   а) СДНФ, если количество значений F=1 меньше количества значений F=0;

   b) СКНФ, если количество значений F=0 меньше количества значений F=1

   А ВПоэтому для логической функции F=AB находим СКНФ. Для этого в последний столбец записываем дизъюнкцию для набора 10 : +В

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

   Поскольку электронная схема является аппаратной реализацией простой или сложной логической функции, то знание правил записи СДНФ или СКНФ логической функции по таблице истинности позволяет избежать ошибки при необходимости реализации требуемой функциональной схемы на логических элементах, отличных от первоначально планируемых. На том же примере импликатора можно построить взаиморавнозначную функциональную схему, состоящую из инвертора и вентиля ИЛИ: (показать Слайд № 22) ²

   
   

   +B
   

   
   

   В
   

   Равнозначность логических функций F=AàB и +В доказана на таблицах истинности. Мониторинг равнозначности аппаратной реализации этих функций

   (функциональных схем) можно доказать с помощью Excel-графики:

   Задача пятая: исследование эффективности применения совершенных нормальных форм

   Упрощение СДНФ или СКНФ логической функции позволяет получить кратчайшую форму записи логической функции, что позволяет снизить аппаратные и стоимостные параметры электронных схем. Примем это как аксиому, т.к. это отдельный, достаточно сложный, материал для рассмотрения.

   На одном из практических занятиях будет рассмотрен вопрос упрощения логической функции, заданной некоторой комбинационной схемой, используя СДНФ (СКНФ). Инструмент процессора электронных таблиц позволяет достаточно просто реализовать расчет сложных функциональных схем, например: (показать Слайд № 23) ²

   
   

   Из всего вышеизложенного материала по теме можно сделать следующие выводы:

   1. СДНФ (СКНФ) - ключевые понятия для конструирования функциональных схем электронных устройств;

   2. Знание правил записи СДНФ (СКНФ) по таблице истинности позволяет:

      1. моделировать логические функции, исключающие неоднозначность их толкования;

      2. конструировать комбинационные схемы, реализующие необходимую логику их функционирования;

   3. Применение СДНФ или СКНФ логической функции позволяет снизить аппаратные и стоимостные параметры электронных схем (показать Слайд № 24) ²

   Слушают.

   Анализируют вопрос-тест

   c) Просчитать таблицы истинности для каждой из сравниваемых функций

   
   

   
   

   
   

   Слушают, записывают содержание поставленной перед ними первой задачи

   
   

   
   

   
   

   
   

   
   

   Слушают, записывают содержание вывода по поставленной перед ними первой задачи

   
   

   
   

   Слушают, записывают правила

   
   

   
   

   
   

   
   

   
   

   Анализируют интерактивную демонстрацию слайда

   
   

   
   

   
   

   
   

   Анализируют интерактивную демонстрацию слайда

   
   

   
   

   Анализируют интерактивную демонстрацию слайда

   
   

   
   

   
   

   
   

   
   

   
   

   Анализируют интерактивную демонстрацию слайда

   
   

   
   

   
   

   
   

   
   

5. Закрепление материала

3. Подведение итогов:

а) краткий анализ урока;

б) выставление оценок

3. Домашнее задание

Дано: три входных логических переменных - C_i , X_{i ,} Y_i , где X_{i ,} Y_i - соответствующие разряды двух чисел (числа X и числа Y), C_i - входной перенос.

Требуется: построить таблицу истинности по трем входным логическим переменным и двум выходным логическим функциям: C_i+1, S_i , используя алгоритм одного шага легенды поразрядного сложения (одного разряда):

15