Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри

Государственный комитет РоссийскойФедерации по высшему образованиюКубанский государственныйтехнологический университетКафедра ???ПОЯСНИТЕЛЬНАЯЗАПИСКА

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

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

 

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

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

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

                                               

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

                                                                                        ????

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

 

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

                                                                                         ????            

???

1999

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

ЗАДАНИЕ

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

/>Студентугр.

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

/> /> /> /> <td/> /> /> /> />

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

/> /> /> /> <td/> /> /> /> />

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

/> /> /> /> <td/> /> /> /> /> /> /> /> /> <td/> /> /> /> /> /> /> <td/> />

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 Основная литература

/> /> /> /> /> /> <td/> /> /> /> <td/> /> /> /> />

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

/>


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

/>


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

/>


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

/>


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

/>


С оценкой

/>


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


РЕФЕРАТ

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

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

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

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

     Курсовая работасодержит   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

2.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.1.2)

где gi, zi<sub/>– десятичные числа из диапазона от 0 до 15 в двоичномвиде,

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

а)  представить F1 и F2 ввиде СДНФ.

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

помощью карт Карно, F2<sub/>– методомКвайна-МакКласки.

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

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

                                  />                                              (1.1.3)

                                  />                                              (1.1.4)

приg= A, z0 = B.Параметр /> изменять от 1 до тех пор, пока не будет получено 9различных значений gi и zi.

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

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

а) Для /> A,B, C  />  S 

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

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

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

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

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

6)  /> втом и только том случае, если

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

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

                        />;

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

                                     />,    />.

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

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

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

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

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

                                   />                                            (1.2.1)

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

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

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

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

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

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

 

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

По варианту задания находим  gi  и  zi:

i

gi

zi

5

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

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

      />,        (1.3.1)

для  F2:

     />.        (1.3.2)

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

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

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

                                      

                                                              x3x4 

/>                                                    00         01         11          10

 

                                           00                    1            1

 

 

                                           01       1           1             1   

                               

                                  x1x2

                                          11                     1

 

 

                                           10       1           1             1

 

 

                                                     Рисунок  1.2.1 – картаКарно         

На основании выбранной комбинациипокрытий выписываем минимизированное выражение для функции F1:

                         />.                    (1.3.3)   

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

На первом шаге алгоритма выписываем комплекс K0-кубов заданной функции, упорядоченных повозрастанию количества единиц:

/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/> /> <td/> /> <td/> <td/> /> /> />

                                     0   0 0   0 0 1 1 1 1

                                     0   0 1  1 1 0 0 1  1

                   K0 =         0    1 0   0 1 0 1 0  1                                         (1.3.4)

                                     0   0 0  1 0 1 00   0     .

Второйэтап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными.Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенныйразряд в дальнейшем обозначается как  x. Куб, участвовавший в операции склеивания, соответствующим образом помечается.Поскольку таких кубов мало, будем отмечать не участвовавшие в операциисклеивания кубы. В результатеполучаем комплекс K1-кубов,также упорядоченный по возрастанию количества единиц в разрядах:

/> /> /> /> /> /> /> /> <td/> /> <td/> /> />  

/>/>                                     0 0   0 x 0 0 x  x 1 1

                                     0 x   x 0 1 1 1  1 x 1

                K1  =            x 0    1 10 x 0  1 1 x                                          (1.3.5)

                                    0 0    0 0 x 0 0 0 0 0     .

Повторяемвышеописанную операцию для  комплекса    K1-кубов,после чего удаляем из полученного комплекса K2-кубов повторяющиеся:

/>/>/>/>/>/>                     0 0   x x xx                        0   x x

                     x x   x x 11                        x   x 1

      K2 =       x x   1 1 x x        =            x   1 x                                      (1.3.6)

                    0 0   0 0 00                       0   0 0   

Текубы, которые не участвовали в операциях склеивания, называются импликантами –это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицупокрытий K0-кубов. Импликанта считается покрывающей K0-куб, если они совпадают при  x, принимающем произвольное значение.

/>


               K0

 

      z

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

 

Импликанты

1001

+

/>

010x

+ +

/>

0xx0

+ + + +

/>

xx10

+ + + +

/>

x1x0

+ + + +

/>

Таблица 1.3.1 – Покрытия K0-кубов

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

Изтаблицы следует, что все импликанты являются экстремалями. Следовательно, онивсе войдут в запись функции в виде сокращённой ДНФ:

                      />.                      (1.3.7)

Комбинационная схема – это дискретное устройство,каждый из выходных сигналов которого в момент времени  tm  определяется так:

                               yj(tm)= ƒ ( x1(tm), x2(tm),…,xn(tm)),                       (1.3.8)

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

Приведём F1  к базису И – НЕ, а  F2 – к базису ИЛИ – НЕ:

/>  (1.3.9)

