Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Тульский государственный университет

Кафедра автоматизированных станочных систем

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания по выполнению контрольно-курсовой (контрольной) работы для студентов направления

220200 «Автоматизация и управление», специальности

220301 «Автоматизация технологических процессов и производств»

Разработал А.Б. Орлов

Тула 2008 г.

Введение

При решении задач синтеза систем управления разнообразными объектами необходимо использовать математический аппарат дискретной математики: математической логики и теории информации, которые базируются на теории множеств и теории графов.

1. Цель и задачи выполнения контрольно-курсовой работы

Целью выполнения контрольно-курсовой работы является овладения этим аппаратом дискретной математики и закрепление знаний, полученных на лекционных и практических занятиях выполняется контрольно-курсовая работа. В задачи контрольно-курсовой работы входит решение типовых задач дискретной математики, находящих практическое применение при синтезе систем управления.

2. Основные требования к контрольно-курсовой работе

2.1 Тематика контрольно-курсовой работы

Контрольно-курсовая работа (контрольная работа заочников) содержит следующие задания: карно арифметический десятичный

1.Выполнить арифметические операции в шестнадцатеричной, двоичной, восьмеричной и десятичной системах счисления.

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

3.Минимизировать (упростить) логическую функцию заданную таблицей истинности (соответствия), методом карт Карно. Для минимизированной функции построить логическую схему.

4.Построить граф конечного автомата по общей таблице выходов и переходов.

5.Смоделировать работу автомата для заданной последовательности входных слов и начального состояния.

Контрольно-курсовая работа подлежит защите, на которой студенту могут быть заданы вопросы по каждому из заданий работы. Если студент дает неправильные ответы по всем заданиям работы контрольно-курсовая работа считается выполненной несамостоятельно, не зачитывается и подлежит повторной защите.

2.2 Исходные данные к контрольно-курсовой работе

Исходными данными к контрольно-курсовой работе является задание на работу, выдаваемое преподавателем.

2.3Задание на контрольно-курсовой работу

Пример задания на контрольно-курсовую работу:

1.Выполнить сложение в шестнадцатеричной, двоичной, восьмеричной и десятичной системах счисления: ВD+19

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

	X0	X1	X2	X3	X4	X5	X6	X7
x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
y	1	1	1	1	0	0	0	1

3.Минимизировать (упростить) логическую функцию , заданную таблицей истинности (соответствия), методом карт Карно. Для минимизированной функции построить логическую схему.

	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	X14	X15
X1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
X2	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
X3	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
X4	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Y	1	1	1	1	1	0	0	0	1	1	1	1	1	0	0	1

4.Построить граф конечного автомата по общей таблице выходов и переходов. Смоделировать работу автомата для заданной последовательности входных слов и начального состояния.

X0

X1

X2

X3

0

1

2

3

4

5

S0

S2/Y1

S0/Y0

S3/Y3

S2/Y2

X()

X1

X2

X2

X0

X1

X3

S1

S3/Y7

S2/Y3

S2/Y5

S1/Y1

Y()

S2

S1/Y2

S0/Y6

S0/Y2

S2/Y3

S()

S2

S3

S1/Y0

S0/Y2

S0/Y0

S3/Y4

2.4 Объем контрольно-курсовой работы

Контрольно-курсовая работа содержит 4 задания и выполняется в форме пояснительной записки на листах формата А4.

2.5 Работа над контрольно-курсовой работой

Работа над контрольно-курсовой работой ведется в течение всего семестра.

2.6 Защита контрольно-курсовой работы

Защита ККР проводится преподавателю, который ее консультировал. При этом студенту могут быть заданы вопросы по тематике ККР с целью контроля самостоятельности ее выполнения. За защиту ККР студент может получить до 20 баллов за выполнение всех заданий работы и правильные ответы на вопросы при защите работы, при неправильных ответах оценка снижается на 5 балла за каждое задание работы, по которому был дан неверный ответ. Студенты, не выполнившие, или не защитившие контрольно-курсовую работу не допускаются к зачету. Защита работы может проходить в форме тестирования;

