第3章 Petri网.pptVIP

*;*;*;前集和后集：对于一个Petri网结构N =（P，T；F），设x∈(P ? T)，令 ?x = {y︱? y：(y，x) ?F}; x? = {y︱? y：(x，y) ?F}，那么称?x为x的前集或输入集，x?称为x的后集或输出集。 在N =（P，T，F）中，如果对所有的x∈(P ? T)，都有?x ? x?= ?，则称N为单纯网（pure net），简称纯网；如果对所有的x，y∈X，都有(?x =?y)?(x?=y?)? x = y，则称N为简单网（simple net）。 Petri网允许位置中包含令牌（token），令牌可以依据迁移的引发而重新分布。具有动态特征的Petri网定义如下： 普通Petri网：普通Petri网形式上定义为一个四元组PN=(P, T, F, M0）= (N，M0)，其中， ① N =（P，T，F）是一个Petri网结构； ② M：P? Z（非负整数集合）是位置集合上的标识（marking）向量。对于任一位置p ?P,以M (p)表示标识向量M中位置p所对应的分量，称为位置p上的标识或者令牌数目。M0是初始标识向量。 在Petri网的图形表示中，标记或令牌用位置中的黑点或数字表示，同一位置中的多个标记代表同一类完全等价的个体。标识向量表示了令牌在位置中的分布。 ;*;; ;（一） 基本定义;*;*;迁移的使能条件II：对于Petri网PN=（P,T,F,K,W,M），如果(?p1)p1??t? M(p1) ?W（p1，t）且(?p2) p2∈t? ?K(p2)?M(p2)+W(t,p2)，则称t在M下使能，记为M[t ?。 迁移的引发规则II ：对于Petri网PN=（P, T, F, K ,W, M），任何在M下使能的迁移t将会引发，迁移t的引发使得位置中令牌重新分布，从而将标识M变成新标识M?，并记为M[t? M?。对于?p?P，M? (p)可通过下式计算： M(p)– W(p,t) p??t - t? M?(p)= M(p)+ W(t,p) p? t?- ?t M(p)– W(p,t)+ W(t,p) p??t ? t? M(p) p? t???t ;;p4;顺序、并发、冲突、混惑结构的Petri网模型： 顺序关系：设M为Petri网PN的一个标识，若存在t1和t2使得M[t1? M?， 且?M[t2?，M? [t2?，亦即，在M标识下，t1使能，而t2不使能，且 t1的引发会使t2使能，即t2的使能以t1的引发为条件，则称t1和t2在M下有顺序关系。 并发关系：设M为Petri网PN的一个标识，若存在t1和t2使得M[t1?和M[t2?，并满足M[t1?M1 ? M1[t2?，且M[t2 ?M2 ? M2[t1?，则称t1和t2在M下并发。就是说在M标识下，t1和t2都使能，且它们当中任一个迁移的引发都不会使另一个迁移不使能。 冲突关系：设M为Petri网PN的一个标识，若存在t1和t2使得M[t1?和M[t2?，并满足M[t1?M1 ? ?M1[t2?，且M[t2?M2 ? ?M2[t1?，则称t1和t2在M下冲突。就是说M 标识下，t1和t2都使能，但它们当中任一个迁移引发都会使另一个迁移不使能。; 混惑关系：某些情形下，一个Petri网中可能同时存在着并发和冲突，而且并发迁移的引发会引起冲突的消失或出现。下图所示的Petri网中，t1和t3是两个并发迁移，若t3先于t1引发，则t2获得发生权，而且t2和t1处于竞争资源的冲突状态。若进一步在解决冲突时让t2引发，则t1就失去了曾经拥有的发生权。如果在t1和t2的冲突中让t1引发，则p5获得令牌，系统到达最终状态（0，0，1，0，1，0）。从初始状态（1，1，0，1，0，0）到达（0，0，1，0，1，0）的另一种可能是t1先引发，然后t3引发。t1和t3并发也到达这一状态。这后两种情况不会出现冲突。换句话说，从所观察到的状态变化（1，1，0，1，0，0）→（0，0，1，0，1，0），无法判断其间是否出现过冲突，象这样并发和冲突混合在一起产生的困惑，使人无法从终态判断是否有冲突发生过，所以将这种情况称为“混惑”。 ;*;*;*;*;*;图中Petri网，t1、t2、t3和t4分别是L0、L1、L2和L3-活的，因为t1总是不能引发的；一旦p1因t2引发而失去令牌，就无法再获得令牌，即t2最多只能引发1次；t2引发后，t4不能再引发，t3的最大引发次数为p2中的令牌数，即