第四章 Petri网的结构性质

提纲 网的结构性质只由网的结构（基网）确定，而与网的初始标识无关。 一、结构有界性和守恒性 二、可重复性和协调性 三、不变量 四、可重复向量 五、死锁与陷阱

一、结构有界性和守恒性 定义4.1. 设N=(P,T;F)为一个网。如果对N赋予任意初始标识M0。网系统(N, M0)都是有界的，则称N为结构有界网。 定理4.1. 设A为网N=(P,T;F)的关联矩阵，则N为结构有界网的充分必要条件是：存在m（m=|P|）维正整数向量Y，使得AY0。

一、结构有界性和守恒性

一、结构有界性和守恒性

一、结构有界性和守恒性 定义4.2. 设N=(P,T;F)为一个网， P1 P 。如果对N的任意初始标识M0，每个pP1在(N, M0)中都是有界的，则称P1是网N的结构有界的库所子集。当P1= {p}时，称库所p 是结构有界的。若p不是结构有界的，则称p为结构无界库所。 定理4.2. 设A为网N=(P,T;F)的关联矩阵。 P1 P 是网N的结构有界的库所子集的充分必要条件是：存在非平凡的非负整数向量Y，使得AY0，且piP1 ,Y(pi)>0。

一、结构有界性和守恒性 定义4.3. 设N=(P,T;F)为一个网。如果存在一个m（m=|P|）维正整数权向量Y=[y(1), y(2), …, y(m)]T，使得对N的任一个初始标识 M0和任意MR(M0)都有 则称N为守恒的。特别地，当Y=[1,1,… ,1]T时，得到 这时称N为严格守恒的。 定理4.3.设A为网N=(P,T;F)的关联矩阵。N为守恒网的充分必要条件是：存在m（m=|P|）维正整数向量Y，使得AY=0。

一、结构有界性和守恒性 推论4.1. 设A为网N=(P,T;F)的关联矩阵。N为严格守恒网的充分必要条件是：存在m（m=|P|）维的全1向量Y=[1,1,… ,1]T ，使得AY=0。 推论4.2. 若N是守恒网，则N必是结构有界网。 定义4.4. 设N=(P,T;F)为一个网。如果存在一个m（m=|P|）维非负整数向量Y， piP1 当且仅当Y(j)>0，使得对N的任意初始标识 M0和任意MR(M0)都有 则称N关于库所子集P1为部分守恒的。 推论4.3. 设A为网N=(P,T;F)的关联矩阵。网N关于库所子集P1为部分守恒的充分必要条件是：存在m维非负整数向量Y，使得AY=0。

