Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 3

Кроме того, среди первых публикаций важную роль играет работа Хольта и Коммоиера «События и условия» [1271. Петри представил небольшую статью на конгресс ИФИП, которая опубликована в трудах конгресса [2421. Она основана на идеях, изложенных в диссертации.

Представленный в книге подход во многом основан на работе группы вычислительных структур МТИ и работах Денниса [721, Патила [2311 и др., кончая работой Хзка [1131. На содержание книги также оказал влияние Келлер — своим отчетом по системам замещения векторов [1Щ и своей точкой зрения на моделирование [1521. 4.7. Темы дпп дальнейшего изучения 1. Проследите истоки и направления важных идей теории сетей Петри. Очевидно, что исходная точка принадлежит Петри, но как и к кому направлялись идеи дальше, как они появились в Соединенных Штатах? Куда они направились оттуда? Для определения предшествования используйте даты и ссылки из опубликованных отчетов, статей, диссертаций и меморандумов.

Возможно, вам захочется проинтервьюировать некоторых «ключевых» людей: Петри, Хольта, Денниса, Патила и др. ГЛАВА 2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ В этой главе мы дадим формальные определения основных понятий сетей Петри. Основные понятия используются на протяжении всей книги и являготся необходимыми для правильного понимания. Наш формализм основывается на теории комклеклюв, являющейся обобщением теории множеств. Если вы не знакомы близко створней комплектов. предлагаем вам прочитать приложение. Определения, данныи здесь, по стилю подобны определениям теории автоматов 11301, т.

е. определен новый класс машин — автоматная сеть Петри. Как мы уанднм позднее (гл. 5-8), такая точка зрения может привести к некоторым интересным результатам в теории формальных языков и теории автоматов. 2.т. Структура сети Петри Сеть Петри состоит из четырех элементов: множество позиг(ий Р, множество переходов Т, входная функция ! и выходнал функция О. Входная и выходная функции связаны с переходами и позициями. Входная функция ! отображает переход Г! в множество позиций !(Г!), называемых входными позициями перехода. Выходная функция О отображает переход !! в множество позиций О(!!), называемых выходными позициями перехода.

Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями. Определение 2.1. Сеть Петри С является четверкой, С = (Р, Т, !, О!. Р = (р„р„..., р„) — конечное множество позиции и ъ О. Т = (Гь Г,, ..., ! ) — конечное множество переходов, и - О. Множество позиций и множество переходов не пересекаются, Р О Т = = И. Г: Т-+ Р' является входной функцией — отображением из переходов в комплекты позиций. О: Т-+- Р есть выходная функция — отображение из переходов в комплекты позиций.

Мощность множества Р есть число п, а мощность множества Т есть число гп. Произвольный элемент Р обозначается символом ри г' = 1, ..., и, а произвольный элемент Т вЂ” символом Гп ! = Примеры сетей Петри даны на рис. 2.1 — 2.3. Позиция р, является входной позицией перехода !! в том случае, если р, Е ! (!!); р; является выходной позициеи, если р, е О (!!).

Входы н выходы переходов представляют собой комплекты позиций. Комплекгп является обобщением множества, в которое вклю- е 1Е Глава 2 Определение 2.2. Определим расширенную входную функцию Х и выходную функпню 1: Р-+. Т, О: Р— 1- Т таким образом, что З) (1Р 1(р,)) = З( (р„о (11)), ~ф (1л О.(р1)) - фр (рм 1(Ч). Для сети Петри на рис. 2.1 расширеняыми входной и выходной функциями являются: 1(р1) =( ). 1(рз) = (1 ° 11).

1 (Рз) = (111 11Ь 1(рз) = (11)з Г (Рз) = (11 11) О(рх) = (111. О (рз) = (1з). О (рз) (111 131 О(рз) = (11), О (р,) = (1,). С=(Р, Т, 1, О» ° Р = (Рх. Рз, Рзъ Раз 1Ъ» ° Т=(1„11, 111 1з»1 1 (11) = (Р1» ° О(1» =-(Р, Рз, Р», 1 (11» = (пз, рз рх» О (1» (Рб» 1(11» = (рз». О(11» =(Ра» ° 1 (1з) = (рз» 0(1з» = (Рз. Рз» ° Рис. 2Л. Структура сети Петри представлена в виде четверки„иоторая состоит ив множества позиций (Р», множества переходов Щ, входной функции 11 Т-и Р И ВЫХОдНОй фуИКцян (СС Т- Р ».

чены многократно повторяющиеся элементы — тиражированные элементы. В приложении содержится описание теории комплектов. Использование комплектов, а не множеств для входов и выходов перехода позволяет позиции быть кратным входом либо кратным выходом перехода. Кратлнослзь входной позиции рз для перехода 4. 1 есть число появлений позиции во входном комплекте перехода, (р,, Г (11)). Аналогично кратность выходной позиции р, для перехода 11 есть число появлений позиции в выходном комплекте перехода, $~(рз, О (11)). Если входная и выходная функции являются множествами (а не комплектами), то крапюсть каждой позиции есть либо О, либо 1.

Входные и выходные функции используются для отображения позиций в комплекты переходов, а также их можно использовать для отображения переходов в комплекты позиций. Определим, что переход 11 является входом позиции р,, если р1 есть выход Переход 11 есть выход позиции р„если р,- есть вход Основные определения С=(Р, т, л, 0), (Рз Рз Рз Ре Рв Ре) т= (тз, )з, (з, гз, 14. 1в), )(1) =(Рв).

0(г ) = (Р ° рз). У(тз) = (Ра). О(1.) =(Рз, Рв, Р.), 1(зз) =(Р, Р ), 0(гз) = (Р, Ре). ) (г,) = (Р,, ЄЄР,), о (4) = (Р,), Г(1») = (Рз), О(тв) = (Ре). Рис. 2.2. Структура сети Петри. с=(Р, т, 1, о), (Рв ~ Рз Рз Ре РБ Ре Р» Рв Рв) т = (1„г„г„з„г„г,), 1(1) = (Рв). О(й) =(Р.. Рз). )(1.) =( ). О(1) =(Р~, Р»). ) (гз) = (Р Рв) 0 (зз) = (Ре) ) ((е) = (Рз) ° О (ге) = (Ре). У (Ч = (Ре. Рт) 0(г,) = (р,), в (ге) = (Ре, Рв)» 0(ге) = (Рев Рв).

Рис. 2.3. Структура сети Петри. Упражнения. 1. Найдите расширенную входную и выходную функции сетей Петри (рис. 2.2 и 2.3). 2. Покажите, что входная н выходная функции одновременно не являются необходимыми и что сеть Петри может быть определена множествами позиций, переходов и расширенной входной (или выходной) функцией. Для этого покажите, как расширенная выходная функция может быть определена иэ расширенной входной функции н наоборот. 2.2. Графьз сетей Петри В значительной степени теоретическая работа по сетям Петри основана на формальном определении сетей Петри, изложенном Выше.

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

Кружок С) является позицией, а планка ! — переходом. зз з а д и и и р а и и и политехнический институт "овромсниа цивлиал Ь1с,п1ле тг.втД 1В Глава 2 Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие — от переходов к позициям. Дуга, направленная от позиции р; к переходу 1~, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход.

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

Определение 2.3. Граф 6 сети Петри есть двудольный ориентированный мультнграф, 6 = (У, А), где Ь' = (и,, и~, ..., и,)— множество вершин, а А = (аь а2, ..., а,) — комплект направленных дуг, а~ = (ип оь), где от, оь Е 1'. Множество 1' может быть разбито на два непересекающихся подмножества Р и Т, таких, что У = Р1) Т, Р П Т= Я, и для любой направленной дуги а; Е А, если а~ — — (от, о„), тогда либо и;~ Р и п„Е Т, либо п~ Е Т а пь с Р. Графы сети Петри, изображенные на рис. 2.4 — 2.6, эквивалентны структурам сети Петри на рис.

2.1 — 2.3. Для демонстрации эквивалентности этих двух представлений сети Петри — структуры сети Петри и графа сети Петри — покажем, каким образом можно преобразовать один в другой. Предположим, нам дана структура сети Петри С = (Р, Т, 7, О) с Р = = (р„р2, ..., р„) и Т = (1„1в, ..., 1 ). Тогда граф сети Петри можно определить следующим образом. Определение 2.4. Определим 1Г = Р 11 Т. Определим А как комплект направленных дуг, такой, что для всех р; ~ Р и 1~ Е Т Ф ((р„1;), А) = 4Ф (р;, У (~~)), ~ ((г;, р;), А) = Ф (рь 0 (г;)).

6 = (1', А) есть граф сети Петри, эквивалентный структуре сети Петри С= (Р, Т, У, О). Обратное преобразование (от графа сети Петри к структуре) осуществляется подобным образом, и поэтому оставим более детальное описание такого преобразования читателю. Однако прн перехо- Основные онреоеления Рг Рг рис, 2.4. Граф сети Петри, эквивалентный структуре, показанной на рис. 2.1.

Рг Ра рнс. 2.5„Граф сети Петри, эквивалентный структуре, изоораженной на Рис. 2*2„ Фа ра Рис. 2.6. Граф сети Петри, эквивалентный структуре, показанной на рис. 2.3. де от графа сети Петри к структуре сети Петри возникает одна интересная задача: если множество вершин можно разделить на два подмножества Б и Я, то какое из этих подмножеств должно быть позициями, а какое — переходами? Оба возможных варианта позволяют определить сеть Петри, хотя в получающихся в результате структурах позиции и переходы меняются местами.