Книжка по сетям Петри (547616), страница 29
Текст из файла (страница 29)
т,~,... т* й Теорема 7.4. В З.беги любое 1«сечение и любое Ычлчембе пера- Е д т«бз санаюген не более чем по одному элементу. Доказательство. Предпоб) ловим противное: существует 11 ее)) чениа Ь и Ысечение Зтакиа, что (Ь ГЗЗ(> 1. В этом случае найдут- Гьь 7.$.
ся два эпеманта х н у сати такие, 110 что к, у е ~ и к, уб 3, По опрвдвлвнию свчвний к йу и одновременно ка1 у, но это можвт быть только а том случае, если х у. т.в. !. и 3 содержат адинставнный общий злвмвнт. О Так же, как и а случав О сати, возникает проблвма неадекватных Зсвтвй, ксторыв, вали их интврпрвтироаать как послвдоаатвльноальтврнатианыв процессы, оказываются нвпривмпвмыми как рвальныа процвссы. Срччзи О- ратай выдвлялись К ппотныв О<эти, для которых синтаксические !сетваыв! и свмантичвскив првдстаалвния соответствовали друг другу. Аналогично йля 3 свтвй вводится понятна !..плотности, которов опрадвлявтся спадую!цим образом: 3 свть !..плотна, если а нвй любое !!чжчвннв и любов аЬсвчв.
иив пврвсвкаются ровно по одному злвмвнту. С учвтом творвмы 74 зто означэвт, что А .плотнел свть нв содержит ни одной лары непересекающихся !!чжчвний и а!сечений. Зюать нв рис. 7.6, е яапявтся !..ялотной, а то арвмп как Зювть на рис, 7.6, б на является !..плотной. В посладнвй сати имевтся бвсконвчнов !1'Саванна (Р~ г~ Ры Гыды Гт,... ), котодсв нв папвсакавтсп с басконвчным а!свчвниам (гз, г,, г~...,), показанным пунктирной пи. нивй. На примере этой сети можно увидать, а чем выражается несоответствие между синтаксисом и семантикой нала-плотной сети.
Наличие а нвй бесконечных а!.сечений означает, что сущвстауют бвсконвчныв соаокуююсти альтернативных действий (или измвнвний условий!. По опрвдвпанию послцпоаатапьно альтврнзтианого прсцвссв в каждой полной апьтврнатиав должно раализоаатьсп ровно одно действие. С другой стороны, в сати нв рис.
7.6, б возможна ситуация, когда фишка проходит вдоль бесконечного !! саввина (Ры Гн Рд, гз, Рз, Гт,...) и а РвзУльтатв ни ОДно из двйстанй гз, гч, гч,... на реализуется. Таким образом. указанные "топологичвскжг' альтернативы могут а действительности нв иметь места. Т в о р в м э 7.6. Пюбвя коявчнвя 5 свгь !.-ллогме. Опускавм доказательство этой творамы, поскольку оно авсьма похожа на доказатвльство творвмы 7.2 о х.плотности конвчных О свтвй.
$74. Свтвэов првдспщрвплв параллвлыю альтерпатпппых процвссоа Парвппвльно альтврнатианыв прсцвссы мы будам представлять с помощью зцикличвских свтвй, ипи 4 сетей, удовлетворяющих услоаиям А1-А7 и дополнитвлыюму услоаео А11, обаспвчиавощвму бвзопжность свтай из данного класса !аксиома А11 будвт сформулирована ниже! . В 4 сати пврвход может имать болвв одного аходного идчпи выходного места, а мвсто может быть инцидвнтно нескольким пврвхадэм.
Примвры 4 сетей показаны на рис. 7 8, з, 7 7, а, 7.6. О<эти и Зсати являются частными подклассами 4 сатвй. Поквжвм, каким обрезом отношвния следования, параллелизма и альтврнатиаы аыражаютс~ ° терминах 4 сетей. Отношвнив й аыйажавтся через свтваов отношение Р' таею так жв, как и а О- и 3 свтях, Отношение вльтарнатианости нельзя ощадвпить топологически вдинообразным способом для пврвходоа и мест сати из-за разных требований к реализации условия и действия а систвмв и соотавтстаанно появлению фишки а месте и срабатыаанию перехода а сати. Условие можвт реализоваться !иэмвниться), вопи хотя бы одно нвпосрадстванно првдшвстпующвв ему действие реализовалось, т.в. мвсто получит фишку, если хотя бы один паре. ход, для которого зто мвсто яплпвтсп входным, сработал.
Двйстаив можвт рвализоааться, вели асв нвпосрвдставнно прадшвстцующив вму условия рщлизоввлись. т.в. переход может сработать, шли асв вго входные места имеют фишки. Рз Рз ь! Рнс 2.Б, Два переходе 21 и г, альте(знагиеяы в А.сети в следующем случее: г, з(г, !(тз Иг,) Л ((тз ГЗ 'Гз ~ Ф) У (БРз Е Гз: (У Гз Е Рз: Г~ Е! Гз))~l [ЗРз Е'Гз.
(ЧУГз Е 'РзЗ Гз а! Гз)))'4 (Г, = Гз), тл. резные переходы г, и тз альтернетивиьз, если 1) они не находятся в отношении следования, 2) имеют общее входное место или непосредственный предшественник одного из переходов альтернативен другому. Двв местарз ирз альтернативны, если РЗ З! Р, ° з ('т Г, Е р,, ЗЗЗ т, Е 'РЗ: (Г, а! гЗ ) Л (Г, Ф ГЗ)! 'ЗГ'(Р, «РЗ), т.е. два различных места р, и Р, зльтернативны, если любой переход. для которого выходным местом служит р„альтернативен каждому переходу, выхоДным местом котоРого ЯвлЯетсЯ Рз, и все зти пеРехоДы Различны. Место Р и переход с альтерязтианы, если Р Е! Г з з ('Ф Г' Е 'Р: Г' Е! Г) l~ П(т й Р), т.е.
место р и переход с альтернативны, если они не связаны друг с другом никаким путем и любой переход г', для которого Р является выжщным „! Я 4 е! .а) Рис 2,2. зз2 знв т.в. местом, альтернативен переходу г. Двз злементе х и у в 4чюти мрзплель- ны, если они на связаны отношениями следования и альтернативны (илн х у) хсоу ч (х у)~/ ) (х))утеха(у).. Например, в сети нв рис. 7.6, ° переходы т1 и гз связаны отношением е(, переходы тт и т т также связаны отношением з(, а переходы г| и !э связа.
ны отношанием со. Дополнительное условие А11 формулируется следующим обратом: А11. У'РЕ Р, тГ т,, тт Е Т: ((тмтт Е Р) ° (т, а! тт!). Определения )ьсвчений, со сечений. данные выша длп О.сетей и 8 сетай, переносится на случай 4 сетей. А) сечение в 4 сети определяется несколько иначе. Об етом будет сказано ниже.
бели рассматривать отношения 11, со, а! как "координатные оси" некото- рого трехмерного яространства, то О сети лежат в плоскости, образованной координатными осями й и со, (нет альтернативных зламентов), а Засти лвжатваюскости,обрвзованнойосями!1и а( (нет пареллвльных зпаман. тов).
Для Осетей структурные ограничения, гарантирующие адекватное сетевое задание процассов, формулировались с помщцыо понятий 11- и от- сечений (все они должны попарно пересекаться) . Аналогично для адакват- ностн представлания поспвдоветелыю.альтернативных процессов требова- лось, чтобы попарно пересекались все б. и а) сечение. Для 4 сетей, адекват- но представляющих параллельно апьтернативные процессй, должны, во- парвых, выполняться требовании К.плотности и (.-плотностиихлодсатей, вводимых ниже, и, во.вторых, требуется выполнание еще одного свойства (Мчтлопюсги), которов формулируется в тарзанах пересечения ппоскд- стей, образованных, с одной стороны, 11- и ао саченипми, ° с другой — 11- и Н- сечениями.
Сеть В' (Р', Т, Р') являатсп подсетью сети В ~ (Р, Т, Р), если Р' ь, Р, Т' ~ Т, Р ' ~ Ей (Р' Х Т' О Т' Х Р') . Сеть В' называется Оподсетью 4 сети В, если: 1) В' является подсетью В, 2) дпя В выполнаны все условия, справадлнвью для Очютей, Э) 'ФГ ЕТ; (РЕР!РЕГ) Ь„Р и тГР Е Р: Р(Р,1) *'Р(Р,Г), ИЗ т.е. переход г в О подсети Н' имеет то же самое миожестао входиыи мест и всв дуги, селзыааощие вго с этими маетами, что и а 4 сети М Ззмвчююе. При определении О.подсети мы ие требуем аьиюлиеиил уемл аия АЗ, поскольку рвзиые а исходной 4 сети места а Очювсети могут иметь овио и то же миожестао иицидеитиых первходов, Несмотря ив то, чге ° подсети эти места совпадают, ивм важно сохранить информацию.
что В исходной А сети оии были иицидвитны различным множествам переходов и по существу были резными. 0 иопсвзь И ' сети И ивзоавм максимальной, если: 1) дпл жабой Очадсвти Из сети Н такой, что Щ лалявтсл О.подсетью сети Д)з верее» что Иг «з:, 2) всв головные месте И ' яалжотсл головными местами 4 сати И, Миожество всех мвксимвльиыл Очюдсетвй А сети И образуют ее лровкцию иа координатную плоскость ()), со), в объединение свободных языков всея Очюдсетвй совпадает со свободиым языком сети «(161. Длл Асвти иа рис, 7.6, е миожестао вв максимальных О подсетей состоит из подсвтвй, показвииых иа рис.
7.6, б, а. в для 4 сети нз рм.7.7, в — из подсетей, покеэвииых нв 1жц 7.7ъб, а, з. Сеть И (Р', Т, Р') иазыавется Зчюдсегью А сети И ~ (Р, Т, Р), если: 1) И' лаллвтся подсетью И, 21 для И ' выполиеиы асе условия, справедливые длл Зсетвй. 31»УГ„ГЗ ЕТ, УРЫРЗ Е Р': (т~ РР, Л ГЗРРЗ Л (Р» йРЗ1)м (68чюдсеть и" ~ (Р",т",Р"1 гыгзет"1.
Фактически условие 31 обеспечивает, что в З.пщ)сеть алодлт те и только те алемеиты, которые ° колодкой Асети были альтеривтивиы или ивходились ° отиовеиии спадовские, Замвчвнмл Для Зчюдсцтей мы не требуем аыполиеиия второй чести условия Аб, т.в. (уг Е Т': г Ф ф1, так квк из условил гг в) гз в 4 сети И следует сущвстеоаеиие вльтеривтивиых вхадиых мест (или излечив общаге входного места), ио альтвривтиаиость переходов ие гарантирует альтер. иативгюсти их выловиых мест. Зчюдсвть И' А апти И ивзоавм максимапыюй Зчмрсетью, если; 11 ))ля любой 3 подсети И" сати И такой. что Н лвлявтся 3 подсетью сети И, аерио.
что И' Н"; 21 головков место Н(Н') входит ао множество головиых мест сети И. Множество всея максимвльиыл 3 подсетей А сети И об(жзувт вв п)юекцию ивкоордиивтиую плоскость (й, в)1. Длл сети ив рис. 7.6, в миолилтао ае максимальных 8 подсетей состоит из павсетвй, показанных ларис 7 6 д д, для сети иа рис.7.7. з - из подсетей, показвииык ив рис.7.7, д, е, ж. Миожастло А элементов А сети называется вньгврнвгненим раэзвюм, ° сли»рх, у Е 4: и а1 у в И и существует макси мвльиея Зчюдсвть Н ', ° которой множество А яалявтсл вльтеривтивиым разрезом. Множество А элвмвитов 4 сети Иивзыаеется в) сечением, если множество 4 образует максимапьиый вльтеривтивиый разрез в И, т.в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
