У к а з а н и е. Проверку равносильности совершенных нормальных форм функции проводят преобразованием СКНФ в СДНФ или наоборот. Можно также обе формы преобразовать в одно и то же выражение.

Государственный комитет Российской федерации

По высшему образованию

Новочеркасский государственный технический университет

МАТЕМАТИЧЕСКИЕ ОСНОВЫ

ТЕОРИИ ЦИФРОВЫХ СИСТЕМ

Программа, методические указания и контрольные задания для студентов-заочников специальности 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.

Не нашли, что искали? Воспользуйтесь поиском по сайту: