第一部分 petri网的基本概念.ppt

第一部分petri网的基本概念 提纲 网与网系统库所 变迁系统与加权petri网并发与冲突 网与网系统 petri网是一种网状信息流模型 包括库所和变迁两类节点 同时在库所集上添加表示状态信息的托肯分布 标识 库所表示条件 资源 等待队列和信道等变迁表示事件 动作 语句执行和消息发送 接受等一个变迁 事件 有一定数量的输入和输出库所 分别代表事件的前置条件和后置条件库所中的托肯代表可以使用的资源数量或数据petri网按引发规则使得事件驱动状态的演变 从而反映系统动态运行过程 网与网系统 例 网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 网与网系统 定义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 t m 对p p 有 网与网系统 p1 p2 t1 t2 c1 c2 t3 t4 b 一个网系统的全部可能的运行情况由它的基网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 t m 对p p 有 t h2 o2 2 2 例 化学反应的p t系统 h2o 库所 变迁系统与加权petri网 定义1 4的petri网 p t系统 t2无法引发 库所 变迁系统与加权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网 提纲 网与网系统库所 变迁系统与加权petri网并发与冲突 并发与冲突 定义1 6 设pn p t f m0 是一个petri网 t1和t2是pn中的两个变迁 如果pn的一个标识m使得m t1 且m t2 那么若m t1 m1 m1 t2 且m t2 m2 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 t1 m1 m1 t2 则称t1和t2存在顺序关系 并发与冲突 定义1 8 设pn p t f m0 是一个petri网 t1和t2是pn中的两个变迁 如果pn的一个标识m使得m t1 且m t2 那么若m t1 m1 m1 t2 且m t2 m2 m2 t1 则称t1和t2在m冲突 冲突关系描述了系统的非确定性 在某情况下有两个 或多个 事件都有权发生 但在实际运行过程中 只有一个能真正发生 系统存在冲突之处 正是外界环境可以对其施加控制 加以选择 之处 并发与冲突 t3和t4并发 t1和t2冲突 并发和冲突的示例 控制装置 t1和t2不是冲突 而是并发关系 并发与冲突 混惑的示例 存在混惑的网系统不是好的系统模型 因为在这种网系统的运行中 冲突是否出现