У к а з а н и е. Проверку равносильности совершенных нормальных форм функции проводят преобразованием СКНФ в СДНФ или наоборот. Можно также обе формы преобразовать в одно и то же выражение.
Государственный комитет Российской федерации
По высшему образованию
Новочеркасский государственный технический университет
МАТЕМАТИЧЕСКИЕ ОСНОВЫ
ТЕОРИИ ЦИФРОВЫХ СИСТЕМ
Программа, методические указания и контрольные задания для студентов-заочников специальности 21010665 «Промышленная электроника»
Новочеркасск 2006-
Общие указания
В дисциплину “Математические основы теории цифровых систем” включены разделы, которые отсутствуют в базовом курсе высшей математики, либо рассмотрены недостаточно полно. Целью изучения данной дисциплины являются:
- освоение математического аппарата, необходимого для составления математических моделей цифровых систем и для успешного изучения последующих дисциплин учебного плана специальности 21010665;
- развитие общей инженерной эрудиции и формирование квалифицированного специалиста по промышленной электронике.
Учебным планом по дисциплине предусмотрено 8 часов установочных и обзорных лекций, 6 часов практических занятий, выполнение одной контрольной работы, итоговый теоретический зачёт.
Учебный материал изложен во многих пособиях и монографиях. Некоторые из них приведены в библиографическом списке. Основным является пособие [1]. При изучении материала следует ознакомиться с имеющимися указаниями к разделам, ответить на вопросы и выполнить упражнения для самоконтроля. Остальная литература может рассматриваться как дополнительная.
Программа и методические указания к темам
Введение
Предмет «Математические основы теории цифровых систем». Понятие об управлении. Информатика и управление. Математические модели дискретных систем управления.
Литература [1]. с. 4 - 6.
Тема 1. Элементы и средства теоретико-множественного описания систем
Множества и подмножества. Разновидности множеств (конечные, бесконечные, счётные, несчётные, линейные и др.). Эквивалентные множества. Подмножества и их свойства. Операции над множествами. Универсальное множество. Дополнение множества. Основные законы и тождества алгебры множеств.
Соответствия, отображения и функции. Способы задания функций. Отношения и их свойства.
Литература [1]. с. 7 - 18.
Тема 2. Элементы теории графов
Графы, основные понятия и определения. Ориентированные и неориентированные графы. Подграфы и частичные графы. Способы задания и матричное описание графов.
Разновидности графов. Связные и несвязные графы, компоненты связности. Деревья и лес. Цикломатическое число графа.
Основные действия над графами. Раскраска вершин графа. Бихроматические графы, максимальная двудольная часть графа.
Литература [1]. с. 19 - 25.
Методические указания
Основные понятия теории множеств являются базовыми для описания многих математических соотношений и зависимостей, в том числе и для раскрытия содержания последующих тем данной дисциплины.
С помощью графов можно дать наглядное представление состояний и связей цифровых систем. Понятие графов используется как в последующих разделах, так и в других дисциплинах специальности.
В результате изучения тем 1 и 2 студент д о л ж е н з н а т ь:
- символику обозначений и основные определения теории множеств и графов;
- соотношения между множествами, а также между элементами разных множеств;
- основные действия и законы алгебры множеств;
- различные способы представления графов;
- разновидности графов.
д о л ж е н у м е т ь:
- применять основные законы и действия для конкретно заданных множеств;
- графически интерпретировать множества в виде диаграмм Эйлера-Венна;
- использовать основные понятия и действия для описания (задания) соответствий, отбражений и отношений.
- представлять заданные отношения в виде графов;
- выполнять действия над конкретно заданными графами.
Тема 3. Элементы математической логики
Логические функции и способы их представления. Множества истинности логических функций.
Алгебра логики (булева алгебра). Логические операции и порядок их выполнения. Законы и тождества алгебры логики. Элементарные логические функции. Представление логических функций в заданном базисе.
Нормальные и совершенные нормальные формы логических функций и их свойства. Термы, конституенты единицы (минтермы), конституенты нуля (макстермы). Синтез и минимизация логических функций.
Литература [1]. с. 26 - 44.
Методические указания
Логические функции широко используются для построения абстрактных математических моделей и проектирования дискретных устройств автоматики, телемеханики и вычислительной техники, в том числе, интегральных микросхем. Они позволяют по словесному описанию (заданию) составить математическую конкретную модель устройства управления (автоматики), позволяющую затем составить электрическую схему.
В данной дисциплине изучается двузначная логика. Основные понятия алгебры логики, являющейся разновидностью булевых алгебр, базируются на понятиях алгебры множеств. В частности, для успешного усвоения понятия «логическая функция» следует хорошо разобраться с представлением ее множеством истинности.
В результате изучения темы н е о б х о д и м о з н а т ь :
- понятия, определения и символику обозначений;
- способы представления (задания) логических функций;
- основные законы и тождества алгебры логики;
- элементарные логические функции и их представление в базисе И,ИЛИ,НЕ;
- способы доказательства равносильности логических выражений.
Студент д о л ж е н у м е т ь :
- по формуле логической функции составить таблицу истинности, множество истинности и логическую схему;
- преобразовывать и упрощать сложные логические функции, применяя основные законы и тождества алгебры логики;
- представлять конкретную логическую функцию в СДНФ, в СКНФ, а также в заданном базисе;
- синтезировать формулу логической функции по заданной таблице истинности;
- минимизировать логические функции, в том числе неполностью заданные.
Тема 4. Элементы теории конечных автоматов
Абстрактный автомат, основные понятия и определения. Конечные автоматы без памяти (комбинационные автоматы) и автоматы с памятью. Структурный автомат. Автоматы Мили и Мура. Общие сведения о микропрограммных автоматах.
Способы задания автоматов. Синтез одновыходных и многовыходных комбинационных автоматов. Табличный и графический методы синтеза автоматов с памятью по словесному описанию.
Литература [1]. с. 45 - 28.
Методические указания
Конечный автомат является абстрактной моделью цифровых устройств автоматики, управления и контроля. Материал данной темы в значительной мере использует сведения из предыдущих разделов дисциплины.
После изучения материала темы студенту необходимо знать:
- термины и понятия описания конечных автоматов - алфавиты входа, выхода и состояний, функции переходов и выходов;
- почему автоматы называются конечными и дискретными;
- особенности асинхронных и синхронных автоматов;
- разновидности автоматов с памятью и отличительные особенности соответствующих структурных автоматов;
- в каких автоматах используется гибкая логика и в чем её отличие от жёсткой.
Студент д о л ж е н у м е т ь :
- составить классификацию рассмотренных разновидностей конечных автоматов;
- различать комбинационные автоматы и автоматы с памятью;
- по словесному описанию (заданию) определить тип автомата и составить таблицы и графы функционирования автомата;
- составлять развёрнутую таблицу функционирования и синтезировать логическую схему автомата.
Задания на контрольную работу и указания к её выполнению
В контрольную работу включены четыре задачи. Номера вариантов каждой задачи определяются по двум последним цифрам шифра зачетной книжки из табл.1.
Таблица 1
Предпоследняя
| Последняя цифра шифра
| цифра шифра
|
|
|
|
|
|
|
|
|
|
|
|
|
14 25 34
|
15 24 39
|
13 27 32
|
17 30 34
|
11 29 33
| 10 15 23 40
|
16 22 38
|
12 28 33
|
15 21 39
|
|
18 21 40
|
16 30 35
|
11 22 37
|
20 29 34
|
12 23 37
|
16 27 32
|
19 28 35
|
14 25 31
|
17 24 31
|
19 26 37
|
|
13 22 35
|
20 26 37
|
17 21 38
|
19 23 32
|
14 29 38
|
18 27 36
|
12 24 39
| 10 18 28 34
|
13 30 36
|
11 25 31
|
|
16 27 31
|
12 24 39
|
19 30 33
|
11 22 38
|
15 28 31
|
11 26 35
|
15 23 40
|
12 21 36
|
12 29 33
|
20 25 36
|
|
20 23 40
|
19 21 33
|
14 29 37
|
15 25 35
|
18 27 40
|
19 24 32
| 10 20 28 36
|
15 26 40
|
20 22 31
|
18 30 38
|
|
19 23 33
| 10 17 28 31
|
13 26 37
|
16 21 39
|
20 25 34
|
14 29 40
|
12 24 36
|
20 30 38
|
19 22 40
|
16 27 32
|
|
12 25 40
|
15 27 36
| 10 20 23 33
|
18 29 36
|
13 22 39
| 10 15 28 32
|
17 24 35
| 10 19 30 39
|
11 26 37
|
12 21 40
|
|
14 30 34
|
18 25 32
|
12 21 38
| 10 14 26 37
|
19 28 32
|
11 27 35
|
18 23 39
|
13 24 32
|
18 29 34
|
17 22 35
|
|
17 28 32
| 10 13 22 35
|
16 29 37
|
17 23 34
|
14 26 35
|
17 30 38
|
16 25 33
|
15 27 38
|
16 21 37
|
13 24 31
|
|
11 21 36
|
14 23 31
|
18 27 39
|
12 24 33
| 10 16 29 38
|
20 25 34
|
13 30 36
|
17 22 34
|
11 28 33
|
14 26 40
| З а д а ч а 1. Для заданной в табл.2 логической функции F(x,y,z) выполнить следующие действия:
1) построить множество истинности;
2) составить таблицу истинности функции;
3) составить логическую схему, соответствующую заданной функции в базисе И,ИЛИ,НЕ.
Таблица 2
Вар.
| F(x,y,z)
| Вар.
| F(x,y,z)
|
| (x+ )z
|
|
|
| z+
|
|
|
| y( +z)
|
|
|
| +x
|
|
|
| x+y
|
|
|
У к а з а н и е. Множество истинности строится в виде диаграммы Эйлера-Венна. В прямоугольнике универсального множества изображаются три взаимно пересекающихся исходных множества истинности каждой логической переменной (сами множества, а не их дополнения!). Над диаграммой указывается аналитическая запись множества истинности заданной логической функции. Например, для функции множество истинности будет . Построение множества истинности для функции трех переменных осуществляется в два этапа. На первом этапе находится и штрихуется множество для двух переменных. На втором - штрихуется в другую сторону множество с учётом третьей переменной. Результирующее множество обводится жирной линией.
З а д а ч а 2. Для заданной в табл.3 логической функции F(a,b,...x,y,z) произвести упрощение методом равносильных преобразований, используя основные законы и тождества алгебры логики. Полученный результат представить в виде логической схемы в трёх вариантах:
1) с наименьшим количеством стандартных логических элементов;
2) в базисе И-НЕ;
3) в базисе ИЛИ-НЕ.
У к а з а н и е. Упрощение логической функции рекомендуется начинать с применения закона поглощения – это чаще всего скорейший путь получения требуемого результата.
Таблица 3
Для каждой из схем должна быть записана соответствующая математическая модель в виде логической функции. Уменьшение количества задействованных логических элементов в п.1 возможно введением в упрощенную формулу, выраженную через простейшие логические операции И, ИЛИ и НЕ, более сложных элементарных логических функций (неравнозначности, эквивалентности, импликации и запрета), каждая из которых представлена одним логическим элементом. В п.п. 2 и 3 перед составлением схемы формула упрощенной логической функции преобразуется и записывается в соответствующем базисе (кроме единственной операции базиса никаких других операций – например, инверсии – в формуле не должно оставаться!).
З а д а ч а 3. Для функции, приведенной в табл.4, выполнить следующие действия:
1) представить функцию в базисе И,ИЛИ,НЕ;
2) найти СДНФ функции;
3) найти СКНФ функции.
У к а з а н и е. В п.1 входящие в формулы элементарные логические функции заменяются равносильными представлениями в базисе И,ИЛИ,НЕ. Полученные выражения преобразуются и упрощаются в соответствии с законами и тождествами алгебры логики для нахождения ДНФ и КНФ функции. В п.п. 2 и 3 эти ДНФ и КНФ преобразуются в СДНФ и СКНФ функций. Синтез СДНФ и СКНФ по составленной таблице истинности функции допускается только для проверки полученных ранее выражений.
Таблица 4
Вар
| Логическая функция
| Вар.
| Логическая функция
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З а д а ч а 4. Для логической функции F(x,y,z), заданной таблицей истинности (см.табл.5),выполнить следующие действия:
1) составить логические формулы в виде СДНФ и СКНФ;
2) показать равносильность полученных выражений, упростив полученные СДНФ и СКНФ;
3) найти минимизированные формулы логической функции в виде ДНФ и КНФ с использованием метода карт Карно.
Таблица 5
Наборы переменных
| Номер варианта
| х
| y
| z
|
|
|
|
|
|
|
|
|
|
| 0
| 0
| 0
|
|
|
|
|
|
|
|
|
|
| 0
| 0
| 1
|
|
|
|
|
|
|
|
|
|
| 0
| 1
| 0
|
|
|
|
|
|
|
|
|
|
| 0
| 1
| 1
|
|
|
|
|
|
|
|
|
|
| 1
| 0
| 0
|
|
|
|
|
|
|
|
|
|
| 1
| 0
| 1
|
|
|
|
|
|
|
|
|
|
| 1
| 1
| 0
|
|
|
|
|
|
|
|
|
|
| 1
| 1
| 1
|
|
|
|
|
|
|
|
|
|
|
У к а з а н и е. Проверку равносильности совершенных нормальных форм функции проводят преобразованием СКНФ в СДНФ или наоборот. Можно также обе формы преобразовать в одно и то же выражение.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Основная литература
1. Жмурин Д.Н. Математические и информационные основы теории цифровых систем: Уч. пособие, Ч.1. Теоретико-множественное описание и логический синтез цифровых систем. / Юж.-Рос. гос. техн. ун-т. Новочеркасск: ЮРГТУ, 2002.--63 с.
Дополнительная литература
2. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Уч. пособие для втузов. - С.Пб.: Политехника, 1996. - 885 с.
3. Горбатов В.А. Основы дискретной математики: Уч. пособие. - М.: Высш. шк., 1986.- 312 с.
3. Коршунов Ю.М. Математические основы кибернетики. - М.: Энергоатомиздат,1987. 496 с.
4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергия, 1980. - 344 с.
Учебное издание
Дмитрий Николаевич Жмурин
Математические основы теории цифровых систем: Программа, методические указания и контрольные задания для студентов-заочников специальности 21010665 «Промышленная электроника
Редактор ………………………….
------------------------------------------------------------------------------------------------------------------ ЛР №020417. 12.02.97
Темплан 2006г. . Подписано в печать ………..
Формат 60х84 1/16. Бумага офсетная. Печать оперативная.
Печ.л. 0,7. . Уч.-изд.л. 0,75. Тираж 50 экз. Заказ
Южно-Российский государственный технический университет
Редакционно-издательский отдел ЮРГТУ
Адрес университета: 346428, г. Новочеркасск, ул. Просвещения, 132.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|