第四章 Petri网的结构性质提纲n 网的结构性质只由网的结构（基网）确定，而与网的初始网的结构性质只由网的结构（基网）确定，而与网的初始标识无关。标识无关。一、结构有界性和守恒性一、结构有界性和守恒性二、可重复性和协调性二、可重复性和协调性三、不变量三、不变量四、可重复向量四、可重复向量五、死锁与陷阱五、死锁与陷阱一、结构有界性和守恒性n定义定义4.1. 设设N=(P,T;F)为一个网。如果对为一个网。如果对N赋予任赋予任意初始标识意初始标识M0。网系统。网系统(N, M0)都是有界的，则称都是有界的，则称N为为结构有界网结构有界网。n定理定理4.1. 设设A为网为网N=(P,T;F)的关联矩阵，则的关联矩阵，则N为结为结构有界网的充分必要条件是：存在构有界网的充分必要条件是：存在m（m=|P|）维）维正整数向量正整数向量Y，使得，使得AY 0。一、结构有界性和守恒性一、结构有界性和守恒性一、结构有界性和守恒性n定义定义4.2. 设设N=(P,T;F)为一个网，为一个网， P1 P 。如果对。如果对N的任意初始标识的任意初始标识M0，每个，每个p P1在在(N, M0)中都是有界的，则称中都是有界的，则称P1是网是网N的的结构有界的结构有界的库所子集库所子集。当。当P1= p时，称，称库所所p 是是结构有界的结构有界的。若。若p不是结构有界不是结构有界的，则称的，则称p为为结构无界库所结构无界库所。n定理定理4.2. 设设A为网为网N=(P,T;F)的关联矩阵。的关联矩阵。 P1 P 是网是网N的结构有界的的结构有界的库所子集的充分必要条件是：存在非平凡的非负整数向量库所子集的充分必要条件是：存在非平凡的非负整数向量Y，使得，使得AY 0，且，且pi P1 ,Y(pi)0。一、结构有界性和守恒性n定义定义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, ,1T时，得到时，得到 这时称这时称N为为严格守恒的严格守恒的。n定理定理4.3.设设A为网为网N=(P,T;F)的关联矩阵。的关联矩阵。N为守恒网的充分必要条件是：存在为守恒网的充分必要条件是：存在m（m=|P|）维正整数向量）维正整数向量Y，使得，使得AY=0。一、结构有界性和守恒性n推论推论4.1. 设设A为网为网N=(P,T;F)的关联矩阵。的关联矩阵。N为严格守恒网的充分必要条件是：存在为严格守恒网的充分必要条件是：存在m（m=|P|）维的全）维的全1向量向量Y=1,1, ,1T ，使得，使得AY=0。n推论推论4.2. 若若N是守恒网，则是守恒网，则N必是结构有界网。必是结构有界网。n定义定义4.4. 设设N=(P,T;F)为一个网。如果存在一个为一个网。如果存在一个m（m=|P|）维非负整数向量）维非负整数向量Y， pi P1 当且仅当当且仅当Y(j)0，使得对，使得对N的的任意初始标识任意初始标识 M0和任意和任意M R(M0)都有都有 则称则称N关于库所子集关于库所子集P1为部分守恒的为部分守恒的。n推论推论4.3. 设设A为网为网N=(P,T;F)的关联矩阵。网的关联矩阵。网N关于库所子集关于库所子集P1为部分守恒的充分必要条为部分守恒的充分必要条件是：存在件是：存在m维非负整数向量维非负整数向量Y，使得，使得AY=0。二、可重复性和协调性n定义定义4.5. 设设N=(P,T;F)为一个网。若存在为一个网。若存在N的一个初始标识的一个初始标识M0，和一个，和一个无限的变迁序列无限的变迁序列，使得，使得M0 ，且，且 tT在中无限多次地出现，则称在中无限多次地出现，则称N为一个为一个可重复网可重复网。M0称为称为N的一个的一个可重复标识可重复标识。n定理定理4.4. 设设N=(P,T;F)为一个网。若为一个网。若A为为N的关联矩阵，则的关联矩阵，则N为可重复网为可重复网的充分必要条件是：存在的充分必要条件是：存在n维正整数向量维正整数向量X，使得，使得ATX 0。n推论推论4.4. 设设N为一个可重复网，若存在为一个可重复网，若存在N的一个初始标识的一个初始标识M0，是，是N的一的一个可重复标识。那么对任意个可重复标识。那么对任意M M0，M也是也是N的一个可重复标识。的一个可重复标识。二、可重复性和协调性n定义定义4.6.设设N=(P,T;F)为一个网。若存在为一个网。若存在N的一个初始标识的一个初始标识M0和一个变迁序列和一个变迁序列 T*，使得，使得M0 M0，而且，而且 tT ：#( ,t) 1，则称，则称N为一个为一个协调网协调网。n定理定理4.5. 设设N=(P,T;F)为一个网，若为一个网，若A为为N的关联矩阵，则的关联矩阵，则N为协调网的充分必要条件是：存在为协调网的充分必要条件是：存在n维正整数向量维正整数向量X，使，使得得ATX=0。三、不变量n定义定义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-不变量不变量。n引理引理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-不变量。不变量。n定义定义4.8. 设设N=(P,T;F)为一个网，为一个网，|P|=m，|T|=n，A为为N的关联矩阵。如果的关联矩阵。如果Y1 （ X1）是）是网网N的一个的一个S-不变量（不变量（T-不变量），而且任意满足不变量），而且任意满足Y Y1（X 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 0 |X|=ti T | X(i)0 并分别称它们为并分别称它们为S-不变量不变量Y的支集的支集和和T-不变量不变量X的支集的支集。n定义定义4.11.设设Y（X）为网）为网N=(P,T;F)的一个的一个S-不变量（不变量（T-不变量），不变量），|Y|=P1（ |X|=T1 ）。如果任意满足）。如果任意满足|Y1|=P1（ |X1|=T1 ）且）且Y1 Y（ X1 0 知知Y是是N的一个的一个S-不变量。且不变量。且pk P1Y(k)=0，说明，说明P1不是不是N的极小支集。的极小支集。三、不变量n求解不变量求解不变量J.Martinez, M.Silva, A Simple and Fast Algorithm to Obtain All Invariants of Generalized Petri Nets, Springer-Verlag,1982, pp.301-303C.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. t1t2t5p2t3t4t6t7X1 1=2,2,0,0,1,1,1TX2=0,0,2,2,1,1,1TX3=1,1,1,1,1,1,1T三、不变量n定理定理4.8. 一个网一个网N的任意一个的任意一个S-不变量（不变量（T-不变量）都是不变量）都是网网N的立于极小支集上的极小的立于极小支集上的极小S-不变量（极小不变量（极小T-不变量）不变量）的非负有理系数的线性组合。的非负有理系数的线性组合。n定理定理4.9.如果如果N的每个立于极小支集上的极小的每个立于极小支集上的极小S-不变量不变量（极小（极小T-不变量）都是不变量）都是0/1向量，那么网向量，那么网N的任何一个的任何一个S-不不变量（变量（T-不变量）都是立于极小支集上的极小不变量）都是立于极小支集上的极小S-不变量不变量（极小（极小T-不变量）的非负整系数的线性组合。不变量）的非负整系数的线性组合。四、可重复向量n定义定义4.13. 设设N=(P,T;F)为一个网，为一个网，A为为N的关联矩阵。若的关联矩阵。若n（n=|T|）维非平凡）维非平凡的非负整数向量的非负整数向量X满足满足ATX 0，则称，则称X为为N的一个可重复向量，称的一个可重复向量，称 |X|=ti T|X(i)0 为可重复向量为可重复向量X的支集。的支集。n结论结论网网N的的T-不变量也是不变量也是N的可重复向量的可重复向量若若X1和和X2为网为网N的可重复向量，则的可重复向量，则X1+X2 也是网也是网N的可重复向量的可重复向量若若T1和和T2为网为网N的可重复向量的支集，则的可重复向量的支集，则T1 T2也是网也是网N的可重复向量的支集的可重复向量的支集网网N为可重复网当且仅当为可重复网当且仅当T为为N的可重复向量的支集的可重复向量的支集五、死锁与陷阱n定义定义4.14. 设设N=(P,T;F)为一个网，为一个网， P1 P。 P1 P1 ，则称，则称P1为网为网N的一个死锁（的一个死锁（Siphon） ；如果；如果P1 P1，则称，则称P1为为N的一个陷阱。的一个陷阱。在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。有标志的陷阱，永远不会失去标志。p2t1t2p1p2t1t2p1死锁死锁陷阱陷阱五、死锁与陷阱n定理定理4.10. 设设N=(P,T;F)为一个网，为一个网， 如果如果P1 P是网的一个死锁，是网的一个死锁， P2 P 是网是网N的一个陷阱，那么，对任意初始标识的一个陷阱，那么，对任意初始标识M0，在网系统，在网系统PN=(N,M0) 中中 （1）若存在）若存在M1 R(M0)，使得，使得 则对则对 M R(M1)，都有，都有 则对则对 M R(M1)，都有，都有 （2）若存在）若存在M1 R(M0)，使得，使得五、死锁与陷阱n定理定理4.11. 设设N=(P,T;F)为一个网，为一个网，A为为N的关联矩阵。的关联矩阵。 如果如果P1 =pi1, pi2 , pik 为网的一个死锁（陷阱）的充分必要为网的一个死锁（陷阱）的充分必要条件是：条件是：A关于关于P1 列的列生成子阵中，每个非全零行至少包含一个列的列生成子阵中，每个非全零行至少包含一个“-1”（或（或“1”）元素。）元素。nM. D. Jeng and M. Y. Peng, “Generating minimal siphons and traps for Petri ne