3. Методические указания к работе над контрольно-курсовой работой

Ниже приведен пример выполнения контрольно-курсовой работы для приведенного в настоящем методическом пособии варианта.

1. Первое задание. Вычисления в различных системах счисления:

В любой позиционной системе число, состоящее из K цифр - можно разложить по степеням некоторого числа a, которое называется основанием системы счисления:

Например, в двоичной системе счисления:

10_a= 1 a¹ +0 a⁰ = a

Легко показать, что в любой системе счисления число 10 равно основанию системы счисления а.

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

Десятичные числа	Шестнадцатеричные цифры	Двоичные числа (тетрады)	Двоичные числа (триады)	Восьмеричные цифры	Двоично-десятичные числа
0	0	0000	000	0	0000
1	1	0001	001	1	0001
2	2	0010	010	2	0010
3	3	0011	011	3	0011
4	4	0100	100	4	0100
5	5	0101	101	5	0101
6	6	0110	110	6	0110
7	7	0111	111	7	0111
8	8	1000			1000
9	9	1001			1001
10	A	1010			0001 0000
11	B	1011			0001 0001
12	C	1100			0001 0010
13	D	1101			0001 0011
14	E	1110			0001 0100
15	F	1111			0001 0101

Вычисления целесообразно начать с шестнадцатеричной системы, например

ВD+19

Результат вычислений удобно представить в виде столбца:

В крайнем правом столбце в результате вычисления получаем:

D + 9 = 13₁₀ + 9 = 22, поскольку 22>15, требуется перенос в старший разряд

22 = 16₁₀ + 6 =16₁₆

С учетом переноса в левом столбце получаем:

B + 1 + 1 = D

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

В= 1011₂

D= 1101₂

1 = 0001₂

9 = 1001₂

ВD= 1011 1101₂

19₁₆=0001 1001₂

Выполним сложение, учитывая, что

0+0= 0

1+0= 1

1+1 =10₂

1+1+1 =11₂

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

Выполнив обратный перевод результата в шестнадцатеричную систему счисления (по тетрадам) можно убедиться в его правильности:

1101₂ = D

0110₂ = 6

1101 0110₂ = D6

Выполним вычисления в восьмеричной системе счисления. Перевод в восьмеричную систему счисления удобно выполнять из двоичной системы счисления, разбивая число на триады, начиная с младших разрядов (справа).

ВD= 1011 1101₂ = 010 111 101₂

Из таблицы получаем:

010₂ = 2

111₂ = 7

101₂ = 5

ВD = 275₈

Аналогично получим:

19₁₆=0001 1001₂ = 000 011 001₂

000₂ = 0

011₂ = 3

001₂ = 1

19₁₆ = 31₈

Осуществим поразрядное сложение 275₈ + 31₈

В результате получим:

Вычисления выполняются аналогично шестнадцатеричной системе

5 + 1 = 6₈

7 + 3 = 10₁₀ , поскольку 10>7 требуется перенос в старший разряд

10₁₀ = 8₁₀ + 2 = 12₈

2 + 1 = 3₈

Таким образом:

275₈ + 31₈ = 326₈

Выполним проверку путем перевода результата в двоичную и шестнадцатеричную системы счисления

3₈ = 011₂

2₈ = 010₂

6₈ = 110₂

Отсюда получим

326₈ = 011 010 110₂ = 1101 0110₂ = D6₁₆

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

ВD= В 16¹+D 16⁰=11₁₀16+13₁₀=189₁₀

19₁₆= 1 16¹+9 16⁰=25₁₀

189₁₀+25₁₀=214₁₀

214₁₀=13₁₀16+6 =D6

Таким образом, результаты вычислений во всех системах счисления совпали.

2. Пример выполнения задания на минимизацию методом S-кубов.

Пусть некоторая логическая функция задана следующей таблицей соответствия:

	X0	X1	X2	X3	X4	X5	X6	X7
x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
y	1	1	1	1	0	0	0	1

