"Операция двоичного сложения. Полином Жегалкина."
Методическая разработка
Автор: Сафонова Ольга Александровна, преподаватель, Железнодорожный техникум Нижегородского филиала МИИТ, город Нижний Новгород
В раздел среднее профессиональное образование
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ
СООБЩЕНИЯ» (МГУПС (МИИТ))
НИЖЕГОРОДСКИЙ ФИЛИАЛ МИИТ
МЕТОДИЧЕСКАЯ РАЗРАБОТКА
ОТКРЫТОГО УРОКА
по теме: Операция двоичного сложения. Полином Жегалкина
по дисциплине
:
Прикладная математика для специальности: 27.02.03 «Автоматика и телемеханика на транспорте (на железнодорожном транспорте)» Работу составила: преподаватель высшей квалификационной категории Сафонова О.А. Нижний Новгород 2016 г.
ОДОБРЕНО Цикловой комиссией Общеобразовательных дисциплин _____________________________________ Протокол № От «____»____________2016 г. Председатель комиссии ________________Захарова Н.А. Составлено в соответствии с Государственными требованиями к минимуму содержания и уровню подготовки выпускника по дисциплине «Прикладная математика» специальности 27.02.03 «Автоматика и телемеханика на транспорте (на железнодорожном транспорте)» Методическая разработка . Нижегородский Филиал МИИТ Н.Новгород, 2016 г. - 13 стр. Составитель: преподаватель Сафонова О.А.
Цели урока:
познакомить студентов с операцией двоичного сложения; научить представлять булеву функцию в виде многочлена Жегалкина; воспитывать настойчивость в приобретении знаний и умений; выявить межпредметные связи; сформировать интерес к будущей профессиональной деятельности.
Оборудование
: доска, мел, раздаточный материал (таблицы элементарных булевых функций, карточки с заданиями), проектор.
Ход урока.
1.
Организационный момент.
Цель:
проверить посещаемость.
2.
Проверка домашнего задания.
Цель:
проверить наличие домашней работы; разобрать упражнения, вызвавшие трудности при самостоятельном выполнении.
3.
Выполнение заданий по теме: «Разложение булевых функций по
п переменным. СДНФ. СКНФ.» с целью закрепления.
Цель:
закрепить знания и навыки, приобретенные на предыдущем уроке; оценить работу студентов, отвечающих у доски. Один студент записывает общий вид СДНФ и СКНФ, дает определения приведенных разложений. Два студента выполняют задания 1),2) на крыльях доски. Сравнивая полученные результаты, оценивают свою работу. Для функции ( ) ( ) f x y z xy z = Ъ Ъ Ъ 1) построить СДНФ и СКНФ с помощью таблицы истинности; 2) построить СДНФ и СКНФ с помощью законов алгебры логики. Ответ: ( ) ( ) ( ) ( ) ÑÄÍ Ôf xy z xyz x yz x yz ÑÊÍ Ôf x y z x y z x y z x y z = Ъ Ъ Ъ = Ъ Ъ Ъ Ъ Ъ Ъ Ъ Ъ Один студент выполняет задание на центральной доске: Построить из заданной ДНФ её СДНФ для функции f x y y z xz = Ъ Ъ ; построить из заданной КНФ её СКНФ для функции ( )( ) f x y y z z = Ъ Ъ . Для студентов, выполнивших задания раньше остальных, можно предложить следующее упражнение: Построить СКНФ для функции ( ) ( | ) f x y x yz = ® Е из её СДНФ.
4.
Актуализация, постановка задачи.
Цель:
установить межпредметные связи; дать установку на инициативную деятельность. Вступительное слово преподавателя: Одно из основных приложений булевых функций лежит в области создания схем функциональных элементов или функциональных схем, которые можно реализовать в виде электронных устройств с конечным числом входов и выходов, причем на каждом входе и выходе может появляться только два значения. Такие устройства собраны из функциональных элементов, генерирующих основные булевы операции. Подробно данный материал вы будете изучать в дисциплине «Электронная техника», а общие сведения об элементной базе импульсных и цифровых устройств расскажет и покажет студент. Выступление студента. До 60-х годов элементную базу электронных устройств составляли дискретные отдельные компоненты: усилительные элементы, резисторы, конденсаторы и т.д. До 50-х годов усилительным элементом являлась электронная лампа, вытесненная затем транзистором. Стремление уменьшить массу и габариты аппаратуры привело к созданию интегральных микросхем, составляющих элементную базу современной электронной аппаратуры. Микросхемы разделяются на аналоговые и цифровые. Импульсные устройства выполняются на аналоговых микросхемах, предназначенных для работы с сигналами, которые могут принимать непрерывный ряд значений. Аналоговые микросхемы разделяются на специализированные и универсальные. На специализированной микросхеме может быть собран узел или устройство только определенного типа. Универсальные микросхемы используют для построения различных узлов и устройств. Импульсные устройства отличаются друг от друга выполняемыми функциями. Кроме того, импульсы, действующие в каждом типе таких устройств, могут иметь самые разные различные значения параметров. Поэтому даже специализированные микросхемы предусматривают подключение внешних («навесных») элементов – резисторов, конденсаторов, которыми определяются параметры выходных импульсных последовательностей. Навесные элементы, присоединяемые к универсальным микросхемам, определяют также и характер выполняемых устройством функций. Цифровые устройства выполняются на цифровых микросхемах, которыми реализуются логические функции. Любую такую функцию можно выразить с помощью элементарных логических функций - конъюнкции, дизъюнкции и инверсии логических переменных. Отсюда следует, что из элементов И, ИЛИ, НЕ можно составить цифровое устройство любой сложности. В этом смысле элементы И, ИЛИ, НЕ образуют универсальную
совокупность. Стандартные обозначения основных функциональных элементов показаны на рис.1. РИС.1 Соединяя функциональные элементы вместе, мы получаем функциональную схему. С её помощью можно реализовать любую булеву функцию. Например, что получится на выходе функциональной схемы, представленной на рис.2. РИС.2 На выходе получится функция f xyz x yz xy z = Ъ Ъ .
На ряду с элементами И, ИЛИ, НЕ малой степени интеграции промышленностью выпускаются цифровые микросхемы средней, большой и сверхбольшой степени интеграции. Ограниченное число элементарных логических функций, а также то, что компоненты цифровых сигналов имеют только два значения, позволяет выполнять цифровые устройства только на микросхемах, без использования навесных элементов.
5.
Объяснение нового материала.
Цель:
научить применять теорию на практике; сформировать умения обобщать новый материал; сформировать умения математического чтения.
Теорема.
Всякую булеву функцию можно представить в виде: ( ) 1 1 1 1 1 ... ... 1 ( , ... ) ... n n n n n f f x x x x d d d d d d = = Ч Ч е (1). Нетрудно видеть, что 0 1 1; 0 x x x x x x = = = = Е Е , тогда x x d d = Е . Подставив в (1) вместо i i x d выражение i i x d Е , получим ( ) ( ) ( ) 1 1 1 1 1 ... ... 1 ( , ... ) ... n n n n n f f x x x x d d d d d d = = Е Ч Ч Е е . Раскрыв скобки по закону дистрибутивности и приведя подобные члены по правилу 0 A A = Е , придем к представлению функции: { } { } 1 1 1 1 ... 1 ... ... 1... ( , ... ) ... , (0 1) (2) s s s n i i n i i i i n f x x a x x ãäå a êî ýô ô èöèåí ò û èëè Н = - Ч Ч е Пустая конъюнкция считается равной 1, так что коэффициент, соответствующий пустому множеству индексов, представляет собой свободный член полинома. Представление функции в виде (2) называется
полиномом Жегалкина
. Устное задание: Дать словесное определение полинома Жегалкина. Полином Жегалкина константы равен самой же константе; полином Жегалкина булевой функции одной переменной 0 1 ( ) f x a a x = Е ; полином Жегалкина булевой функции двух переменных 0 1 2 12 ( , ) f x y a a x a y a xy = Е Е Е ; полином Жегалкина булевой функции трех переменных 0 1 2 3 12 23 13 123 ( , , ) f x y z a a x a y a z a xy a yz a xz a xyz = Е Е Е Е Е Е Е и т.д. Если у функции есть фиктивные переменные, то они не должны входить в полином Жегалкина.
Теорема.
Всякая булева функция может быть представлена в виде полинома Жегалкина (ПЖ) единственным образом.
Способы нахождения ПЖ:
1) с помощью законов алгебры логики а) из исходной формулы
Сначала формулу, реализующую функцию f, преобразуем в формулу, содержащую только операции отрицание и конъюнкцию. Затем , заменяем всюду подформулы вида A на 1 A Е , раскрываем скобки, пользуясь дистрибутивным законом ( ) A B C A B A C = Ч Е Ч Е Ч , и применяя тождества , 1 , 0, 0 A A A A A A A A A = = = = Ч Ч Е Е . Пример. Построить полином Жегалкина для функции f x y z = Ъ Ъ . ( ) ( ) ( ) 1 1 1 1 f x y z x y z x y z xyz xy yz xz x y z = = = = Ъ Ъ Ч Ч Е Е Е Е Е Е Е Е Е Е б) из СДНФ Пример. Построить полином Жегалкина для функции f x yz xy z x yz = Ъ Ъ . Строим СДНФ данной функции. ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 ÑÄÍ Ôf x yz xy z x yz x y z x y z x y z = = Ъ Ъ Е Е Е Е Е Е Е Для преобразования этого выражения могут быть использованы обычные приемы элементарной алгебры, за исключением правила 0 A A = Е . В частности, применяя группировку членов и вынесение за скобки, получаем ( ) ( ) ( ) ( 1) 1 f xy x y z xy y z xy x z xyz xz yz z xyz xy yz y xyz xz xyz xy z y = = Е Е Е Е Е Е Е Е = Е Е Е Е Е Е Е Е Е = Е Е Е 2) методом неопределенных коэффициентов Пусть % ( ) n P x - искомый полином Жегалкина, реализующий заданную функцию % ( ) n f x . Запишем его в виде % 0 1 1 12 1 2 1 1 1... 1 ( ) 1 ... ... ... ... n n n n n n n n P x x x x x x x x x a a a a a a - - = Ч Е Ч Е Е Ч Е Ч Ч Е Е Ч Ч Е Е Ч Ч Ч (3) Требуется найти неизвестные коэффициенты в этом разложении. Поступаем так. Для каждого ° n E a О составляем уравнение ( ) ( ) P f a a = , где ° ( ) P a - выражение, получающееся из формулы (3) при % ° x a = . Это дает систему из 2 n уравнений с 2 n неизвестными, которая имеет единственное решение. Решив систему, находим коэффициенты полинома % ( ) n P x . Пример. Методом неопределенных коэффициентов найти полином Жегалкина для функции f x y = ® . % 2 12 1 2 0 ( ) P x a xy a x a y a = Е Е Е
( ) ( ) ( ) ( ) 0 2 0 2 2 1 0 1 1 12 2 1 0 12 0 0 1 0 1 1 1 0 0 1 1 1 00 1 01 1 1 1 0 10 0 1 0 1 11 1 1 1 x y x y f x y f a f a a a a f a a a a f a a a a a Ï Æf xy x ® = ® = = = = = = Е Ю Е Ю = = = = Е Ю Е Ю = = = Е Е Е Ю = Е Е Пример. Методом неопределенных коэффициентов найти полином Жегалкина для функции ( ) 01101001 f a = . % 3 123 12 23 13 1 2 3 0 ( ) P x a xyz a xy a yz a xz a x a y a z a = Е Е Е Е Е Е Е 0 3 0 3 2 0 2 23 2 3 0 23 1 0 1 13 1 3 0 13 12 1 2 0 12 123 12 23 13 1 2 3 0 123 (000) 0 (001) 1 1 (010) 1 1 (011) 0 0 (100) 1 1 (101) 0 0 (110) 0 0 (111) 1 0 f a f a a a f a a a f a a a a a f a a a f a a a a a f a a a a a f a a a a a a a a a Ï Æf x y = = = = = Е Ю = = = Е Ю = = = Е Е Е Ю = = = Е Ю = = = Е Е Е Ю = = = Е Е Е Ю = = = Е Е Е Е Е Е Е Ю = Е z Е Если ПЖ не содержит конъюнкции, т.е. имеет вид 0 1 1 ... n n a a x a x Е Е Е ,то соответствующая ему функция называется линейной.
6.
Закрепление полученных знаний.
Цель:
развить практические навыки; сформировать умение самостоятельного решения задач Студенты самостоятельно выполняют задания по построению полинома Жегалкина различными способами. Некоторые решения по желанию студентов можно разобрать на доске, вызвав учащегося, который испытывает трудности. Предлагаемые задания: 1. Построить полиномы Жегалкина для функций а) ( )( ); f x y z xy z = Ъ Ъ Ъ б) ( ) ( ) | f x y x yz = ® Е . Ответ: а) f xy z = Е ; б) f xyz xy x = Е Е .
2. Методом неопределенных коэффициентов найти полиномы Жегалкина для функций: а) ( ) 01101001 f a = ; б) ( ) 100001110 f a = . Ответ: а) f x y z = Е Е ; б) 1 f yz x y z = Е Е Е Е .
7.
Выступление студента с сообщением о применении суммы по модулю два.
Цель:
расширить кругозор студентов; продемонстрировать творческую активность отдельных студентов. Логический элемент, соответствующий операции М2 (сумма по модулю два), показан на рис.3. РИС.3 Реализовать такой элемент в электронике достаточно сложно. Поэтому на практике он реализуется из набора простых и хорошо работающих элементов: И, НЕ, ИЛИ. Воспользовавшись свойством разложения в СДНФ, имеем схему, изображенную на рис.4.
РИС.4 Сравнивая операции двоичного сложения и суммы по модулю два, можно увидеть аналогию. Операция двоичного сложения в пределах последнего двоичного разряда имеет ту же последовательность символов, что и сумма по модулю два. Действительно, 0+0=0, 0+1=1, 1+0=1, 1+1=(1)0. Эти наблюдения дают основания для выдвижения ещё одной гипотезы: возможно применение суммы по модулю два в двоичном сумматоре для системы контроля и исправления ошибок. Действительно, если из-за неисправности в схеме один из аргументов исказится, то одновременно и значение функции изменится на противоположное, что сразу можно обнаружить на выходе. Поэтому операция сложения по модулю два имеет особое значение для организации работы компьютера: в схемах контроля и исправления ошибок используется это специфическое свойство. Существуют следующие разновидности логических схем: Сумматор двоичных чисел Полусумматор Вспомним, что при сложении двоичных чисел в каждом разряде образуется сумма и при этом возможен перенос в старший разряд. Полный одноразрядный сумматор Полный одноразрядный сумматор должен иметь три входа. Идея построения полного сумматора такая же, как и полусумматора. Многоразрядный сумматор Многоразрядный сумматор процессора состоит из полных одноразрядных сумматоров. На каждый разряд ставится одноразрядный сумматор, причем выход (перенос) сумматора младшего разряда подключается к входу сумматора старшего разряда.
Триггер Важнейшей структурной единицей оперативной памяти компьютера, а также внутренних регистров процессора является триггер. Это устройство позволяет запоминать, хранить, считывать, а в случае необходимости забывать информацию(каждый триггер может хранить 1 бит информации). Триггер можно построить из двух логических элементов ИЛИ и двух элементов НЕ. Теперь поясним, откуда берется название «сумма по модулю два». Обозначим остаток от деления целого числа М на число N как M mod N. Рассмотрим множество{0,1}, причем не абстрактных булевых символов, а обычных чисел (множество 2 Z ). Произведем на этом множестве операцию (а+b) mod 2. Имеем: (0+0) mod 2=0, (1+0) mod 2=(0+1) mod 2=1 mod 2=1, (1+1) mod 2=2 mod 2=0. Видим, что операция (а+b) mod 2 на множестве 2 Z совпадает со строгой дизъюнкцией на множестве {0,1}. Геометрическая интерпретация суммы по модулю два с различным числом переменных может быть представлена на плоскости для функции (рис.5) и в трехмерном пространстве для функции (рис.6).Закрашенные точки символизируют 1, выколотые-0. РИС.5
РИС.6 При любом обходе такого куба по его ребрам нельзя попасть из единичного значения в другое непосредственно, так как между этими значениями расположен хотя бы один нуль. За счет этого и происходит смена значений суммы по модулю два на противоположное при изменении значения одного из аргументов. По этой же причине сумма по модулю два не поддается минимизации через отрицания, дизъюнкции и конъюнкции, так как ее единичные значения не образуют ни общих ребер, ни общих граней. Ра практике если булева функция имеет много единиц и сложно минимизируется, то не исключено, что она имеет вид М2 или близкий к нему.
8.
Подведение итогов урока.
Цель:
обобщить материал урока. Контрольные вопросы: 1. Дать определение многочлена Жегалкина. Ответ: Многочленом Жегалкина называется многочлен, являющийся суммой константы и различных одночленов, в которые каждая переменная входит не выше, чем первой степени. 2. Перечислите способы построения полинома Жегалкина. Ответ: 1 способ – аналитический: из СДНФ; из исходной формулы. 2 способ – метод неопределенных коэффициентов.
3. Какая булева функция называется линейной? Ответ: Булева функция называется линейной, если в полиноме Жегалкина не содержится конъюнкций.
9.
Домашнее задание.
1. Повторить определения СДНФ, СКНФ, основные законы булевых функций. 2. Выучить определение многочлена Жегалкина. 3. Подумать, как можно определять линейность булевой функции, используя геометрическую интерпретацию суммы по модулю два. 4. Выразить через полином Жегалкина все функции алгебры логики от двух переменных. 5. Построить полиномы Жегалкина для следующих функций: ( ) ( ) ) (10011000) ) ) f a á f xy z xz y â f x yz y z a = = ® Е = Ъ Ъ Ч Список рекомендуемой литературы. 1. Хаггарти Р. Дискретная математика для программистов – М.: Техносфера, 2005 4. Спирин П. А., Спирина М. С. Дискретная математика. – М.: Академия, 2004 2. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2004 3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988 4. Гончарова Г. А., Молчалин А. А. Элементы дискретной математики. М.: Форум: Инфра-М, 2003
В раздел среднее профессиональное образование