/>/>     .                  (1.3.10)

Получиввыражения для функций, приведённых к соответствующим базисам, можно нарисоватькомбинационные схемы, реализующие эти функции, на элементах одного вида: дляпервой функции это будут                И – НЕ-элементы, для второй – ИЛИ – НЕ :

/>

Рисунок 1.3.1 – Схема на И – НЕ-элементах

/>

Рисунок 1.3.2 – Схема на ИЛИ – НЕ-элементах

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

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

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

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

Конечный автомат задан своими уравнениями переходов ивыходов:

s(j+1) = [2∙s(j) + x(j) + B] mod 8 ,

 

y(j) = [ s(j) + x(j) + A] mod 2 ,

 

/> .

Требуется:

а)построить таблицы переходов, выходов и общую таблицу переходов автомата;

б) минимизировать автомат по числу состояний сиспользованием таблиц, полученных ранее;

в)построить граф минимизированного автомата и выписать для него матрицу переходов;

г)переходя ко двоичному представлению входа  X,  выхода  Y и состояния  S,  составить таблицу входов и выходов комбинационнойсхемы автомата и выполнить минимизацию булевых функций, соответствующих выходами состояниям автомата;

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

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

Конечнымавтоматом называется такое дискретное устройство, выходные сигналы которого вопределённые моменты времени зависят не только от последнего пришедшеговходного сигнала, но и от некоторого количества предыдущих его значений. 

Различаютсинхронные и асинхронные автоматы. У асинхронных смена выходных сигналов  y(tj)  может происходить только в моменты изменения входных  x(tj) , у синхронных – в моменты времени, определяемыедополнительным синхронизирующим сигналом  c(t).

Определиммножества, которым могут принадлежать входные и выходные сигналы (условимся обозначать  tj как  j):

/> – множетвавходных и выходных сигналов.

Тогдавыражения

                                        />                                   (2.2.1)

определяют входной и выходной алфавиты автомата.

Пусть  />. Тогдаесли  y(j) = λ(x(j)),  то этот автоматявляется, очевидно, комбинационной схемой.

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

                            />                                          (2.2.2)

Втом случае, если  Xи  S – конечныемножества, то и сам автомат называют конечным.

Ввиде уравнений любой конечный автомат можно записать разными способами. Однаиз  возможных форм записи:

                         />                                                  (2.2.3)

Записанныйтаким образом автомат называется автоматом Мили. Ясно, что это – болееинформативная форма записи по сравнению с автоматом Мура:

                       />/>                                                  (2.2.4)

Способызадания автоматов.

Во — первых, автоматможет быть задан непосредственно уравнениями вида (2.2.3) или (2.2.4).

Во — вторых,уравнения (2.2.3) и (2.2.4) могут быть представлены в табличной форме.Табличный аналог первого уравнения в (2.2.3) называется таблицей переходов,второго – таблицей выходов.

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

Графавтомата – это сигнальный граф, вершины которого обозначают состояния автомата,на дугах отражены условия перехода из состояния в состояние и значения выходныхсигналов в виде дроби: над косой чертой – x(j), подней – y(j).

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

Общееопределение конечного автомата:

 

                                             M = (X, Y, S, δ,λ),                                 (2.2.5)

где X – входной алфавит,  Y – выходнойалфавит,  S – множество состояний,  δ – функцияпереходов,  λ – функция выходов.

Пустьимеется два автомата: M  и  M’.

Еслидля любого  /> существует по крайней мереодно />, эквивалентное ему, тоговорят, что  M’  покрывает  MM’ ≥  M.

Еслиодновременно  M’ ≥  M  и  M  ≥  M’,  то  M ~ M’. Получаемэквивалентные автоматы. В этом случае невозможно различить  M  и  M’  по их реакции на входные сигналы.

Существуютдва основных положения определения понятия эквивалентности состояний:

а)состояния  si  и  sj  явно различны, если соответствующие им строки втаблице выходов разные;

б)состояния  si  и  sj  явно эквивалентны, если соответствующие им строки вобщей таблице переходов автомата одинаковы или становятся таковыми при замене  si  на  sj  или наоборот.

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

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

Построениетаблиц переходов, выходов и общей таблицы переходов и выходов на основезаданных уравнений автомата Мили очевидно:

/>     x(j)

s(j)

1

2

3

1

1

1

1

1

2

1

1

3

1

1

4

1

1

5

1

1

6

1

1

7

1

1

Таблица 2.3.1 – Таблица выходов автомата

/>     x(j)

s(j)

1

2

3

1

2

3

1

2

3

4

5

2

4

5

6

7

3

6

7

1

4

1

2

3

5

2

3

4

5

6

4

5

6

7

7

6

7

1

Таблица 2.3.2 – Таблица переходов автомата

/>     x(j)

s(j)

1

2

3

0/1

1/0

2/1

3/0

1

2/0

3/1

4/0

5/1

2

4/1

5/0

6/1

7/0

3

6/0

7/1

0/0

1/1

4

0/1

1/0

2/1

3/0

5

2/0

3/1

4/0

5/1

6

4/1

5/0

6/1

7/0

7

6/0

7/1

0/0

1/1

Таблица 2.3.3 – Общая таблица переходов и выходовавтомата

Перейдём непосредственно к минимизации полученногоавтомата по числу состояний. Для этого воспользуемся алгоритмом, известным влитературе как метод Гриса — Хопкрофта. Его достоинство в том, что он даётгарантированно минимальную форму автомата. Однако в общем случае он являетсядовольно трудоёмким и применяется, как правило, для автоматов с небольшимколичеством состояний. Он основан на свойстве транзитивности эквивалентности

                                  (si ~ sj)∩ (sj ~ sk) /> (si~ sk)                             (2.3.1)

Пара эквивалентных состояний переходит при всехвозможных значениях входа в пары также эквивалентных состояний.

Алгоритмсостоит из следующих шагов.

Сначаларазбиваем все состояния автомата на множества по признаку совпадения выходныхсигналов. В нашем случае получаем 2 множества:       S1 = {0, 2, 4, 6}  и  S2= {1, 3, 5, 7}.

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

пары

1

2

3

0;2

0;4

1;5

2;6

3;7

0;4

0;0

1;1

2;2

3;3

0;6

0;4

1;5

2;6

3;7

2;4

4;0

5;1

6;2

3;7

2;6

4;4

5;5

6;6

7;7

4;6

0;4

1;5

2;6

3;7

1;3

2;6

3;7

4;0

5;1

1;5

2;2

3;3

4;4

5;5

1;7

2;6

3;7

4;0

5;1

3;5

6;2

7;3

0;4

1;5

3;7

6;6

7;7

0;0

1;1

5;7

2;6

3;7

4;0

5;1

Таблица 2.3.4 – Таблица пар эквивалентных состояний

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

Следующим шагом оформляем общую таблицу переходов дляминимизированной формы автомата:

/>     x(j)

s(j)

1

2

3

0/1

1/0

0/1

1/0

1

0/0

1/1

0/0

1/1

Таблица 2.3.5 – Новая общая таблица переходов.

Наосновании полученной общей таблицы переходов и выходов можно нарисовать графминимизированного автомата с двумя состояниями:

 

/>           0/1U 2/1                              1/0 U 3/0                            1/1U 3/1

                                       0                           1

                                                        0/0U 2/0

  

Рисунок 2.3.1 – Граф минимизированного автомата

Дляпрактической реализации полученного автомата надо двоично закодировать всесигналы. Для кодировки  y  и  s  достаточноодного двоичного разряда,  x  требуетдвух –  x1  и  x2:

x

x1

x2

1

1

2

1

3

1

1

Таблица 2.3.6 – Двоичная кодировка  x

Составляемтаблицу истинности для комбинационной части схемы на основе таблицы (2.3.5).Получаем две функции трёх аргументов:

x1(j)

1

1

1

1

x2(j)

1

1

1

1

s(j)

1

1

1

1

y(j)

1

1

1

1

s(j+1)

1

1

1

1

Таблица 2.3.7 – Таблица истинности комбинационнойчасти

Каждуюиз функций  y(j)  и  s(j+1)  минимизируем с помощью карт Карно:

          y(j)                                                     s(j+1)           

                      x1(j)x2(j)                                                         x1(j)x2(j)

/>/>/>                 00  01    11  10                                               00  01    11   10

          0       1                   1                                         0           1      1   

   s(j)                                                                    s(j)

           1            1      1                                                 1           1      1

 

Рисунок 2.3.2 – Карты Карно для комбинационной части

Наосновании выбранных покрытий записываем минимизированные выражения для функцийпереходов и выходов:

                    />                      (2.3.2)

                                       />                                                (2.3.3)

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

/>

Рисунок 2.3.2 – Схема минимизированного автомата вбазисе И – ИЛИ – НЕ

2.3.4Выводы по разделу

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

3 Сети Петри

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

Длязаданной сети Петри, описывающей распределение ресурсов для случая двухпроцессов, сделать следующее:

а)выписать матричное уравнение смены маркировок;

б)построить дерево и граф покрываемости маркировок;

в)описать поведенческие свойства сети на основе графа покрываемости и матричныхуравнений;

г)выписать множество достижимых из  μ0  маркировок;

д)разработать программу моделирования сети Петри.

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

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

Определение. Сетью Петри называется четвёрка элементов

 

                                               C = (P,T, I ,O),                                     (3.2.1)

где

                                         P = { p1,p2,…,pn }, n > 0                             (3.2.2)

