第三章 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)的旁标。


通过引入 ，就可以用有限树来反映无界Petri网的运行情况，称该有限树为 Petri网PN的可覆盖性树（coverability tree），记为CT(PN)。
一、可达标识图与可覆盖性树

算法3.1. Petri网可覆盖性树的构造算法 输入： PN=(P,T;F, M0) 输出：CT(PN) 算法步骤： Step0：以M0作为CT(PN)的根结点，并标之以“新”； Step1：While 存在标注为“新”的结点 Do 任选一个标注为“新”的结点，设为M； Step2： Step3： If 从M0 到M的有向路上有一个结点的标识等于M Then 把M的标注改为“旧”，返回Step1； If tT:M[t> Then 把M的标注改为“端点”，返回Step1
(0,0, ,1)
(1,0, ,1) t1 (0,1, ,1)
(c)
说，的引入主要导致两
类重要信息缺失或者反映 的不全面：
图1：有相同可覆盖性树但标识变化规律不同的Petri网

t1
t3 p2 p3
M0 : (0,1,0)
t1 t2 M1 : (1,0,0) t3 t4
p1
t2
t4
M2: (0,0,1)
一、可达标识图与可覆盖性树

通过可达标识图RG(PN)可以分析有界Petri网PN的各种性质。 定理3.1. 对任意Mi,Mj R(M0)，Mj是从 Mi可达的当且仅当在RG(PN) 中，从Mi到Mj存在一条有向路。
M0 : (1,0,0,0) t2
(0,1,1,0) t1 (1,0, ,0) t2 (0,1, ,0) t1 (1,0, ,0) t4 t4 (0,0,0,1)

t1
t3

定义3.2. 设CT(PN)为Petri网的可覆 盖性树。若将CT(PN)中标识向量相 同的结点合并在一起，便得到PN的 可覆盖性图，记为CG(PN)。
一、可达标识图与可覆盖性树
p1
M0 : (1,0,0,0) 新 t2
t3 (0,1,1,0) 新 t4 t1 p4 (1,0, ,0) 新 1,0) t2 (0,1, ,0) 新 t4 t1 (1,0, ,0) 新 旧 (0,0,0,1) 新 端点
t1 p2
t2
p3
t4
(0,0, ,1) 新

一、可达标识图与可覆盖性树

定理3.3. 有界Petri网PN是活的当且仅当在RG(PN)中，从顶点M0出 发的每条有向路都走入一个强连通子图，而且在每个这样的强连通子 图中，每个t T至少是一条有向弧的旁标。

定理3.4. 有界Petri网PN的两个变迁t1和t2处于公平关系的充分必要条
件是在RG(PN)的每条有向回路C中， t1是其中的一条弧的旁标当且 仅当t2也是其中一条弧的旁标。


推论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.5. PN是公平Petri网的充分必要条件是在RG(PN)的每条有向回
路C中，每个 t T 都至是C中一条弧的旁标。
？
定理3.4和3.5在无界Petri网中 还成立吗？
一、可达标识图与可覆盖性树

若PN不是有界网，则R(M0)是一个无限集合，无法画出PN的可达标识图。 为了用有限形式表达一个有无限个状态的系统的运行情况，引入一个表示无 界量的符号。 具有下述性质： （1）对任意正整数n： > n， n= （2） 当库所pj中的标识数在Petri网的运行过程中趋向于无限增长时，就把标识向 量中的第j个分量改为 ，以此覆盖所有这类标识。
(0,0, ,1)
t3 (1,0, ,0)
一、可达标识图与可覆盖性树
s1 s1

由于无界量的引入，引 起了Petri网运行过程中 的某些信息丢失。具体的
(0,1,0,1) t2
t2
t1 s3 t3 s4
(a)
t2
t1
2
s2
s2 t3 s4
(b)
s3
(1,0,0,1) t1 (0,1, ,1) t3 t2
t3
新 (1,0, ,0) 旧
一、可达标识图与可覆盖性树

定理3.1. PN是有界Petri网当且仅当 （按算法3.1构造的）CT(PN)中，每 个结点的标识向量都不含有分量。 对有界Petri网PN，按照算法3.1构 造出来的树结构称为PN的可达性树 （reachability tree），记为 RT(PN)。
Step4：
4.1： 4.2： 4.3： Step5：
For 每个满足M[t> 的tT Do
计算M[t>M’中的M’； If 从M0 到M的有向路上存在M’’使M’’<M’ Then 找出使M’’(pj)< M’(pj)的分量j，把M’的第j个分量改为； 在CT(PN)中引入一个“新”结点M’，从M到M’画一条有向弧，并把此弧旁标以t； 擦去结点M的“新”标注，返回Step1。