Государственный комитет Российской Федерации по высшему образованию

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

Кафедра ???

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по предмету

математические основы теории систем

тема курсовой работы:

« Синтез комбинационных схем и конечных

автоматов. Сети Петри ».

Выполнил : студент гр. ??–??–??

????

номер зачётной книжки ??–??–???

Руководитель : ????

????

???

1999

Государственный комитет Российской Федерации по высшему образованию

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

ЗАДАНИЕ

На курсовую работу

Студенту гр.

По дисциплине

Тема курсовой работы

Исходные данные

1 Выполнить расчёты:

1.1

1.2

1.3

1.4

2 Выполнить графические работы:

2.1

2.2

3 Выполнить научные и учебно-исследовательские работы:

3.1

3.2

3.3

3.4

4 Оформить расчётно-пояснительную записку

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

Задание выдано

Срок сдачи работы

Задание принял

Руководитель

Работа защищена

С оценкой

ЧЛЕНЫ КОМИССИИ :

РЕФЕРАТ

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ, КОМБИНАЦИОННАЯ СХЕМА, МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ, АВТОМАТ МИЛИ, СЕТЬ ПЕТРИ.

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

Вторая часть содержит основные понятия и определения из теории конечных автоматов, а также пример их использования для конкретного автомата. Сюда входит минимизация конечных автоматов по числу состояний, минимизация булевых функций, описывающих комбинационную часть с последующей реализацией полученного автомата на логических элементах из определённого базиса и элементах памяти – триггерах и задержках.

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

Курсовая работа содержит 38 страниц, 11 рисунков, 8 таблиц,

4 источника, 1 приложение .

СОДЕРЖАНИЕ

Введение ………………………………………………………………6

1 Синтез комбинационных схем

1.1 Постановка задачи ……………………………………………… 7

1.2 Теоретические сведения …………………………………………7

1.3 Расчёты и полученные результаты ……………………………..9

1.4 Выводы по разделу………………………………………………13

2 Синтез конечных автоматов

2.1 Постановка задачи ……………………………………………… 14

2.2 Теоретические сведения …………………………………………14

2.3 Расчёты и полученные результаты …………………………… 16

4. Выводы по разделу……………………………………………… 20

3 Сети Петри

3.1 Постановка задачи ……………………………………………… 21

3.2 Теоретические сведения ……………………………………… 21

3.3 Расчёты и полученные результаты …………………………… 26

3.4 Выводы по разделу……………………………………………… 31

Заключение …………………………………………………………. 32

Литература ………………………………………………………… 33

Приложение А ……………………………………………………… 34

ВВЕДЕНИЕ

Работа посвящена синтезу дискретных устройств с “памятью” (конечных автоматов) и “без памяти” (комбинационных схем), а также анализу реально протекающих процессов с помощью сетей Петри.

В первой части рассмотрена минимизация булевых функций, заданных в виде СДНФ, с помощью двух различных способов : карт Карно и метода склеивания Квайна – МакКласки. Полученные в виде минимизированных ДНФ функции были приведены к базисам, состоящим всего из одной функции : И – НЕ и ИЛИ – НЕ , а затем реализованы в виде комбинационных схем на соответствующих логических элементах.

Во второй части заданный по условию в функциональном виде конечный автомат был минимизирован по числу состояний. Для полученного автомата был построен граф состояний. Затем, перейдя к двоичному представлению входных, выходных сигналов и сигналов состояния, в автомате были выделены элементы памяти и комбинационная часть, которая затем была минимизирована по числу переменнных. Автомат был реализован в базисе И – ИЛИ – НЕ с использованием D - триггера и задержки.

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

1 Синтез комбинационных схем

1. Постановка задачи

Для двух булевых функций, построенных по варианту задания в виде

(1.1.1)

, (1.1.2)

где g_i, z_i – десятичные числа из диапазона от 0 до 15 в двоичном виде,

сделать следующее:

а) представить F₁ и F₂ в виде СДНФ.

б) минимизировать (по количеству переменных в ДНФ) F₁ с

помощью карт Карно, F₂ – методом Квайна-МакКласки.

в) реализовать в виде комбинационной схемы на логических элементах F₁ – в базисе И – НЕ, F₂ – в базисе ИЛИ – НЕ, предварительно приведя F₁ и F₂ к соответствующим базисам.

g_i и z_i вычислять по выражениям:

(1.1.3)

(1.1.4)

при g₀ = A, z₀ = B . Параметр изменять от 1 до тех пор, пока не будет получено 9 различных значений g_i и z_i.

2. Теоретические сведения.

Булевой алгеброй называется множество S объектов A, B, C…, в котором определены две бинарные операции (логическое сложение – дизъюнкция(+) и логическое умножение – конъюнкция(∙)) и одна унарная операция(логическое отрицание()). Оно обладает следующими свойствами:

а) Для A, B, C S

1. , (замкнутость);

2. (коммутативные законы);

3. (ассоциативные законы);

4. (дистрибутивные законы);

5. (свойства идемпотентности);

6. в том и только том случае, если

(свойство совместимости);

7. S содержит элементы 1 и 0 такие, что для всякого элемента

;

8. для каждого элемента A класс S содержит элемент Г (дополнение элемента A, часто обозначаемое символами Ā или 1- A ) такой, что

, .

В каждой булевой алгебре

(законы поглощения),

(законы склеивания),

(двойственность, законы де Моргана).

Если даны n булевых переменных X₁, X₂,…, X_n, каждая из которых может быть равна любому элементу булевой алгебры, то булевой функцией называется выражение

(1.2.1)

В каждой булевой алгебре существует ровно различных булевых функций n переменных.

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

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

Введём понятие многомерного куба.

Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью соответствующей размерности: если оно представляет собой конъюнкцию n переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами.

Комплекс K(y) кубов функции y=ƒ(x₁,x₂,…,x_n) есть объединение K^s(y) множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем обозначать через x.

3. Расчёты и полученные результаты.

По варианту задания находим g_i и z_i:

i	gi	zi
0	5	0
1	1	6
2	8	2
3	5	9
4	13	6
5	11	14
6	4	12
7	3	5
8	13	4
9	13	14
10	8	14
11	9	9
12	5	10
13	7	6

Неповторяющиеся значения g_i: 5, 1, 8, 13, 11, 4, 3, 9, 7. Неповторяющиеся значения z_i: 0, 6, 2, 9, 14, 12, 5, 4, 10. Таким образом, для F₁ получаем выражение

, (1.3.1)

для F₂:

. (1.3.2)

Для минимизации первой функции применяем метод карт Карно.

Карта Карно – прямоугольник с 2ⁿ клетками, каждой из которых соответствует своя конъюнкция из n переменных и их отрицаний (дополнений).

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

x₃x₄

00 01 11 10