множествопозиций (конечное),

                                        T = { t1,t2,…,tm }, m > 0                                (3.2.3)

множествопереходов (конечное),

                                               I: T→ P                                                (3.2.4)

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

                                            O: T → P                                                (3.2.5)

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

Если  pi/> I (tj), то  pi – входная позиция j — го перехода, если  pi/>I (tj) , то  pi– выходная позиция  j — го перехода.

Для наглядного представления сетей Петрииспользуются графы.

Граф сети Петри есть двудольный ориентированныймультиграф

                                          G= (V,/>),                                                (3.2.6)

где  V = P U T,причём  P ∩ T = Ø.

Исходя из графического представления сети Петри, еёможно определить и так:

                                      C = (P, T, A),                                                (3.2.7)

где А – матрица инцидентности графа сети.

Определим понятие маркированной сети Петри – оноявляется ключевым для любой сети.

Маркировка  μ  сети Петри  C = (P, T, I, O)  есть функция:

                                   N = μ(P),  N /> N,                                            (3.2.8)

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

                                      μ= {μ1, μ2,…, μn} ,                                         (3.2.9)

 

где  n =│P │, а  μi/> N. Между этими определениями есть связь:

                                         μi = μ (pi)                                                   (3.2.10)

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

Таким образом, маркированная сеть Петри представляетсобой пятёрку элементов:

                                 M = (P, T, I, O, μ).                                             (3.2.11)

Пример простейшей сети Петри:

/>             p1

                  ▪▪▪

                                           t1                            p3

           p2     ▪

Рисунок 3.2.1 – Пример сети Петри

Правила работы с сетями Петри.

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

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

Проиллюстрируем сказанное на примере уженарисованной сети  Петри. Запустим в ней переход  t1– он является разрешённым:

 />              p1

                    ▪

                                          t1                             p3

                                                                     ▪

           p2     ▪

Рисунок 3.2.2 – Пример запуска перехода сети Петри

Пространство состояний и поведенческие свойствасетей Петри.

Пусть имеется маркированная сеть Петри:

                                               M = (P, T, I, O, μ)                                (3.2.12)

У неё  n  позиций. В каждой позиции не более  N  фишек. Тогдапространство сотояний есть множество всех возможных маркировок сети. Определим δ – функцию следующего состояния.

Если переход  tj разрешён при текущей маркировке  μ , то следующая маркировка  μ определится так:

                                               μ’ = δ (μ, tj)                                           (3.2.13)

Если переход  tj не разрешён, то  δ  не определена.

Пусть  {tj0, tj1,…,tjs} – последовательностьзапущенных переходов. Тогда ей будет соответствовать последовательность  {μ0, μ1,…,μs+1},то есть

                                           μk+1 = δ(μk, tjk)                                           (3.2.14)

На основании последнего равенства можно определитьпонятие непосредственно достижимой маркировки. Для сети C =(P, T, I ,O)     маркировка  μ’ называется непосредственно достижимой из  μ, если существует такойпереход  tj/> T, при котором

                                             μ' = δ(μ, tj)                                             (3.2.15)

Можно распространить это понятие на множестводостижимых из данной маркировок. Определим множество достижимых из  μ маркировок  R(C, μ)  следующим образом:

во — первых,  μ /> R(C,μ);

во — вторых, если  μ/> R(C, μ),   μ’ = δ(μ, tj)  и  μ’’ = δ(μ’,tk),  то и         μ’’ /> R(C,μ).

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

1    Достижимостьданной маркировки. Пусть имеется некоторая маркировка  μ,  отличнаяот начальной. Тогда возникает вопрос достижимости:можно ли путём запуска определённой поледовательности переходов перейти изначальной в заданную маркировку.

2    Ограниченность.Сеть Петри называется  k — ограниченной, если прилюбой маркировке количество фишек в любой из позиций не превышает  k. В частности, сеть называется безопасной, если  k  равно 1. Кроме того, сеть называется однородной, еслив ней отсутствуют петли и одинарной (простой), если в ней нет кратных дуг.

3    Активность.Сеть Петри называется активной, если независимо от дотигнутой из  μ0 маркировки существует последовательность запусков, приводящая к запускуэтого перехода.

Реальновводят понятия нескольких уровней активности для конкретных переходов. Переход tj/> T  называется:

а)пассивным (L0- активным), если он никогда неможет быть запущен;

б) L1- активным, если он может быть запущенпоследовательностью переходов из  μ0  хотя бы один раз;

в) L2- активным, если для любого числа  K существует последовательность запусков переходов из  μ0 ,при которой данный переход может сработать  K  иболее раз;

             г) L3-активным, если он является  L2- активным при  K → ∞.

4    Обратимость.Сеть Петри обратима, если для любой маркировки      μ /> R(C,μ0)  маркировка  μ0 достижима из  μ.

