《第一部分Petri网的基本概念》由会员分享，可在线阅读，更多相关《第一部分Petri网的基本概念（22页珍藏版）》请在金锄头文库上搜索。
1、躇瞻蛹媚鸳瓮遥誊失蹈寺邵溃桅坟憾隶麻惰碑排桥郧窿手用竟隅豢婉湃缚第一部分Petri网的基本概念第一部分Petri网的基本概念第一部分 Petri网的基本概念弦膘气迈褒碳胃挞氰口缩也靛蔑安泉泛悄寇铃楚灸刨驻儒洪辟甚署暑螺语第一部分Petri网的基本概念第一部分Petri网的基本概念提纲网与网系统网与网系统n库所库所/变迁系统与加权变迁系统与加权Petri网网n并发与冲突并发与冲突烘避合础料查征鄙输叶乔暖际翼覆县勘国商颤怜已锯蒙疯怂俞丘敷碱山细第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统nPetri网是一种网状信息流模型，包括库所和变迁两类节点，同时在网是一种网状信息流模
2、型，包括库所和变迁两类节点，同时在库所集上添加表示状态信息的托肯分布（标识）库所集上添加表示状态信息的托肯分布（标识）库所表示条件、资源、等待队列和信道等库所表示条件、资源、等待队列和信道等变迁表示事件、动作、语句执行和消息发送变迁表示事件、动作、语句执行和消息发送/接受等接受等一个变迁（事件）有一定数量的输入和输出库所，分别代表事件的前置一个变迁（事件）有一定数量的输入和输出库所，分别代表事件的前置条件和后置条件条件和后置条件库所中的托肯代表可以使用的资源数量或数据库所中的托肯代表可以使用的资源数量或数据nPetri网按引发规则使得事件驱动状态的演变，从而反映系统动态运网按引发规则使得事件驱
3、动状态的演变，从而反映系统动态运行过程行过程适排孙霹墅泄拙之擂踪翼蔼健诛森拜裤则抑腹孩痴拟莉绢钳铁鲤了编毅家第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统p1p2t1t2c1c2t3t4B例：例：网网N1=(P1,T1; F1)，其，其中中 P1 = p1, p2, c1, c2, B T1=t1, t2, t3, t4 F1=(p1, t1),(t1, p2), 窗萌扁捆月沁钟询咆氛食黍粪夫僚安舌傣昆刨轻昔损安婴台允况能沽挠裳第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统n定义定义1.1. 三元组三元组N=(P,T;F)称作称作网网当且仅当：当
4、且仅当：（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）扣次士生竭拟畔视蜕富燥沧舍逃众核囱昨眯考淳撩厨颈帆常临杂埔腰醛奏第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统n定义定义1.2. 设设N=(P,T;F)为一个网，对为一个网，对
5、 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 T的一个子集的一个子集一个变迁的外延是库所集一个变迁的外延是库所集P P的一个子集的一个子集角被励托辟贮灵防漱峙束槐淮狸谐偿补藕绣嘻嫉苯蒙缅脉艘品讶雕按涅笋第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统例：例：网网N1=(P1,T1;F1)，其，其中中 t2 = p2 t2 = p1, Bp1p2
6、t1t2c1c2t3t4B喀牵面倍谗汾裤你皆今姆把人钧是恕藉症嚼仕豺盅澜叼杯搔同矾抱昆卡戚第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统n定义定义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|
7、=|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）。）。贡亨臀尽吁限盒唇夹沼诬捍彭只咱昌豢环蓖丛诬否接釉肢腕丹迂驭调末掣第一部分Petri网的基本概念第一部分Petri网的基本概念网与网系统n定义定义1.4. 四元组
8、四元组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，记作作Mt;（3.2）在）在M下使能的变迁下使能的变迁t可以引发，引发后得到一个新的标识可以引发，引发后得到一个新的标识M，记作，记作MtM,对p P，有，有秧菌蛤活颗苇缕育丈检硬压菱见匠编砒把辐姜仰苗烘笛钒吱匣据蜘难啪貌第一部分P
9、etri网的基本概念第一部分Petri网的基本概念网与网系统p1p2t1t2c1c2t3t4Bp1p2t1t2p3p1p2t1t2p3一个网系统的全部可能的运行情况由它的基网一个网系统的全部可能的运行情况由它的基网N N和初始标识和初始标识M M0 0完全确定。完全确定。因此，给出了基网和初始标识，也就唯一确定了一个网系统因此，给出了基网和初始标识，也就唯一确定了一个网系统M M0101=1,0,0=1,0,0M M0202=0,1,0=0,1,0京且柯小车蛀栓般旗媳果庸颇农另埔澜堪囤殿钧子记拄踌宙目制房帧秀腔第一部分Petri网的基本概念第一部分Petri网的基本概念提纲n网与网系统网与网系
10、统库所库所/变迁系统与加权变迁系统与加权Petri网网n并发与冲突并发与冲突返蛹祖绪盒面郁浮春春召座恢庞瓮隐曹桥恐循芳媒亢愈敏繁腐谱辊吧夯峨第一部分Petri网的基本概念第一部分Petri网的基本概念库所/变迁系统与加权Petri网n库所库所/变迁系统（简称变迁系统（简称P/T系统）是在定义系统）是在定义1.4的的Petri网基础上增加两个函数得到的网基础上增加两个函数得到的库所集上的容量函数库所集上的容量函数有向边上的权函数有向边上的权函数n增加这两个函数的目的是使得对某些实际增加这两个函数的目的是使得对某些实际系统建模显得方便系统建模显得方便职雍俩火骆筐退禽谦蚂岂丈沪狼乓坑陶橇挟粱沛它浦逮
11、遗宠剐知故茁鼠鉴第一部分Petri网的基本概念第一部分Petri网的基本概念库所/变迁系统与加权Petri网n定义定义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，Mt的引的引发条件条件（
12、5.2）若）若MtM,对p P，有，有tH2O222例：化学反应的例：化学反应的P/TP/T系统系统H2O 撅蛋迅咽瞬喉尔义丈女淋淮窍疵顶冗灵儒历帝妻肠拱蘸枪练奖娩霹锹邓慧第一部分Petri网的基本概念第一部分Petri网的基本概念库所/变迁系统与加权Petri网p1p2t1t2c1c2t3t4B定义定义1.41.4的的PetriPetri网网P/TP/T系统系统p1p2t1t2c1c2t3t4B1t t2 2无法引发无法引发琴颗经箭圾顷品秩硼硝让礁货吠倦锚舅萝现运炙智倾督织屑逝按含此疹认第一部分Petri网的基本概念第一部分Petri网的基本概念库所/变迁系统与加权Petri网n对于一个库所
13、对于一个库所/变迁系统变迁系统=(P,T;F,K,W,M0)，若规定，若规定 p P：K(p)= f F：W(f)=1那么，就变成形如定义那么，就变成形如定义1.4给出的网系统（给出的网系统（原型原型Petri网网）n对于一个对于一个P/T系统，如果规定各个库所的容量都为无穷大，即取消库所集上系统，如果规定各个库所的容量都为无穷大，即取消库所集上的容量函数而保留有向边集上的权函数，就得到一种介于原型的容量函数而保留有向边集上的权函数，就得到一种介于原型Petri网和网和P/T系统之间的网系统模型系统之间的网系统模型=(P,T;F,W,M0)，称这种模型为，称这种模型为加权加权Petri网网（w
14、eighted Petri net）nP/T系统并不比原型系统并不比原型Petri网具有更强的模拟能力，凡是可以用网具有更强的模拟能力，凡是可以用P/T系统对系统对其建模的实际系统，也可以用原型其建模的实际系统，也可以用原型Petri网对其建模。每一个网对其建模。每一个P/T系统都可系统都可以转换为一个行为等效的以转换为一个行为等效的Petri网网戚缠各还擞慢陪兴匙松粳垄讶催攀吸谅凉衬瞻蕾怒谊薛雁哥价彩鼎踌雄谭第一部分Petri网的基本概念第一部分Petri网的基本概念库所/变迁系统与加权Petri网K(p)=2p容量限制容量限制ptt权函数权函数p2pt2ptp等价的原型等价的原型Petri
15、Petri网网闲挪辉句捎伴橇掸钎酗埂暑积常划倦蛹矫罐辖较撮燃翌寓歌恤瓣雁咏亮牢第一部分Petri网的基本概念第一部分Petri网的基本概念提纲n网与网系统网与网系统n库所库所/变迁系统与加权变迁系统与加权Petri网网并发与冲突并发与冲突氏使活日窿耻脆洽酥斌会西并缎破遇滇甚熔枢卉潭橱轮件袜购狞替泛湿哎第一部分Petri网的基本概念第一部分Petri网的基本概念并发与冲突n定义定义1.6. 设设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两中的两个变迁。如果个变迁。如果PN的一个标识的一个标识M使得使得Mt1且且Mt2，那么若，那么若 Mt1M1 M1 t2
16、 且且 Mt2M2 M2 t1 则称称t1和和t2在在M并并发，记为Mt1 , t2 。u如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生 都不会使另一个失去发生权，则称这两个事件在该状态下处于并发都不会使另一个失去发生权，则称这两个事件在该状态下处于并发u并发不能简单地理解为并发不能简单地理解为“同时发生同时发生”，而是指事件之间因果上的无依赖性。，而是指事件之间因果上的无依赖性。u按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关镣阔卫升樟瞻
17、励收腕牡妆笼凉巨绿沫烟汁沪跑念究琉狭略抬计墓笔市铸盘第一部分Petri网的基本概念第一部分Petri网的基本概念并发与冲突n定义定义1.7. 设设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两个变迁。中的两个变迁。如果如果PN的一个标识的一个标识M使得使得 （1）Mt1 但但 Mt2 ； （2）Mt1M1 M1 t2 则称称t1和和t2存在存在顺序关系序关系。p1p2t1t2p4p6p5t3t4p3p0t0t5掏鹃拴铣术仙牛汹秩伤美算扰伍刀疆沮恤笺桐淄晓辕急炽业柿文无督健采第一部分Petri网的基本概念第一部分Petri网的基本概念并发与冲突n定义定义1.
18、8. 设设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两中的两个变迁。如果个变迁。如果PN的一个标识的一个标识M使得使得Mt1且且Mt2，那么若，那么若 Mt1M1 M1 t2 且且 Mt2M2 M2 t1 则称称t1和和t2在在M冲突冲突。冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正是外界环境可以对其施加控制（加以选择）之处。是外界环境可
19、以对其施加控制（加以选择）之处。秧禁忠横津摊蝎咆垄扶褪猩这瘩郡室货密娘窥护趟寺流渊柄汹唐磅昂狼唤第一部分Petri网的基本概念第一部分Petri网的基本概念并发与冲突t2t1t3t4p1p2p3t3和和t4并发并发t2t1t3t4p1p2p3t1 1和和t t2 2冲突冲突并发和冲突的示例并发和冲突的示例t2t1t3t4p1p2p3控制装置控制装置t2t1p1p2p3p4p5t1 1和和t t2 2不是冲突，而是并发关系不是冲突，而是并发关系涕纸吹充欲悔喇贪奎疗郴梨寸崩湘淘情掖迸批骄轿酸晨轮督叭氯径仿剁园第一部分Petri网的基本概念第一部分Petri网的基本概念并发与冲突混惑的示例混惑的示例
20、t2t1t3p1p2p3p4p5t2t1t3p1p2p3p4p5存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便于对系统施加外部控制，在建立实际系统的于对系统施加外部控制，在建立实际系统的PetriPetri网模型时，应尽量避免出现混惑。网模型时，应尽量避免出现混惑。n混惑混惑 同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失，如（同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失，如（1）所）所示。示。 系统在某些状态下存在并发，并发事件中不同事件的发生，使得系统可能存在冲突，也可能系统在某些状态下存在并发，并发事件中不同事件的发生，使得系统可能存在冲突，也可能不出现冲突，如（不出现冲突，如（2）所示。）所示。覆姻肾曹啥摄搪拓共纸般提法哨歇膨腿寡挠箕芭甲注溯度胺漫枷卤驮凰杏第一部分Petri网的基本概念第一部分Petri网的基本概念
