Petri网的基本概念.PPT

* * * * * * * * * * * * * * 第一部分 Petri网的基本概念 提纲 网与网系统 库所/变迁系统与加权Petri网 并发与冲突 网与网系统 Petri网是一种网状信息流模型，包括库所和变迁两类节点，同时在库所集上添加表示状态信息的托肯分布（标识） 库所表示条件、资源、等待队列和信道等 变迁表示事件、动作、语句执行和消息发送/接受等 一个变迁（事件）有一定数量的输入和输出库所，分别代表事件的前置条件和后置条件 库所中的托肯代表可以使用的资源数量或数据 Petri网按引发规则使得事件驱动状态的演变，从而反映系统动态运行过程 网与网系统 p1 p2 t1 t2 c1 c2 t3 t4 B 例：网N1=(P1,T1; F1)，其中 P1 = {p1, p2, c1, c2, B} T1={t1, t2, t3, t4} F1={(p1, t1),(t1, p2), ?} 网与网系统 定义1.1. 三元组N=(P,T;F)称作网当且仅当： （1） P?T≠Φ, P?T=Φ; （2） F?(P?T)?(T?P); （3）dom(F)?cod(F)=P?T 其中， dom(F)={x ? P?T | ?y?P?T: (x, y) ?F} cod(F) ={x ? P?T | ?y?P?T: (y, x) ?F} 这里， P表示库所（Place）集合 T表示变迁（Transition）集合 F是网的流关系（Flow） 网与网系统 定义1.2. 设N=(P,T;F)为一个网，对?? x?P?T，令 ?x = {y | y?P?T ? (y, x)?F} x? = {y | y?P?T ? (x, y)?F} 称?x为x的前集或输入集， x?为x的后集或输出集。称?x ? x? 为元素x的外延。 一个库所的外延是变迁集T的一个子集 一个变迁的外延是库所集P的一个子集 网与网系统 例：网N1=(P1,T1;F1)，其中 ? t2 = {p2} t2? = {p1, B} p1 p2 t1 t2 c1 c2 t3 t4 B 网与网系统 定义1.3. 设N=(P,T;F)为一个网 （1）若对?? x?P?T， ?x ? x? =Φ，则称N为一个纯网（pure net）。 （2）若对?? x, y?P?T，(?x= ?y)?(x? =y? ) →x=y，则称N为一个简单网（simple net）。 （3）若?? p?P，|?p|=|p?|=1，则称N为一个T-图（T-Graph）或标识图（marked graph）。 （4）若?? t?T，|?t|=|t?|=1，则称N为一个S-图（S-Graph）或状态机（state machine）。 （5）若?t1,t2 ?T (t1 ≠ t2), ?t1 ? ?t2≠Φ → |?t1|=|?t2|=1，则称N为一个自由选择网（free-choice net）。 （6）若?t1,t2 ?T (t1 ≠ t2), ?t1 ? ?t2≠Φ → ?t1=?t2，则称N为一个扩充的自由选择网（extended free-choice net）。 网与网系统 定义1.4. 四元组PN=(P,T;F,M0)称作Petri网（网系统）当且仅当 （1） N=(P,T;F)为一个网； （2）映射M:P →{0,1,2,?}(非负整数集)称为网N的一个标识，其中，M0是初始标识； （3）引发规则： （3.1）变迁t ?T称为使能的当且仅当： ?? p ? ?t：M(p)?1，记作M[t>; （3.2）在M下使能的变迁t可以引发，引发后得到一个新的标识M’，记作M[t>M’,对p?P，有 网与网系统 p1 p2 t1 t2 c1 c2 t3 t4 B p1 p2 t1 t2 p3 p1 p2 t1 t2 p3 一个网系统的全部可能的运行情况由它的基网N和初始标识M0完全确定。 因此，给出了基网和初始标识，也就唯一确定了一个网系统 M01={1,0,0} M02={0,1,0} 提纲 网与网系统 库所/变迁系统与加权Petri网 并发与冲突 库所/变迁系统与加权Petri网 库所/变迁系统（简称P/T系统）是在定义1.4的Petri网基础上增加两个函数得到的 库所集上的容量函数 有向边上的权函数 增加这两个函数的目的是使得对某些实际系统建模显得方便 库所/变迁系统与加权Petri网 定义1.5. 六元组Σ=(P,T;F,K,W,M0)称作一个库所/变迁网系统，其中 （1） N=(P,T;F)为一个网； （2） W: F →{1,2,?}(正整数集)称为权函数；