- •1. Общие указания
- •2. Программа и методические указания к темам
- •Тема 1. Элементы и средства теоретико-множественного описания систем
- •Тема 2. Элементы теории графов
- •Методические указания
- •Тема 3. Элементы математической логики
- •Методические указания
- •Тема 4. Элементы теории конечных автоматов
- •Методические указания
- •3. Задания на контрольную работу и указания к её выполнению
3. Задания на контрольную работу и указания к её выполнению
В контрольную работу включены четыре задачи. Номера вариантов каждой задачи определяются по двум последним цифрам шифра зачетной книжки из табл.1.
Таблица 1
Предпоследняя |
Последняя цифра шифра |
|||||||||
цифра шифра |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 |
2 11 26 31 |
5 14 25 34 |
9 15 24 39 |
1 13 27 32 |
6 17 30 34 |
3 11 29 33 |
10 15 23 40 |
4 16 22 38 |
9 12 28 33 |
5 15 21 39 |
1 |
4 18 21 40 |
1 16 30 35 |
3 11 22 37 |
9 20 29 34 |
5 12 23 37 |
9 16 27 32 |
7 19 28 35 |
8 14 25 31 |
6 17 24 31 |
1 19 26 37 |
2 |
9 13 22 35 |
6 20 26 37 |
2 17 21 38 |
7 19 23 32 |
3 14 29 38 |
8 18 27 36 |
2 12 24 39 |
10 18 28 34 |
1 13 30 36 |
4 11 25 31 |
3 |
1 16 27 31 |
4 12 24 39 |
7 19 30 33 |
9 11 22 38 |
5 15 28 31 |
8 11 26 35 |
1 15 23 40 |
9 12 21 36 |
4 12 29 33 |
2 20 25 36 |
4 |
7 20 23 40 |
2 19 21 33 |
8 14 29 37 |
5 15 25 35 |
8 18 27 40 |
4 19 24 32 |
10 20 28 36 |
5 15 26 40 |
9 20 22 31 |
7 18 30 38 |
5 |
6 19 23 33 |
10 17 28 31 |
2 13 26 37 |
8 16 21 39 |
1 20 25 34 |
2 14 29 40 |
7 12 24 36 |
1 20 30 38 |
6 19 22 40 |
3 16 27 32 |
6 |
3 12 25 40 |
5 15 27 36 |
10 20 23 33 |
4 18 29 36 |
6 13 22 39 |
10 15 28 32 |
4 17 24 35 |
10 19 30 39 |
7 11 26 37 |
9 12 21 40 |
7 |
8 14 30 34 |
2 18 25 32 |
6 12 21 38 |
10 14 26 37 |
8 19 28 32 |
3 11 27 35 |
7 18 23 39 |
6 13 24 32 |
8 18 29 34 |
6 17 22 35 |
8 |
6 17 28 32 |
10 13 22 35 |
4 16 29 37 |
7 17 23 34 |
2 14 26 35 |
5 17 30 38 |
1 16 25 33 |
8 15 27 38 |
9 16 21 37 |
3 13 24 31 |
9 |
3 11 21 36 |
7 14 23 31 |
3 18 27 39 |
5 12 24 33 |
10 16 29 38 |
4 20 25 34 |
6 13 30 36 |
3 17 22 34 |
8 11 28 33 |
1 14 26 40 |
З а д а ч а 1. Для заданной в табл.2 логической функции F(x,y,z) выполнить следующие действия:
1) построить множество истинности;
2) составить таблицу истинности функции;
3) составить логическую схему, соответствующую заданной функции в базисе И,ИЛИ,НЕ.
Таблица 2
Вар. |
F(x,y,z) |
Вар. |
F(x,y,z) |
1 |
(x+)z |
6 |
|
2 |
z+ |
7 |
|
3 |
y(+z) |
8 |
|
4 |
+x |
9 |
|
5 |
x+y |
10 |
У к а з а н и е. Множество истинности строится в виде диаграммы Эйлера-Венна. В прямоугольнике универсального множества изображаются три взаимно пересекающихся исходных множества истинности каждой логической переменной (сами множества, а не их дополнения!). Над диаграммой указывается аналитическая запись множества истинности заданной логической функции. Например, для функции множество истинности будет . Построение множества истинности для функции трех переменных осуществляется в два этапа. На первом этапе находится и штрихуется множество для двух переменных. На втором - штрихуется в другую сторону множество с учётом третьей переменной. Результирующее множество обводится жирной линией.
З а д а ч а 2. Для заданной в табл.3 логической функции F(a,b,...x,y,z) произвести упрощение методом равносильных преобразований, используя основные законы и тождества алгебры логики. Полученный результат представить в виде логической схемы в трёх вариантах:
1) с наименьшим количеством стандартных логических элементов;
2) в базисе И-НЕ;
3) в базисе ИЛИ-НЕ.
У к а з а н и е. Упрощение логической функции рекомендуется начинать с применения закона поглощения – это чаще всего скорейший путь получения требуемого результата.
Таблица 3
Вар |
Логическая функция |
11 |
|
12 |
|
13 |
|
14 |
|
15 |
] |
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
Для каждой из схем должна быть записана соответствующая математическая модель в виде логической функции. Уменьшение количества задействованных логических элементов в п.1 возможно введением в упрощенную формулу, выраженную через простейшие логические операции И, ИЛИ и НЕ, более сложных элементарных логических функций (неравнозначности, эквивалентности, импликации и запрета), каждая из которых представлена одним логическим элементом. В п.п. 2 и 3 перед составлением схемы формула упрощенной логической функции преобразуется и записывается в соответствующем базисе (кроме единственной операции базиса никаких других операций – например, инверсии – в формуле не должно оставаться!).
З а д а ч а 3. Для функции, приведенной в табл.4, выполнить следующие действия:
1) представить функцию в базисе И,ИЛИ,НЕ;
2) найти СДНФ функции;
3) найти СКНФ функции.
У к а з а н и е. В п.1 входящие в формулы элементарные логические функции заменяются равносильными представлениями в базисе И,ИЛИ,НЕ. Полученные выражения преобразуются и упрощаются в соответствии с законами и тождествами алгебры логики для нахождения ДНФ и КНФ функции. В п.п. 2 и 3 эти ДНФ и КНФ преобразуются в СДНФ и СКНФ функций. Синтез СДНФ и СКНФ по составленной таблице истинности функции допускается только для проверки полученных ранее выражений.
Таблица 4
Вар |
Логическая функция |
Вар. |
Логическая функция |
21 |
|
26 |
|
22 |
|
27 |
|
23 |
|
28 |
|
24 |
|
29 |
|
25 |
|
30 |
|
З а д а ч а 4. Для логической функции F(x,y,z), заданной таблицей истинности (см.табл.5), выполнить следующие действия:
1) составить логические формулы в виде СДНФ и СКНФ;
2) показать равносильность полученных выражений, упростив полученные СДНФ и СКНФ;
3) найти минимизированные формулы логической функции в виде ДНФ и КНФ с использованием метода карт Карно.
Таблица 5
Наборы переменных |
Номер варианта |
|||||||||||
х |
y |
z |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
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.