为Petri网的可覆盖性树.PPT

* Petri网进程 证. 令u0= {b| ?b = Φ}，显然u0是N的一个s-切，且 ?? (u0)=M0。设u为N的任一个s-切。显然u0 ? u，记 E(u0 , u)={e?E | ?b0 ?u0, b ?u: (b0,e) ? G+ ? (e, b) ? G+ } 下面对|E(u0 , u)|用数学归纳法证明定理的结论。 当|E(u0 , u)|=0时，显然u=u0，从而? (u0)= M0? R(M0)。 设对|E(u0 , u)|=k的任一个s-切u，都有M? R(M0)使得 ? (u)=M。 那么当|E(u0 , u)|=k+1时，易知存在N的一个s-切u1，使得 u0 ? u1? u（从而 E(u0 , u1) ? E(u0 , u) ），且|E(u0 , u1)|=k。 设E(u0 , u) - E(u0 , u1)={e}，则有?e ?u1，(u1 - ?e) ? e? =u ? (u1)=M1， ? (e)=t，因此有M1[t。设M1[tM，则? (u)=M。 在简单有向图中， 若任何两个节点间是相互可达的，则称是强连通图； 若任何两个节点之间至少从一个节点到另一个节点是可达的，则称是单向连通图或单侧连通图； 若在图中略去边的方向，将它看成无向图后，图是连通的，则称该图是弱连通图。 简单有向图中拥有附连通性质的最大子图就是强分图。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第三部分 Petri网的分析方法 提纲 可达标识图与可覆盖性树 关联矩阵与状态方程 Petri网语言 Petri网进程 可达标识图与可覆盖性树 对于有界Petri网，其可达标识集R(M0)是一个有限集合，因此可以以R(M0)作为顶点集，以标识之间的直接可达关系为弧集构成一个有向图，称为Petri网的可达标识图（reachable marking graph）。 定义3.1. 设PN=(P,T;F, M0)为一个有界Petri网。PN的可达标识图定义为一个三元组RG(PN)=(R(M0),E, L)，其中 E={(Mi,Mj)| Mi, Mj ? R(M0),??tk ?T: Mi [ tk Mj } L:E→T，L(Mi,Mj)= tk 当且仅当Mi [ tk Mj 称R(M0)为顶点集，E为弧（边）集， 若L(Mi,Mj) = tk，则称tk为弧(Mi,Mj)的旁标。 t2 t1 t4 p1 p2 p3 t3 M0 : (0,1,0) M2: (0,0,1) M1 : (1,0,0) t1 t2 t3 t4 可达标识图与可覆盖性树 通过可达标识图RG(PN)可以分析有界Petri网PN的各种性质。 定理3.1. 对任意Mi,Mj ? R(M0)，Mj是从 Mi可达的当且仅当在RG(PN)中，从Mi到Mj存在一条有向路。 推论3.1. 在RG(PN)中，从M0到每个结点都有一条有向路。 推论3.2. M? R(M0)是PN的一个死标识当且仅当在RG(PN)中，M是一个终端标识。 定理3.2. 设pj ?P，在Petri网PN中pj的界 B(pj )等于RG(PN)中各个顶点向量的第j个分量的最大值。 推论3.3. PN是安全的当且仅当RG(PN)中每个顶点的向量都是0-1向量。 可达标识图与可覆盖性树 定理3.3. 有界Petri网PN是活的当且仅当在RG(PN)中，从顶点M0出发的每条有向路都走入一个强连通子图，而且在每个这样的强连通子图中，每个t ?T至少是一条有向弧的旁标。 定理3.4. 有界Petri网PN的两个变迁t1和t2处于公平关系的充分必要条件是在RG(PN)的每条有向回路C中， t1是其中的一条弧的旁标当且仅当t2也是其中一条弧的旁标。 定理3.5. PN是公平Petri网的充分必要条件是在RG(PN)的每条有向回路C中，每个 t ?T 都至少是C中一条弧的旁标。 定理3.3、3.4和3.5在无界Petri网中还成立吗？ ？ 可达标识图与可覆盖性树 若PN不是有界网，则R(M0)是一个无限集合，无法画出PN的可达标识图。 为了用有限形式表达一个有无限个状态的系统的运行情况，引入一个表示无界量的符号??。 ??具有下述性质： （1）对任意正整数n：? n，? ? n= ? （2）? ? ? 当库所pj中的标识数在Petri网的运行过程中趋向于无限增长时，就把标识向量中的第j个分量改为? ，以此覆盖所有这类