二、可重复性和协调性 定义4.5. 设N=(P,T;F)为一个网。若存在N的一个初始标识M0，和一个无限的变迁序列，使得M0[>，且tT在中无限多次地出现，则称N为一个可重复网。M0称为N的一个可重复标识。 定理4.4. 设N=(P,T;F)为一个网。若A为N的关联矩阵，则N为可重复网的充分必要条件是：存在n维正整数向量X，使得ATX0。 推论4.4. 设N为一个可重复网，若存在N的一个初始标识M0，是N的一个可重复标识。那么对任意M M0，M也是N的一个可重复标识。

二、可重复性和协调性 定义4.6.设N=(P,T;F)为一个网。若存在N的一个初始标识M0和一个变迁序列T*，使得M0[> M0，而且tT ：#(,t)1，则称N为一个协调网。 定理4.5. 设N=(P,T;F)为一个网，若A为N的关联矩阵，则N为协调网的充分必要条件是：存在n维正整数向量X，使得ATX=0。

三、不变量 定义4.7.设N=(P,T;F)为一个网，|P|=m，|T|=n，A为N的关联矩阵。 （1）如果存在非平凡的m维非负整数向量Y满足AY=0，则称Y为网N的一个S-不变量。 （2）如果存在非平凡的n维非负整数向量X满足ATX=0，则称X为网N的一个T-不变量。 引理4.1. 设Y1和Y2为N=(P,T;F)的两个S-不变量，X1和X2为N的两个T-不变量。那么 （1） Y1 + Y2是网N的S-不变量， X1 + X2是网N的T-不变量。 （2）若Y1 - Y2 >0，则Y1 - Y2也是网N的一个网S-不变量；若X1 - X2 >0 ， X1 - X2是网N的T-不变量。 定义4.8. 设N=(P,T;F)为一个网，|P|=m，|T|=n，A为N的关联矩阵。如果Y1 （ X1）是网N的一个S-不变量（T-不变量），而且任意满足Y< Y1（X< X1）的m（n）维非负整数向量Y（X）都不是网N的S-不变量（T-不变量），那么称Y1 （ X1）为网N的一个极小S-不变量（极小T-不变量）。

三、不变量 定义4.9.设V1,V2,…,Vk和V都是非平凡的非负整数n维向量。如果存在一组非负整数c1,c2,…,ck，使得 V= c1V1+c2V2+…+ckVk 则称向量V可以被V1,V2,…,Vk非负整系数线性表出，或称V是V1,V2,…,Vk的非负整系数线性组合。 定理4.6. 一个网N的任意一个S-不变量（T-不变量）都是网N的极小S-不变量（极小T-不变量）的非负整系数线性组合。

三、不变量 证：设SI={Y1,Y2,…,Yk} 为网N的全部极小S-不变量的集合。对任意一个S-不变量Y，都存在一组非负整数c1,c2,…,ck，使得 Y= c1Y1+c2Y2+…+ckYk 用反证法。假设上式不成立，那么必存在一组非负整数d1,d2,…,dk，使得 Y > d1Y1+d2Y2+…+dkYk 而且，对任意YiSI，都有 Y’=Y-(d1Y1+d2Y2+…+dkYk ) Yi 由引理4.1知Y’也是网N的一个S-不变量。这样，就只能有下面两种情况之一： 或者Y’是网N的另一个极小S-不变量；或者存在网N的另一个极小S-不变量Yk+1SI，使得Yk+1 < Y’。两种情况都表明SI并没有包含网N的全部极小S-不变量，从而产生矛盾。

三、不变量 定义4.10.设Y和X分别为网N=(P,T;F)的S-不变量和T-不变量。记 ||Y||={pjP | Y(j)>0} ||X||={tiT | X(i)>0} 并分别称它们为S-不变量Y的支集和T-不变量X的支集。 定义4.11.设Y（X）为网N=(P,T;F)的一个S-不变量（T-不变量），||Y||=P1（ ||X||=T1 ）。如果任意满足||Y1||=P1（ ||X1||=T1 ）且Y1 < Y（ X1 < X ）的m（n）维非负整数向量Y1（X1）都不是N的S-不变量（T-不变量），则称Y（X）为立于支集S1（T1）上的极小S-不变量（极小T-不变量）。 定义4.12.设Y（X）为网N=(P,T;F)的一个S-不变量（T-不变量），||Y||=P1（ ||X||=T1 ）。如果任意P2P1（ T2T1 ）都不是网N的S-不变量的支集，则称P1 （ T1 ）为网N的S-不变量的极小支集（网N的T-不变量的极小支集）。

三、不变量 引理4.2.设P1和P2为网N=(P,T;F)的两个S-不变量的支集，则P2 P1也是网N的S-不变量的支集（对T-不变量也有类似结论）。 推论4.5. 网N=(P,T;F)为守恒网的当且仅当N的库所集P是N的一个S-不变量的支集；N为协调网当且仅当N的变迁集是N的一个T-不变量的支集。 定理4.7.对每个极小支集P1 （ T1 ），立于极小支集P1 （ T1 ）上的极小S-不变量（极小T-不变量）是唯一的。

三、不变量 证：下面只对S-不变量的情况进行证明。 设Y1和Y2都是立于支集P1上的极小S-不变量，但Y1Y2 。记 Y1=[Y1(1), Y1(2), …,Y1(m)]T Y2=[Y2(1), Y2(2), …,Y2(m)]T 显然，若piP1，则Y1(i) 0且Y2(i) 0。令 和 Y=Y2 (k) Y1 - Y1(k)Y2 则易知 AY=A(Y2 (k) Y1 - Y1(k)Y2)= Y2 (k)AY1 - Y1(k)AY2=0 i：Y(i)=Y2 (k) Y1(i) - Y1(k)Y2(i)0，且由于Y1Y2 ，至少存在一个j，使得 从而 Y(j)=Y2(k)Y1(j) - Y1(k)Y2(j) >0 知Y是N的一个S-不变量。且pkP1→Y(k)=0，说明P1不是N的极小支集。

三、不变量 求解不变量 t1 t2 t6 t7 X1={2,2,0,0,1,1,1}T X2={0,0,2,2,1,1,1}T p2 t3 t4 t6 t7 X1={2,2,0,0,1,1,1}T X2={0,0,2,2,1,1,1}T X3={1,1,1,1,1,1,1}T 求解不变量 J.Martinez, M.Silva, A Simple and Fast Algorithm to Obtain All Invariants of Generalized Petri Nets, Springer-Verlag,1982, pp.301-303 C.Lin, S.T.Chanson, T.Murata, Petri net Models and Efficient T-invariant Analysis for Logic Inference of Clauses, 1996 IEEE International Conference on Systmes, Man and Cybernetics, Beijing, China, October 14-17, 1996, pp. 3174-3179.

三、不变量 定理4.8. 一个网N的任意一个S-不变量（T-不变量）都是网N的立于极小支集上的极小S-不变量（极小T-不变量）的非负有理系数的线性组合。 定理4.9.如果N的每个立于极小支集上的极小S-不变量（极小T-不变量）都是0/1向量，那么网N的任何一个S-不变量（T-不变量）都是立于极小支集上的极小S-不变量（极小T-不变量）的非负整系数的线性组合。

四、可重复向量 定义4.13. 设N=(P,T;F)为一个网，A为N的关联矩阵。若n（n=|T|）维非平凡的非负整数向量X满足ATX0，则称X为N的一个可重复向量，称 ||X||={ti T|X(i)>0} 为可重复向量X的支集。 结论 网N的T-不变量也是N的可重复向量 若X1和X2为网N的可重复向量，则X1+X2 也是网N的可重复向量 若T1和T2为网N的可重复向量的支集，则T1T2也是网N的可重复向量的支集 网N为可重复网当且仅当T为N的可重复向量的支集

在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。 五、死锁与陷阱 定义4.14. 设N=(P,T;F)为一个网， P1  P。 •P1  P1• ，则称P1为网N的一个死锁（Siphon） ；如果P1•  •P1，则称P1为N的一个陷阱。 p2 t1 t2 p1 死锁 陷阱 在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。

五、死锁与陷阱 定理4.10. 设N=(P,T;F)为一个网， 如果P1  P是网的一个死锁， P2  P 是网N的一个陷阱，那么，对任意初始标识M0，在网系统PN=(N,M0) 中 （1）若存在M1R(M0)，使得 则对MR(M1)，都有 （2）若存在M1R(M0)，使得 则对MR(M1)，都有

五、死锁与陷阱 定理4.11. 设N=(P,T;F)为一个网，A为N的关联矩阵。 如果P1 ={pi1, pi2 ,…, pik} 为网的一个死锁（陷阱）的充分必要条件是：A关于P1 列的列生成子阵中，每个非全零行至少包含一个“-1”（或“1”）元素。 M. D. Jeng and M. Y. Peng, “Generating minimal siphons and traps for Petri nets,” in IEEE International Conference on Systems, Man and Cybernetics, Vol. 4, 1996, pp. 2996-2999. M. Kinuyama, “Generating siphons and traps by Petri net representation of logic equations,” in Proceedings of 2th Conference of the Net Theory, SIG-IECE, 1989, pp. 93-100. K. Lautenbach, “Linear algebraic calculation of deadlocks and traps,” in Concurrency and Nets-Advances in Petri Nets, Voss, Genrich and Rozenberg, Eds., New York: Springer-Verlag, 1987, pp.315-336. R. Cordone, L. Ferrarini, and L. Piroddi, “Characterization of minimal and basis siphons with predicate logic and binary programming,” in 2002 IEEE International Symposium on Computer Aided Control and System Design, 2002, pp. 193-198. M. Yamauchi, S. Tanimoto, and T. Watanabe, “Extracting siphons containing a specified set of places in a Petri net,” in 1998 IEEE International Conference on Systems, Man and Cybernetics, Vol. 1, 1998, pp. 142-147. E. R. Boer and T. Murata, “Generating basis siphons and traps of Petri nets using the sign incidence matrix,” IEEE Transactions On Circuits and Systems-I: Fundamental Theory and Applications, Vol. 41, 1994, pp. 266-271. A. Taguchi, S. Taoka, and T. Watanabe, “An algorithm GMST for extracting minimal siphon-traps and its application to efficient computation of Petri net invariants,” in Proceedings of the 2003 IEEE International Symposium on Circuits and Systems, Vol. 3, 2003, pp. III-172-III-175. D. Y. Chao, “An incremental approach to extracting minimal bad siphons,” Journal of Information Science and Engineering, Vol. 23. 2007, pp. 203-214. M. Yamauchi and T. Watanabe, “Time complexity analysis of the minimal siphon extraction problem of Petri nets,” IEICE Transactions on Fundamentals, Vol. E82-A, 1999, pp. 2558-2565.