Здесь аргументы функции, а входные слова - наборы значений аргументов. Например, .

На основе данной таблицы можно получить аналитическое выражение для логической функции в совершенной дизъюнктивной или конъюнктивной нормальной формах (СДНФ или СКНФ). Элементы СДНФ называют минитермами, а СКНФ - макстермами. СДНФ представляет собой дизъюнкцию минитермов, а СКНФ - конъюнкцию макстермов . В свою очередь, минитерм представляет собой конъюнкцию переменных или их инверсий (напрмер ), а макстерм - дизъюнкцию (например, ). Легко обнаружить, что минитерм равен 1 только при одном единственном входном слове, а макстерм равен 0 также только при одном единственном входном слове. По отношению к этим словам минитерм называют конституентой единицы, а макстерм - конституентой нуля. Тогда аналитическое выражение функции в форме СДНФ будет содержать конституенты единиц (и только их) для входных слов, при которых функция =1, а в форме СКНФ будет содержать конституенты нулей (и только их) для входных слов, при которых функция =0. При этом, если аргумент во входном слове =1, он входит в конституенту единицы в прямой форме, а в конституенту нуля - в инверсной. И наоборот, если аргумент во входном слове =0, он входит в конституенту нуля в прямой форме, а в конституенту единицы - в инверсной.

В результате для заданной функции можно получить следующие аналитические выражения в форме СДНФ

и СКНФ

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

Каноническая задача синтеза логических схем сводится к минимизации булевых функций, т. е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением закона склеивания и закона поглощения . Здесь под a и b можно понимать любую формулу алгебры логики. Однако при применении закона склеивания возникает проблема, что с чем склеивать, так как легко можно получить тупиковую форму, которая не будет минимальной, но не будет также и упрощаться. Поэтому для минимизации логических функций используют графо-аналитические методы, одним из которых является метод S-кубов.

Отобразим логическую функцию в логическом пространстве (Рисунок 1). Легко обнаружить, что данная логическая функция будут задана только в вершинах куба с длиной ребра, равной 1. Отметим (зачерним) все вершины (точки в логическом пространстве), в которых функция равна 1.

Для каждой вершины можно записать соответствующую ей конституенту единицы (рисунок 2). Легко обнаружить, что к конституентам единиц для точек, принадлежащих одному ребру можно применить закон склеивания. Тогда для ребер появятся новые конституенты, содержащие уже только две переменные. Аналогично к подобным конституентам для двух параллельных ребер, принадлежащих одной грани, также можно применить закон склеивания и получить значения переменных или их инверсий, выступающие в качестве конституент, соответствующих граням, что показано на рисунке 1. Тогда конституенты, соответствующие ребрам могут быть получены как конъюнкции конституент граней, на пересечении которых данное ребро находится.

Теперь можно легко получить минимальную форму, как дизъюнкцию конституент (минитермов), соответствующих точкам, ребрам, граням полностью покрывающим все зачерненные точки, в которых функция равна 1 (и только их). При этом нежелательно оставлять отдельные точки, а следует склеивать их в ребра.

Рисунок 1 - Минимизация логической функции методом S-кубов.



Рисунок 2 - Другие примеры конституент единицы на S-кубе.

Из рисунка 1 видно, что все точки могут быть покрыты гранью и ребром . Тогда минимальная форма для рассматриваемой функции будет иметь вид.

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

Таким образом, результат минимизации методом S-кубов проверен тождественными преобразованиями.

3. Минимизация методом карт Карно.

Методом карт Карно минимизируются функции с числом переменных до 5 - 6. Карта Карно представляет собой развертку логического пространства на плоскость (рисунок 3). Аналогично методу S-кубов на карте также можно выделить области, соответствующие переменным или их инверсиям.

Минимизируем с помощью карты Карно функцию, заданную следующей таблицей соответствия:

	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	X14	X15
x1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
x2	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
x3	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
x4	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Y	1	1	1	1	1	0	0	0	1	1	1	1	1	0	0	1

