Petri网的基本概念

第一部分Petri网的基本概念提纲网与网系统库所/变迁系统与加权Petri网并发与冲突网与网系统Petri网是一种网状信息流模型，包括库所和变迁两类节点，同时在库所集上添加表示状态信息的托肯分布（标识）库所表示条件、资源、等待队列和信道等变迁表示事件、动作、语句执行和消息发送/接受等一个变迁（事件）有一定数量的输入和输出库所，分别代表事件的前置条件和后置条件库所中的托肯代表可以使用的资源数量或数据Petri网按引发规则使得事件驱动状态的演变，从而反映系统动态运行过程网与网系统p1p2t1t2c1c2t3t4B例：网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}p1p2t1t2c1c2t3t4B网与网系统定义1.3.设N=(P,T;F)为一个网（1）若对xPT，•xx•=Φ，则称N为一个纯网（purenet）。（2）若对x,yPT，(•x=•y)(x•=y•)→x=y，则称N为一个简单网（simplenet）。（3）若pP，|•p|=|p•|=1，则称N为一个T-图（T-Graph）或标识图（markedgraph）。（4）若tT，|•t|=|t•|=1，则称N为一个S-图（S-Graph）或状态机（statemachine）。（5）若t1,t2T(t1≠t2),•t1•t2≠Φ→|•t1|=|•t2|=1，则称N为一个自由选择网（free-choicenet）。（6）若t1,t2T(t1≠t2),•t1•t2≠Φ→•t1=•t2，则称N为一个扩充的自由选择网（extendedfree-choicenet）。网与网系统定义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[tM’,对pP，有()1()()1()MppttMpMppttMp当当否则网与网系统p1p2t1t2c1c2t3t4Bp1p2t1t2p3p1p2t1t2p3一个网系统的全部可能的运行情况由它的基网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,}(正整数集)称为权函数；（3）K:P→{1,2,}(正整数集)称为容量函数；（4）M:P→{0,1,2,}是一个标识，满足pP：M(p)K(p)其中，M0是初始标识；（5）引发规则：（5.1）对于tT，M[t的引发条件（5.2）若M[tM’,对pP，有()(,)()(,)()()(,)(,)()MpWptpttMpWtppttMpMpWtpWptpttMp当当当否则:()(,):()(,)():()(,)(,)()ptMpWptpttMpWtpKppttMpWtpWptKptH2O222例：化学反应的P/T系统H2O库所/变迁系统与加权Petri网p1p2t1t2c1c2t3t4B定义1.4的Petri网P/T系统p1p2t1t2c1c2t3t4B1t2无法引发库所/变迁系统与加权Petri网对于一个库所/变迁系统Σ=(P,T;F,K,W,M0)，若规定pP：K(p)=fF：W(f)=1那么，就变成形如定义1.4给出的网系统（原型Petri网）对于一个P/T系统，如果规定各个库所的容量都为无穷大，即取消库所集上的容量函数而保留有向边集上的权函数，就得到一种介于原型Petri网和P/T系统之间的网系统模型Σ=(P,T;F,W,M0)，称这种模型为加权Petri网（weightedPetrinet）P/T系统并不比原型Petri网具有更强的模拟能力，凡是可以用P/T系统对其建模的实际系统，也可以用原型Petri网对其建模。每一个P/T系统都可以转换为一个行为等效的Petri网库所/变迁系统与加权Petri网K(p)=2p容量限制ptt权函数p2pt2p等价的原型Petri网pt提纲网与网系统库所/变迁系统与加权Petri网并发与冲突并发与冲突定义1.6.设PN=(P,T;F,M0)是一个Petri网，t1和t2是PN中的两个变迁。如果PN的一个标识M使得M[t1且M[t2，那么若M[t1M1→M1[t2且M[t2M2→M2[t1则称t1和t2在M并发，记为M[{t1,t2}。如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生都不会使另一个失去发生权，则称这两个事件在该状态下处于并发并发不能简单地理解为“同时发生”，而是指事件之间因果上的无依赖性。按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关并发与冲突定义1.7.设PN=(P,T;F,M0)是一个Petri网，t1和t2是PN中的两个变迁。如果PN的一个标识M使得（1）M[t1但M[t2；（2）M[t1M1→M1[t2则称t1和t2存在顺序关系。p1p2t1t2p4p6p5t3t4p3p0t0t5并发与冲突定义1.8.设PN=(P,T;F,M0)是一个Petri网，t1和t2是PN中的两个变迁。如果PN的一个标识M使得M[t1且M[t2，那么若M[t1M1→M1[t2且M[t2M2→M2[t1则称t1和t2在M冲突。冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正是外界环境可以对其施加控制（加以选择）之处。并发与冲突t2t1t3t4p1p2p3t3和t4并发t2t1t3t4p1p2p3t1和t2冲突并发和冲突的示例t2t1t3t4p1p2p3控制装置t2t1p1p2p3p4p5t1和t2不是冲突，而是并发关系并发与冲突混惑的示例t2t1t3p1p2p3p4p5t2t1t3p1p2p3p4p5存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便于对系统施加外部控制，在建立实际系统的Petri网模型时，应尽量避免出现混惑。混惑同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失，如（1）所示。系统在某些状态下存在并发，并发事件中不同事件的发生，使得系统可能存在冲突，也可能不出现冲突，如（2）所示。