5    Покрываемость.Маркировка  μ  покрываема, если существует другая маркировка  μ’ /> R(C, μ0)  такая, что в каждой позиции μ’  фишек не меньше, чем в позициях маркировки  μ.

6    Устойчивость.Сеть Петри называется устойчивой, если для любых двух разрешённых переходовсрабатывание одного из них не приводит к запрещению срабатывания другого.

Существуют два основных метода анализа сетей Петри: матричные и основанные на построении дерева покрываемости.

Первая группа методов основана на матричномпредставлении маркировок и последовательностей запуска переходов. Для этогоопределим две матрицы размерности количество позиций /> количество переходов,связанные со структурой сети. Первая матрица называется матрицей входов:

                                     D– [i, j] = # (pi, I(tj)),                                   (3.2.16)

каждый её элемент равенчислу фишек, уходящих из  j — й позиции призапуске  i — го перехода. Вторая матрицаназывается матрицей выходов:

                                    D+[i, j] = # (pi, O(tj)),                                   (3.2.17)

каждый её элемент равенчислу фишек, приходящих в  j — ю позицию призапуске  i — го перехода. Определим единичныйвектор  e[j]  размерности  m, содержащий нули во всех позициях кроме той, котораясоответствует запускаемому в данный момент переходу. Очевидно, что переход разрешён,если  μ ≥ e[j]·D.Тогда результат запуска  j — го перехода можноописать так:

                                                  μ’ = μ + e[j]·D,                                          (3.2.18)

где  D= (D+D –)  –  матрица изменений. Тогда всесформулированные ранее проблемы сети Петри легко интерпретируются матричнымиуравнениями вида

                                                  μ = μ0+ σ·D,                                               (3.2.19)

где μ– исследуемая маркировка,  σ – вектор, компоненты которогопоказывают, сколько раз срабатывает каждый переход.

Хотя данный метод достаточно прост, он не лишённекоторых недостатков. А именно, его применение даёт лишьнеобходимые условия существования какого- либо свойства, иными словами, можетгарантировать лишь его отсутствие, а о присутствии мы сможем говорить суверенностью, только проанализировав дерево покрываемости (смены) маркировок.

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

Ясно, что этот метод хотя и требуетутомительного перебора всех возможных маркировок сети, но зато по уже готовомудереву достаточно легко анализировать проблемы достижимости, покрываемости,активности, обратимости сети.

Описав поведенческие свойства и методы анализа,можно перейти непосредственно к анализу конкретной сети Петри.

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

Исходная сеть в виде графа:

/>

                     p1                                                                p6

               ▪                                                                              ▪

                                                                                               

          t1                                        ▪    p4                            t4

                                                     

                                                     

         p2                                                                           p7

          t2                                        ▪    p5                           t5

                                                     

         p3                                                                           p8

              

              

         t3                                                                            t6

Рисунок 3.3.1 – Исходная сеть Петри

Для матричного анализа сети найдём её матрицуизменений.

                              />                                 (3.3.1)

                              />                               (3.3.2)

Матрицу изменений найдём как разность между (3.3.2)и (3.3.1):

                        />                      (3.3.3)

Таким образом, получив матрицу изменений, можнозаписать матричное уравнение смены маркировок вида (3.2.19). Вектор начальноймаркировки определим так:

                                        μ0= (10011100)                                          (3.3.4)

Составим дерево покрываемости маркировок сети.

                                              (10011100)‘Новая

/>


                                      t1                              t4    

              ‘Новая’                                                          ‘Новая

                        (01001100)                         (10010010)           

                      

             t2                           t4                         t1                       t5

                                                  

(00100100)              (01000010)            (01000010)         (10000001)

               ‘Новая’               ‘Тупик’           ‘Тупик’                              ‘Новая

       t3                                                                                       t6

 

(10011100)‘Старая’                                                    (10011100)‘Старая’ 

Рисунок 3.3.1 – Дерево покрываемости маркировок

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

Граф покрываемости сети выглядитследующим образом:

                                                 μ0

/>                 t3                                                                           t6

                                             10011100

     00100100         t1                                             t4          10000001

            t2                                                                                 t5

                     01001100                              10010010

                              

                               t4                                         t1

                                             01000010

Рисунок 3.3.2 – Граф покрываемости маркировок сетиПетри

Проанализируем сеть двумя методами – матричным играфическим и сравним полученные результаты.

Вопрос достижимости какой- либо маркировки легчевсего решается, глядя на граф покрываемости. Действительно, возьмём для примерадве маркировки:  μ1 = (01000010) и  μ2 = (00100010). Первая из них достижима, и возможныдва пути прихода к ней:  t1, t4 или  t4, t1 . Однако они неединственны, перед вторым запуском перехода возможно бесконечное число раз запуститьдля первого случая последовательность  t2, t3, для второго случая –  t5, t6. Вторая маркировка явно недостижима, так как её нет награфе.

