Основные определения

4.2.1. Теоретико-множественное определение сетей Петри

Пусть мультимножество это множество, допускающее вхождение нескольких экземпляров одного и того же элемента.

Сеть Петри N является четверкой N=(P,Т,I,O), где

P = {p ₁, p ₂,..., p _n } — конечное множество позиций, n ³ 0;

T = {t ₁, t ₂,..., t _m } — конечное множество переходов, m ³ 0;

I: T ® P* — входная функция, сопоставляющая переходу мультимножество его входных позиций;

О: T ® P* - выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция pÎPназывается входом для перехода tÎT, если pÎI(t). Позиция pÎPназывается выходом для перехода tÎT, если pÎO(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Пример 4.1. Сеть Петри N =(P,T,I,O),

P={p ₁, p ₂, p ₃ },

T={t ₁, t ₂ },

I(t ₁)={ p ₁, p ₁, p ₂ }, O(t ₁)={p ₃ },

I(t ₂)={ p ₁, p ₂, p ₂ }, O(t ₂)={p ₃ }.

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

4.2.2. Графы сетей Петри.

Наиболее наглядным представлением сети Петри является её графическое представление, которое представляет собой двудольный, ориентированный мультиграф.

Граф сети Петри обладает двумя типами узлов: кружок m, представляющий позицию сети Петри; и планка ¾;,представляющая переход сети Петри. Ориентированные дуги этого графа (стрелки) соединяют переход с его входными и выходными позициями. При этом дуги направлены от входных позиций к переходу и от перехода к выходным позициям. Кратным входным и выходным позициям перехода соответствуют кратные входные и выходные дуги. Граф сети Петри примера 4.1.

Рисунок 4.1.

В графе сети Петри не возможны дуги между двумя позициями и между двумя переходами.

4.2.3. Маркировка сетей Петри.

Маркировка — это размещение по позициям сети Петри фишек, изображаемых на графе сети Петри точками. Фишки используются для определения выполнения сети Петри. Количество фишек в позиции при выполнении сети Петри может изменяться от 0 до бесконечности.

Маркировка m сети Петри N=(P,T,I,О) есть функция, отображающая множество позиций P во множествоNat неотрицательных целых чисел. Маркировка m, может быть также определена как n-вектор m=<m(p₁), m(p ₂),…, m(p _n)>, где n– число позиций в сети Петри и для каждого 1 £ i £ n m(p _i) Î Nat – количество фишек в позиции p _i.

Маркированная сеть Петри N=(P,Т,I,О,m) определяется совокупностью структуры сети Петри (P,T,I,О) и маркировки m. На рисунке 4.2 представлена маркированная сеть Петри m = <1,0,1>.

Рисунок 4.2.

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

4.2.4. Правила выполнения сетей Петри.

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

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

Пусть функция ^{^} #: P´T ® Nat для произвольных позиции pÎPи перехода tÎТ задает значение ^{^} #(p,t), которое совпадает с кратностью дуги, ведущей из p в t, если такая дуга существует, и с нулем, в противном случае.

Пусть функция # ^{^}: T´P ®Nat для произвольных и перехода tÎT позиции pÎPзадает значение # ^{^} (t,p), которое совпадает с кратностью дуги, ведущей из t в p, если такая дуга существует, и с нулем, в противном случае.

Переход tÎT в маркированной сети Петри N=(P,T,1,О,m) разрешен, если для всех p Î I(t) справедливо m(p) ³ ;^{^}#(p,t).

Запуск разрешённого перехода tÎT из своей входной позиции pÎI(t) удаляет ^{^} #(p,t) фишек, а в свою выходную позицию p’Î O(t) добавляет # ^{^} (t,p’) фишек.

Сеть Петри до запуска перехода t ₁ (рис. 4.3, а). Сеть Петри после запуска перехода t ₁ (рис. 4.3, б).

Рисунок 4.3. а б

Переход t в маркированной сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен и в результате этого запуска образуется новая маркировка m ', определяемая для всех pÎP следующим соотношением:

m'(p)= m(p) – ^{^} #(p,t) + # ^{^} (t,p).

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

Если запуск произвольного перехода t преобразует маркировку m сети Петри в новую маркировку m', то будем говорить, что m' достижима из m посредством запуска перехода t и обозначать этот факт, как m ®^t m'. Это понятие очевидным образом обобщается для случая последовательности запусков разрешённых переходов. Через R(N,m) обозначим множество всех достижимых маркировок из начальной маркировки m в сети Петри N.

Преобразование маркировки сети Петри изображено на рисунке 4.3. Переход t ₁ преобразует маркировку m =<5,1> в маркировку m’=<2,3>.