Отобразим данную функцию на карте Карно, проставив 1 в ячейки карты, соответствующие входным словам, при которых функция =1. Ребрам, граням и кубам на карте Карно соответствуют ортогональные области (блоки - строки, столбцы, квадраты, прямоугольники) заполненные 2, 4 и 8 единицами.

Рисунок 3 - Пример выполнения задания на минимизацию методом карт Карно.

Минитерм, соответствующий той иди иной области (блоку) определяется как конъюнкция переменных или их инверсий, соответствующих областям, на пересечении которых данная ассоциация находится. Минимальная форма формируется как дизъюнкция этих минитермов. Для приведенной функции минимальная форма будет содержать минитермы, соответствующие трем ассоциациям: из двух единиц, из четырех единиц и из 8 единиц (то есть через край карты будет полностью заполнена область )

В результате минимальная форма будет иметь вид:

Второй частью третьего задания является построение логической схемы для минимальной формы. Для полученной минимальной формы логическая схема будет иметь вид, представленный на рисунке 4.

Рисунок 4 - Логическая схема для минимальной формы

4. Построение графа автомата

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 5 - Таблицы, задающие состояния и переходы конечного автомата

X0

X1

X2

X3

0

1

2

3

4

5

S0

S2/Y1

S0/Y0

S3/Y3

S2/Y2

X()

X1

X2

X2

X0

X1

X3

S1

S3/Y7

S2/Y3

S2/Y5

S1/Y1

Y()

S2

S1/Y2

S0/Y6

S0/Y2

S2/Y3

S()

S2

S3

S1/Y0

S0/Y2

S0/Y0

S3/Y4

В данной таблице указано, какие слова обозначают те или иные элементы таблицы. Построение графа начинается с построения четырех вершин, соответствующих четырем состояниям автомата (рисунок 6). Затем построение ведется по строкам таблицы. Например, первая строка соответствует состоянию S_0. . Из соответствующей вершины для каждого входного слова X в графе проводится соответствующая дуга. Концом дуги будет вершина, соответствующая состоянию, в которое перейдет автомат в следующем такте, если на его вход подано слово X. Около каждой дуги указывается ее вес - в числителе входное слово, при котором произойдет данный переход, а в знаменателе - выходное слово, которое при этом установится. Например, при входном слове X₂ из S₀ на выходе установится слово Y₃ и в следующем такте произойдет переход в состояние S_3.

Подобное построение осуществляется для каждого исходного состояния конечного автомата (каждой строки). Пример полностью построенного графа приведен на рисунке 6.



Рисунок 6 - Граф конечного автомата.

По графу требуется осуществить моделирование работы автомата при подаче на него некоторой последовательности входных слов. Для каждого входного слова и данного состояния по графу определяется выходное слово и состояние в следующем такте S(?+1). Затем процедура повторяется для этого нового состояния и т.д. Пример моделирования работы автомата приведен ниже

	0	1	2	3	4	5
X()	X1	X2	X2	X0	X1	X3
Y()	Y6	Y3	Y0	Y1	Y6	Y2
S()	S2	S0	S3	S0	S2	S0

Библиографический список

Основная литература

1. Сигорский В.П. Математический аппарат инженера. - Киев, Техника, 1975, - 768 с

2. Белоусов А.И., Ткачев С.Б. Дискретная математика. - М.: МГТУ им. Баумана, 2001, - 744 с.

3. Яблонский С.В. Введение в дискретную математику. - М.: "Наука", 1986, - 384 с.

4. Нефедов В.Н., Осипова В.А. курс дискретной математики.- М. МАИ, 1992, - 262 с.

Дополнительная литература

Тимковский В.Н. Дискретная математика в мире станков и деталей. - М.: "Наука", 1992, - 144 с.

Новиков Ф.А. Дискретная математика для программистов. - СПб.: - Питер, - 2000,-304 с.

Клячкин В.Н., Афанасьева Т.В. Основы дискретной математики в машиностроительном проектировании.- Ульяновск, 1995. -60 с.

Размещено на Allbest.ru