С помощью матриц этот вопрос решается следующимобразом. Составляем уравнение вида (3.2.19), в котором вместо  σ ставим неизвестный вектор  x  той жеразмерности, а вместо  μ  –интересующую нас маркировку  μ1. В итоге получаемсистему из 8 уравнений относительно 6 неизвестных компонент вектора x.

                               />                                          (3.3.5)

Проанализировав данную систему, видим, что пятоеуравнение является следствием из третьего и шестого, шестое – из седьмого ивосьмого, первое – из второго и третьего. Из  (1)  и  (4)  следует, что  x5 = 0x6 = 0, из (7) следует, что  x4 = 1. Первыетри уравнения в  (3.3.5) являются линейно зависимыми, поэтому за свободноенеизвестное примем  x1. Тогдаполучаем решение в виде  x1 = {y y-1 y-1 1 0 0},где  y – любое целое число. Полученное решениеговорит о достижимости маркировки  μ1  и указывает,какие из переходов и сколько раз должны быть для этого запущены.

Сравнив оба способа решения, сразу можно увидетьнедостатки второго. Во- первых, решение  (3.3.5)  не указывает, в какой именнопоследовательности должны быть запущены указанные переходы.               Во-вторых, глядя на матрицу изменений, мы не можем судить о наличии в сети петель.Кроме того, полученное матричное решение не даёт, вообще говоря, гарантий своейреализуемости – оно является лишь необходимым условием достижимости. Однако, неполучив решения, можно говорить о недостижимости маркировки.

Действительно, записав  (3.2.19)  для  μ2,получаем систему:

                              />                                           (3.3.6)

Система является несовместной, так как послевычитания третьего уравнения из шестого получаем уравнение, противоречащеепятому. Поэтому можно сделать вывод о недостижимости  μ2,совпадающий с полученным из графа покрываемости маркировок.

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

Данная сеть является активной – вней каждый переход может сработать хотя бы один раз. Проанализируем уровниактивности отдельных переходов. Переходы  t1  и  t4  являются  L1 — активными, так как они в худшем случае (то есть приполучения тупиковой маркировки) могут сработать хотя бы один раз. Переходы  t2, t3, t5и t6  являются  L2 — активными, так как они могут сработать любое наперёдзаданное число раз и даже больше.

Отсюда можно сделать вывод о том, что данная сеть неявляется бесконфликтной – у неё есть тупиковое состояние.

Можно также сказать, что сеть является обратимой.Этот вывод можно получить и матричным путём – решив уравнение

                                          D= 0                                                        (3.3.7)

Получаем систему

                              />                                           (3.3.8)

Данная система имеет 2 решения:  {y y y 0 0 0}  и  {0 0 0 y y y},  где  y – любое. Действительно, запуская любоечисло раз последовательности  t1 t2 t3 или t4 t5 t6,каждый раз мы возвращаемся к исходной маркировке.

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

Можно сказать, что данная сеть не являетсяустойчивой. У неё есть тупик, и, кроме того, непосредственно перед  переходом втупиковое состояние всегда существуют два разрешённых перехода. Запуская ‘неправильный’ переход, мы запрещаем оба – и оказываемся в тупике.Такое свойство сети говорит о наличии потенциально возможных конфликтов.

Па основании графа  (3.3.2)  можновыписать множество достижимых из  μ0  маркировок: 

                        

                             />                                               (3.3.9)

Для моделирования сети быланаписана программа на языке Turbo Pascal. Она отображаетсостояние сети и разрешённые в каждый момент переходы. Для выбора запускаемогоперехода используется мышь.

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

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

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

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

2   Г.Корн, Т.Корн  Справочник по математике для научных работников иинженеров.– М.: Наука, 1984. –831 с.

3   В.Брауэр Введение в теорию конечных автоматов.–М.: Радио и связь, 1987. –392 с.

4   Фаронов В.В. Турбо Паскаль 7.0: практика программирования.– М.: Нолидж, 1997. –432 с.

Приложение А

Программа моделирования сети Петри

Program Farewell_Pascal_Please_Forgive_Me;

Uses graph,crt;

Const m_0=$9C;

      r_0=$90;

     path='cursor.dat';

 mask:array[0..5] of byte = ($90,$48,$20,$0C,$12,$01);

 jump:array[0..5] of word =($406F,$20B7,$98DF,$02F3,$01ED,$1CFE);

