Книжка по сетям Петри, страница 4

Х А„- декартово произведение множеств А,,..., А„; л"-дх...хд, эг. й( — множество всех натуральных чисел (включая 0(; Ч,Л, Ь ~ — логические операции дизъюнкции, конъюнкции, отрицания и имппикации: А  — А истинно тогда и только тогда, когда истинно В; 3, ч — кванторы существования и всеобщности (например,ч хб Х,Зу Е Е У: А (х, у! — для любого х, принадлвкащего Х, существует у, принадлежащее У, такое, что истинно условие А (х, у) 1. Пусть Х, У вЂ” множества, ЯЕХХ Х вЂ” бинарное отношение на Х, и х, уСХ. хЯу-х и у находятся в отношении Я; Я ' — обращение отношения Я, т.е. уЯ 'х, если и только если хЯу; Я -дополнение отношения Я, т.е.

Я (ХХ Х(М: ге Я ч 8 — суперпозиция отношений Я и 8, т.е. Я ч 8 = ( (х, у) ( Эг Е Х: кЯг Л э8у ); Я" =Я ... Д, п>2; Я' О Я", где и Е (4, — транзитивное замыкание отношения Я. п=е Для функции Ф запись Ф: х. У указывает область определения функ- ции Х и область ее значений У. Конечное множество символов А ( е, Ь,..., с ) образует алфавит. Сло- вом в алфавите А называется некоторая последовательность выписанных подряд символов иэ алфавита А (например, еЬЬесЬ).

Конкатенэпиейдвух слов и и () в алфавите А называется слово аб, т.е. слово, полученное выписыванием подряд слов а и б (слова а и () являются в этом случае подсловами слова а()). Через А обозначим множество всех слов в алфа- вите А, через х — пустое слово, т.е. слово, не содержащее ни одного сим- вола. Через е" и а", где а — символ, и — слово или подспово, обознача- ют слова (подслове) м... е и ж...а. Если слово представляет собой конкатенацию ()у, то В называют префиксом, а у — суффиксом слова ()т, Если А и  — алфавиты такие, что А 2В, то слово () в алфавите В, полу- ченное вычеркиванием изслова а в алфавите А всех символов нз А ! В, будем называть проекцией слова а в алфавите А не алфавит В.

Через Э( = Э( !.! (ы) обозначим расширенное множество натуральных чисел, где ы — элемент, удовлетворяющий для любого и Е й( следующим свойствам: 1) ш)л, 2)п+ы ы+и ы+ы ы — и ы — ш=ш, 3)ы ° л=п ы=ы, 4) О ы =ш.О=О. Пусть К" (Д,,..., Мг), Ь ((ы..., (г) Е М" — векторы иэ г чисел. Ариф- метические операции распространим на векторы, считая их покомпонентны- ми операциями.

Например, К+(. (д, +1,,..., хг+(г).Отношения же пе- реопределим для векторов как глобальные отношения, с использованием кванторов существования и всеобщности. Например, истина,еслиуб 1<(<г: Э!<(л (К<(.) = лоэю в противном случае, ~ истина,еспи ЮЬ 1</(г: йт=(ь (К () = ~ лола в противном случае, истине,если (У>'. 1 К~(<г: Гг~<(!) Л(йг, 1 <)<г: юг!<1;), (К<(.) = ложь в противном случае. Сетью будем называть тройку (Р, Т, Е) где Р— непустое множество элементов сети, называемых эмсгеэш, Т вЂ” непустое множество элементов сети, называемых переходами, Е ь, Р Х Т () Т Х Р вЂ” отношение инпиденгносги. и для (Р, Т, Е) выгонке. ны следующие условия: А1) Р Г! Т = р (множества мест и переходов не пересекаются); А2) (ЕФф) Л (чх Е Р()Т, Зук РОТ: хЕУЧУЕх) (т.е. любой элемент сати инцидентен хотя бы одному элементу'другого типа); !5 АЗ! если для произвольного элементе сети к Е Х обозначить через 'х множество его входных элементов (у ( уЕх), з через к' — множество его выводных зяеиекгое (у ! хЕу), то ур~ рт ЕР: (р1 "рз)Л(Р1 Рз)'ч(Р1 Рд! (т.е.

сеть не содержит пары мест, которые инцидентны одному и тому же множзству переходов) . Графическим предстеапением сати служит двудольный ориентированный граФ (в общем случае бесконечный) с двумя типами вершин; аершиныместе изображаются кружочками, вершины-переходы — барьерами (з твкже прямоугопьникеми или квадратами, если переходы являются неэлементарными объектами, см. главу 6) . Из вершины х в вершину у ведет дуга, если и только если хЕу.

Не основе понятия сети, которзя описывает только статическую тополо. гию моделируемого процесса ипи системы, вводятся динзмические сетевые структуры, в которых местам приписывеются специальные разметки, моделирующие выполнение условия, и с сетью связывается понятие ее функционировения, изменяющего зти разметки (условия) в результате тек называемых срэбегывекид лереходое. К таким динамическим се~ям относятся сети Петри, их различные варианты, обобщения и частные случаи. Сеть Гйгри — это набор )У = (Р, Т, Е, ИГ, Ме), где (Р, Т, Е) — конечнзя сеть (множествоХ ° РОТ конечно),з ИГ: Е - эТ1(О) иМе. Р.

й) — две функции, называемые соответственно крэгкосгью дуг и кзчепькод Резмегкод. Переел сопостевпяет каждой дуге число л > О (кретность дуги) . Если л > 1, то в графическом представлении сети число л выписывается рядом с короткой чертой, пересекающей дугу. Часто текля дуга будет также заменяться пучком из л дуг, соединяющих соответствующие элементы сети. Условия(ся никак не отмечать кратность дуг, равную 1. Такую сеть будем называть ордикернод (см. % 4.1). Вторая функция сопостевляет кеждому месту р Е Р некоторое число Ме Ог) Е З) (рззметкз месте) .

В граФическом прм(стзвлении сети разметка месте р изображается помещением в верши. ну кружок числа Ме (о) или, если зто число невелико, соответствующего числа точек (фишек) . Функционирование сети Петри описывается формально с помощью множестве последовательностей сребзтывений и множестве достижимых в сети резметок. Эти понятия определяются через правиле срабатывания перехо. дов сети. Разметка сети )У вЂ” это функция М: Р .й. Если предположить, что все месте сети Мстрого упорядочены кзкимлибо образом, те.Р = (Р, ...,Р„), то резметку М сети (в том числе начальную разметку) можно вздеть кзк вектор чисел М = (т„..., т„) тзкой,.что для любого г', 1 <г' Сл, глг = = м (Рг ! .

если Р' ( Рг,..., Рг ) — подмножество мест из Р, то условимся через М(Р ) обозначать множество резметок (М(РА ), ...,М(ог„)). Если Р предстевить кек вектор Р = (Рг,...,Р;„), то М(Р ! обознечеет вектор из множества й)", незывземый проекцией разметки М нз Р. Не основе отношения инцидентности Е и функции крзтности дуг ИГ можно ввести бгункцию инцидекгносги Е: Р Х Т О Т Х Р - е), которая определяется кек л, если хЕуЛ(гУ(х,у) =л), Е(к, у) = О, если И(хЕУ) .

Если мщта сети упорядочены, то можно каждому переходу С сопоставить двацелочисленныхвектора Р(г) и Р'(г)длинойл,гдеп )Рр 'РЯ (Ь,,..., Ь„), гда Ь~ Р(рэ Г). Р'Я = (Ьы,...Ь„), где Ьг Р11,рг) . Переход г может сработать при некоторой разметке М сати )У, если 'со Е Г: М (р) > Р (р, г), т.е. каждое входное место р перехода с имеет разметку, не меньшую, чем кратность дуги; соединяющей р и Г.

Это условие можно переписать в векторной форме следующим образом: М> У(т) . Для ординарной сети Петри условие срабатывания перехода означает, что любое входное место этого перехода содержит хотя бы одну фишку, т.е. имеет ненулевую разметку. Срабатывание перехода с при разметке М порождает разметку М по следующему правилу: ДЮРЕР: М'(р) М(р) — Р(р, г) + Р(г,р), т.е.

М' =М вЂ” 'Р(т) + Р (т). Таким образом, срабатывание перехода с изменяет разметку так, что разметка каждого его входного места р уменьшается на Р(р, т), т.е. на кратность дуги, соединяющей р и т, а-разметка каждого его выходного места увеличивается на Р (т, р), т.е. на кратность дуги, соединяющей т и р. На множестве разметок можно ввести отношение [ ) непосредственного следования разметок: м[)м' Чтет: (м>'Р(г))л(м' м — 'РЯ+Р (г)). Будем использовать уточняющее обозначение М[т) М, если М непосредственно следует после М в результате срабатывания перехода с.

Говорят, что разметка М достижима от разметки М, если существует последовательность раэметок М, М„М„..., М и слово т г,тэ ... тэ в алфавите Т такие, что М[11 )М1[т1)Мэ .. [Гэ)М. Слово т в этом случае называется последовательностью срабатываний, ведущих от М к М'. Обобщим отношения непосредственного следования до отношения "М досгиэгимэ ог М", используя обозначение М[) М или М[т) М, если уточняется последовательность срабатываний.

(Последовательность т может быть пустой, т.е. М достижима от М.) Множество [М ( И[) М ) разметок, достижимых в сети )Уст разметки М, обозначим через Я (В М) . Множество Я ()У) = Я ()У, Ма ), т.е. множество всех разметок, достижимых в )у от начальной разметки Ма, называют мноэгэсгеом досгиэгпмых раэмэгок сети )У.

(Заметим, что М Е Я(И, М) и Ме Е Я(Д().) Множеством последовательностей срабэгывапид сети И, или свободным языком сети д( называется множество Е(й) =[тЕТ [ИМЕЯ()У): Ме[т)М',, т.е. множество всех последовательностей срабатываний, ведущих от Ма к каждой достижиьюй в )у разметке. На рис. 1.3 изображена сеть Петри, на примере которой поясним данные выше определения. В этой сети Р (р,, рт,р,), Т (Г,. Гт, Гз, Гч).Функ- 17 ция инцидентности Р задается с помощью следующих двух таблнц, в которых на пересечении строки х и столбца у стоит число Е (х, у): г, г, г, г, л, с, г, Рр г~ Рз с, Начальная разметка Ме задается следующим образом: Ме(р[) = 1, М,(р,) =2, Ме(рз) "0 или, в векторной форме: Ме " [1, 2,0).

При разметке Ме могут сработать переходы Г~ и Гз, так как Ме" = (1,2,0) > 'Р [1,) (1, О, 0), Ме ~ Т [гт) (1,2,0!. ПеРехсды Гз итч не могут сработать, так как Ме яг'Я[ге) = (0,0, 1),Ме Ф'г(гч) (О, О, 1). В результате срабатывания перехода г, разметка Мс сменяется на разметку (1, 3, 0), а в результате срабатывания перехода гт разметка Ме сменяется на разметку (О, О, 1) . Обе новые разметки непосредственно следуют после Ме в рассматриваемой сети. Можно представить возможные изменения разметок сети )У, происходящие в результате срабатывания ее переходов, в виде графе размегок — ориентированного графа, множество вершин которого образовано множеством Я(Л)) достижимых в )У разметок. Из вершины М в вершину М ведет дуга, помеченная символом перехода г, если и только если М [г ) М . На рнс.

1.4 показан начальный фрагмент графа разметок сети на рис. 1З. Этот граф бесконечен, так как множество Я (Дб достижимых разметок бесконечно для рассматриваеыой сети. Разметка М Е Я (йб называется туликовой, если в сети д) не существует ни одного перехода, который может сработать при этой разметке. Для рассматриваемой сети тупиковыми являются разметки [0,2,0), (0,3,0), (0,4,0),..., (О,л,О), ... Легко видеть, что если выделить путь по дугам графа разметок, начинающийся в вершине М и ааканчивающийся в вершине М, и выпи. сеть подряд все встречаю. щиеся символы переходов, то полученное слово образует последовательность срабатываний, ведущих от М к М ~.