第四章Petri网的结构性质课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,Petri,网的结构性质,-,第四章 Petri网的结构性质-,1,提纲,网的结构性质只由网的结构（基网）确定，而与网的初始标识无关。,一、结构有界性和守恒性,二、可重复性和协调性,三、不变量,四、可重复向量,五、死锁与陷阱,-,提纲 网的结构性质只由网的结构（基网）确定，而与网的初始标识,2,一、结构有界性和守恒性,定义,4.1.,设,N=(P,T;F),为一个网。如果对,N,赋予任意初始标识,M,0,。网系统,(N,M,0,),都是有界的，则称,N,为,结构有界网,。,定理,4.1.,设,A,为网,N=(P,T;F),的关联矩阵，则,N,为结构有界网的充分必要条件是：存在,m,（,m=|P|,）维正整数向量,Y,，使得,AY,0,。,-,一、结构有界性和守恒性定义4.1.设N=(P,T;F)为一,3,一、结构有界性和守恒性,-,一、结构有界性和守恒性-,4,一、结构有界性和守恒性,-,一、结构有界性和守恒性-,5,一、结构有界性和守恒性,定义,4.2.,设,N=(P,T;F),为一个网，,P,1,P,。如果对,N,的任意初始标识,M,0,，每个,pP,1,在,(N,M,0,),中都是有界的，则称,P,1,是网,N,的,结构有界的库所子集,。当,P,1,=,p,时，称库所,p,是,结构有界的,。若,p,不是结构有界的，则称,p,为,结构无界库所,。,定理,4.2.,设,A,为网,N=(P,T;F),的关联矩阵。,P,1,P,是网,N,的结构有界的库所子集的充分必要条件是：存在非平凡的非负整数向量,Y,，使得,AY,0,，且,p,i,P,1,Y(p,i,)0,。,-,一、结构有界性和守恒性定义4.2.设N=(P,T;F)为一,6,一、结构有界性和守恒性,定义,4.3.,设,N=(P,T;F),为一个网。如果存在一个,m,（,m=|P|,）维正整数权向量,Y=y(1),y(2),y(m),T,，使得对,N,的任一个初始标识,M,0,和任意,M,R(,M,0,),都有,则称,N,为,守恒的,。特别地，当,Y=1,1,1,T,时，得到,这时称,N,为,严格守恒的,。,定理,4.3.,设,A,为网,N=(P,T;F),的关联矩阵。,N,为守恒网的充分必要条件是：存在,m,（,m=|P|,）维正整数向量,Y,，使得,AY=0,。,-,一、结构有界性和守恒性定义4.3.设N=(P,T;F)为一,7,一、结构有界性和守恒性,推论,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,，,p,i,P,1,当且仅当,Y(j)0,，使得对,N,的,任意初始标识,M,0,和任意,M,R(,M,0,),都有,则称,N,关于库所子集,P,1,为部分守恒的,。,推论,4.3.,设,A,为网,N=(P,T;F),的关联矩阵。网,N,关于库所子集,P,1,为部分守恒的充分必要条件是：存在,m,维非负整数向量,Y,，使得,AY=0,。,-,一、结构有界性和守恒性推论4.1.设A为网N=(P,T;F,8,二、可重复性和协调性,定义,4.5.,设,N=(P,T;F),为一个网。若存在,N,的一个初始标识,M,0,，和一个无限的变迁序列,，使得,M,0,，且,tT,在中无限多次地出现，则称,N,为一个,可重复网,。,M,0,称为,N,的一个,可重复标识,。,定理,4.4.,设,N=(P,T;F),为一个网。若,A,为,N,的关联矩阵，则,N,为可重复网的充分必要条件是：存在,n,维正整数向量,X,，使得,A,T,X,0,。,推论,4.4.,设,N,为一个可重复网，若存在,N,的一个初始标识,M,0,，是,N,的一个可重复标识。那么对任意,M,M,0,，,M,也是,N,的一个可重复标识。,-,二、可重复性和协调性定义4.5.设N=(P,T;F)为一个,9,二、可重复性和协调性,定义,4.6.,设,N=(P,T;F),为一个网。若存在,N,的一个初始标识,M,0,和一个变迁序列,T*,，使得,M,0,M,0,，而且,tT,：,#(,t,),1,，则称,N,为一个,协调网,。,定理,4.5.,设,N=(P,T;F),为一个网，若,A,为,N,的关联矩阵，则,N,为协调网的充分必要条件是：存在,n,维正整数向量,X,，使得,A,T,X,=,0,。,-,二、可重复性和协调性定义4.6.设N=(P,T;F)为一个网,10,三、不变量,定义,4.7.,设,N=(P,T;F),为一个网，,|P|=m,，,|T|=n,，,A,为,N,的关联矩阵。,（,1,）如果存在非平凡的,m,维非负整数向量,Y,满足,AY=0,，则称,Y,为网,N,的一个,S-,不变量,。,（,2,）如果存在非平凡的,n,维非负整数向量,X,满足,A,T,X=0,，则称,X,为网,N,的一个,T-,不变量,。,引理,4.1.,设,Y,1,和,Y,2,为,N=(P,T;F),的两个,S-,不变量，,X,1,和,X,2,为,N,的两个,T-,不变量。那么,（,1,）,Y,1,+Y,2,是网,N,的,S-,不变量，,X,1,+X,2,是网,N,的,T-,不变量。,（,2,）若,Y,1,-Y,2,0,，则,Y,1,-Y,2,也是网,N,的一个网,S-,不变量；若,X,1,-X,2,0,，,X,1,-X,2,是网,N,的,T-,不变量。,定义,4.8.,设,N=(P,T;F),为一个网，,|P|=m,，,|T|=n,，,A,为,N,的关联矩阵。如果,Y,1,（,X,1,）是网,N,的一个,S-,不变量（,T-,不变量），而且任意满足,Y Y,1,（,X d,1,Y,1,+d,2,Y,2,+,+d,k,Y,k,而且，对任意,Y,i,SI,，都有,Y,=Y-(,d,1,Y,1,+d,2,Y,2,+,+d,k,Y,k,),Y,i,由引理,4.1,知,Y,也是网,N,的一个,S-,不变量。这样，就只能有下面两种情况之一：,或者,Y,是网,N,的另一个极小,S-,不变量；或者存在网,N,的另一个极小,S-,不变量,Y,k+1,SI,，使得,Y,k+1,0,|X|=t,i,T|X(i)0,并分别称它们为,S-,不变量,Y,的支集,和,T-,不变量,X,的支集,。,定义,4.11.,设,Y,（,X,）为网,N=(P,T;F),的一个,S-,不变量（,T-,不变量），,|Y|=P,1,（,|X|=T,1,）。如果任意满足,|Y,1,|=P,1,（,|X,1,|=T,1,）且,Y,1,Y,（,X,1,0,知,Y,是,N,的一个,S-,不变量。且,p,k,P,1,Y(k)=0,，说明,P,1,不是,N,的极小支集。,-,三、不变量证：下面只对S-不变量的情况进行证明。,16,三、不变量,求解不变量,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.,t,1,t,2,t,5,p,2,t,3,t,4,t,6,t,7,X,1,=2,2,0,0,1,1,1,T,X,2,=0,0,2,2,1,1,1,T,X,3,=1,1,1,1,1,1,1,T,-,三、不变量求解不变量t1t2t5p2t3t4t6t7X1=,17,三、不变量,定理,4.8.,一个网,N,的任意一个,S-,不变量（,T-,不变量）都是网,N,的立于极小支集上的极小,S-,不变量（极小,T-,不变量）的非负有理系数的线性组合。,定理,4.9.,如果,N,的每个立于极小支集上的极小,S-,不变量（极小,T-,不变量）都是,0/1,向量，那么网,N,的任何一个,S-,不变量（,T-,不变量）都是立于极小支集上的极小,S-,不变量（极小,T-,不变量）的非负整系数的线性组合。,-,三、不变量定理4.8.一个网N的任意一个S-不变量（T-不,18,四、可重复向量,定义,4.13.,设,N=(P,T;F),为一个网，,A,为,N,的关联矩阵。若,n,（,n=|T|,）维非平凡的非负整数向量,X,满足,A,T,X,0,，则称,X,为,N,的一个可重复向量，称,|X|=t,i,T|X(i)0,为可重复向量,X,的支集。,结论,网,N,的,T-,不变量也是,N,的可重复向量,若,X,1,和,X,2,为网,N,的可重复向量，则,X,1,+X,2,也是网,N,的可重复向量,若,T,1,和,T,2,为网,N,的可重复向量的支集，则,T,1,T,2,也是网,N,的可重复向量的支集,网,N,为可重复网当且仅当,T,为,N,的可重复向量的支集,-,四、可重复向量定义4.13.设N=(P,T;F)为一个网，,19,五、死锁与陷阱,定义,4.14.,设,N=(P,T;F),为一个网，,P,1,P,。,P,1,P,1,，则称,P,1,为网,N,的一个死锁（,Siphon,）,；如果,P,1,P,1,，则称,P,1,为,N,的一个陷阱。,在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。,p,2,t,1,t,2,p,1,p,2,t,1,t,2,p,1,死锁,陷阱,-,五、死锁与陷阱定义4.14.设N=(P,T;F)为一个网，,20,五、死锁与陷阱,定理,4.10.,设,N=(P,T;F),为一个网，,如果,P,1,P,是网的一个死锁，,P,2,P,是网,N,的一个陷阱，那么，对任意初始标识,M,0,，在网系统,PN=(N,M,0,),中,（,1,）若存在,M,1,R(,M,0,),，使得,则对,M,R(,M,1,),，都有,则对,M,R(,M,1,),，都有,（,2,）若存在,M,1,R(,M,0,),，使得,-,五、死锁与陷阱定理4.10.设N=(P,T;F)为一个网，,21,五、死锁与陷阱,定理,4.11.,设,N=(P,T;F),为一个网，,A,为,N,的关联矩阵。,如果,P,1,=p,i1,p,i2,p,ik,为网的一个死锁（陷阱）的充分必要条件是：,A,关于,P,1,列的列生成子阵中，每个非全零行至少包含一个,“,-1,”,（或,“,1,”,）元素。,M.,D.,J,eng,and,M.,Y.,P,eng,“,Generating,m,inimal,s,iphons and,t,raps for Petri,n,ets,”,in,IEEE International Conference on Systems,Man and Cybernetics,Vol.4,1996,pp.2996-2999.,M.Kinuyama,“,Generating,s,iphons and,t,raps by Petri,n,et,r,epresentation of,l,ogic,e,quations,”,in,Proceedings of 2th Conf