Var

  i,j,counter,number:integer;

  flag_of_exit:boolean;

  ok:word;

  bm:integer;

  ScrMask:array[1..64] of byte;

  r,m,old_m,old_r:byte;

  f:file of byte;

  procedure Init_Graph_Mode;

  var

    Driver,

    Mode,

    ErrCode: Integer;

  begin

   Driver := Detect;

   InitGraph(Driver, Mode, '');

   ErrCode := GraphResult;

   if ErrCode <> grOk then

   begin

     Writeln('Ошибка графического режима:',

                                    GraphErrorMSG(ErrCode));

     Halt(1);

  end;

  SetTextStyle(DefaultFont, HorizDir, 1);

  SetColor(15);

  SetLineStyle(0,0,1);

  SetFillStyle(1,0)

  end;

  function Init_Mouse:word;

  begin

    asm

      push ax

      mov ax,00h

      int 33h

      mov @Result,ax

      pop ax

    end

  end;

  procedure Show_Mouse;

  begin

    asm

      push ax

      mov ax,01h

      int 33h

      pop ax

    end

  end;

  procedure Hide_Mouse;

  begin

    asm

      push ax

      mov ax,02h

      int 33h

      pop ax

    end

  end;

  procedure Set_Graph_Cursor(segm,ofst:word;x,y:integer);

  begin

    asm

      push ax

      push bx

      push cx

      push dx

      mov bx,x

      mov cx,y

      mov es,segm

      mov dx,ofst

      mov ax,09h

      int 33h

      pop dx

      pop cx

      pop bx

      pop ax

    end

  end;

  procedure Get_Mouse_State(var bt,x,y:integer);

  begin

    asm

      push ax

      push bx

      push cx

      push dx

      mov ax,03h

      int 33h

      lds di,bt

      mov [di],bx

      lds di,x

      mov [di],cx

      lds di,y

      mov [di],dx

      pop dx

      pop cx

      pop bx

      pop ax

    end

  end;

  procedure Get_Web_State;

  begin

    r := 0;

    for counter:= 0 to 5 do

      if (mask[counter] and m) = mask[counter] then

        r := r or ($80 shr counter)

  end;

  procedure Design_Kernel;

  begin

    OutTextXY(190,20,'Распределение ресурсов для');

    OutTextXY(207,27,'случая двух процессов');

    for counter := 0 to 2 do

      Circle(150,counter*150+50,15);

    for counter := 0 to 2 do

      Circle(450,counter*150+50,15);

    for counter := 0 to 1 do

      Circle(300,counter*150+120,15);

    for counter := 0 to 2 do

      begin

        Line(140,counter*150+123,160,counter*150+123);

        Line(140,counter*150+127,160,counter*150+127);

        Line(140,counter*150+123,140,counter*150+127);

        Line(160,counter*150+123,160,counter*150+127)

      end;

    for counter := 0 to 2 do

      begin

        Line(440,counter*150+123,460,counter*150+123);

        Line(440,counter*150+127,460,counter*150+127);

        Line(440,counter*150+123,440,counter*150+127);

        Line(460,counter*150+123,460,counter*150+127)

      end;

    for counter := 0 to 1 do

      begin

        Line(counter*300+150,65,counter*300+150,123);

        Line(counter*300+150,127,counter*300+150,185);

        Line(counter*300+150,215,counter*300+150,273);

        Line(counter*300+150,277,counter*300+150,335);

        Line(counter*300+150,365,counter*300+150,423);

        Line(counter*300+150,123,counter*300+148,114);

        Line(counter*300+150,123,counter*300+152,114);

        Line(counter*300+150,185,counter*300+148,176);

        Line(counter*300+150,185,counter*300+152,176);

        Line(counter*300+150,273,counter*300+148,264);

        Line(counter*300+150,273,counter*300+152,264);

        Line(counter*300+150,335,counter*300+148,326);

        Line(counter*300+150,335,counter*300+152,326);

        Line(counter*300+150,423,counter*300+148,414);

        Line(counter*300+150,423,counter*300+152,414)

      end;

    Arc(120,427,180,360,25);Arc(480,427,180,360,25);

    Arc(122,35,0,180,27);Arc(478,35,0,180,27);

    Line(95,35,95,425);Line(505,35,505,425);

    Line(293,134,163,431);Arc(159,427,180,330,5);

    Line(290,281,170,436);Arc(162,427,180,320,12);

    Line(307,134,436,431);Arc(440,427,210,360,5);

    Line(310,281,429,436);Arc(438,427,220,360,12);

    Line(283,117,169,106);Arc(171,121,80,180,15);

    Line(312,129,439,262);Arc(429,273,0,45,15);

    Line(283,267,169,256);Arc(171,271,80,180,15);

    Line(311,257,426,110);Arc(432,121,0,160,12);

    Line(150,35,145,26);Line(150,35,150,26);

    Line(450,35,455,26);Line(450,35,450,26);

    Line(155,123,156,114);Line(155,123,159,115);

    Line(155,273,156,264);Line(155,273,159,265);

    Line(445,123,444,114);Line(445,123,440,115);

    Line(445,123,444,114);Line(445,123,441,116);

    Line(445,273,444,264);Line(445,273,440,265);

    Line(293,135,287,142);Line(293,135,291,143);

    Line(307,135,309,143);Line(307,135,312,142);

    Line(290,282,282,288);Line(290,282,285,290);

    Line(311,282,315,290);Line(311,282,317,288);

    SetFillStyle(1,8);

    for counter := 0 to 1 do

      begin

        Line(540,counter*70+150,600,counter*70+150);

        Line(540,counter*70+170,600,counter*70+170);

        Line(600,counter*70+150,600,counter*70+170);

        Line(540,counter*70+150,540,counter*70+170);

        FloodFill(570,counter*70+160,15)

      end;

    SetFillStyle(1,15);

    OutTextXY(543,159,'Restore');

    OutTextXY(555,229,'Exit');

  end;

  procedure Design_Mark_and_Jumps;

  begin

      SetColor(15);

      SetLineStyle(0,0,3);

      SetFillStyle(1,15);

      Hide_Mouse;

      for counter := 0 to 2 do

        if ((m shr (7 — counter)) and 1) = 1 then

          begin

            SetColor(15);

            SetFillStyle(1,15);

            FillEllipse(150,counter*150+50,1,1)

          end

          else

          begin

            SetColor(0);

            SetFillStyle(1,0);

            FillEllipse(150,counter*150+50,1,1)

          end;

      for counter := 3 to 4 do

        if ((m shr (7 — counter)) and 1) = 1 then

          begin

            SetColor(15);

            SetFillStyle(1,15);

            FillEllipse(300,(counter-3)*150+120,1,1)

          end

          else

          begin

            SetColor(0);

            SetFillStyle(1,0);

            FillEllipse(300,(counter-3)*150+120,1,1)

          end;

      for counter := 5 to 7 do

        if ((m shr (7 — counter)) and 1) = 1 then

          begin

            SetColor(15);

            SetFillStyle(1,15);

            FillEllipse(450,(counter-5)*150+50,1,1)

          end

          else

          begin

            SetColor(0);

            SetFillStyle(1,0);

            FillEllipse(450,(counter-5)*150+50,1,1)

          end;

      for counter := 0 to 2 do

        if ((r shr (7 — counter)) and 1) = 1 then

          begin

            SetFillStyle(1,10);

            FloodFill(150,counter*150+125,15)

          end

          else

          begin

            SetFillStyle(1,12);

            FloodFill(150,counter*150+125,15)

          end;

      for counter := 3 to 5 do

        if ((r shr (7 — counter)) and 1) = 1 then

          begin

            SetFillStyle(1,10);

            FloodFill(450,(counter-3)*150+125,15)

          end

          else

          begin

            SetFillStyle(1,12);

            FloodFill(450,(counter-3)*150+125,15)

          end;

      SetColor(15);

      SetFillStyle(1,15);

      Show_Mouse

  end;

  Begin

    Init_Graph_Mode;

    ok := Init_Mouse;

    flag_of_exit := false;

    m := m_0;

    r := r_0;

    old_m := 0;

    old_r := 0;

    if ok = $FFFF then

      begin

{$I-}   assign(f,path);

        reset(f);

        ok := filesize(f);

{$I+}   if (IOResult = 0) and (ok = 64) then

          begin

            for i := 0 to 63 do

              read(f,ScrMask[i]);

           Set_Graph_Cursor(seg(ScrMask),ofs(ScrMask),2,2)

          end;

        Design_Kernel;

        Show_Mouse;

        repeat

          Get_Mouse_State(bm,i,j);

          if (m <> old_m) or (r <> old_r) then

            begin

              Get_Web_State;

              Design_Mark_and_Jumps;

              old_m := m;

              old_r := r

            end;

          if bm = 1 then

          begin

            number := 6;

            for counter := 0 to 2 do

              if (i < 165) and (i > 135) and

                 (j < counter*150+130) and (j >counter*150+120)

              then

                number := counter;

            for counter := 3 to 5 do

              if (i < 465) and (i > 435) and

                 (j < (counter-3)*150+130) and (j >(counter-3)*150+120)

              then

                number := counter;

            if (number < 6) and (((1 shl (7-number))and r) <> 0) then

              begin

                m := m and (jump[number] and $FF);

                m := m or (jump[number] shr 8)

              end;

            if (i < 600) and (i > 540) and (j <170) and (j > 150)

              then

                m := m_0;

            if (i < 600) and (i > 540) and (j <240) and (j > 220)

              then

                flag_of_exit := true

          end;

        until flag_of_exit;

        Hide_Mouse;

        CloseGraph

      end

      else

        begin

          CloseGraph;

          WriteLn('Ошибка мыши: Device or driver notfound.')

        end

  End.

еще рефераты
Еще работы по информатике, программированию