当前课程知识点:Petri网:模型、理论与应用 > 第三章 Petri网 > 3-3 基本网(EN)系统 > 第一部分
我们要从这个基本网系统
就是这个EN系统来开始
我们的介绍
网系统的介绍
这个基本网系统它定义就是这样的
是一个四元组
前面这三个元素B E F
构成一个有向网
有向网我们知道是怎么定义的
今天不重复了
我们原来有向网是用S T F来表示的
为什么今天这里这个有向网
用B E F 来表示呢
B在德文里面呢
是德文里面条件的第一个字母
然后这个E呢是事件
凡是在第一个层次
因为它的状态都是条件
因此它的那个translation
只跟条件有关系
所以我们把这个要么成真
要么不成真的状态元素叫做条件
只跟条件有关的变迁叫做事件
所以就用B E来表示
F还是一样的还是流关系
这个Cin是什么呢
Cin是它的初始状态
就这个Cin这个Cin是什么呢
是它的一个所有条件的一个子集
它是初始状态表示什么呢
这个子集里面的
所有的条件都是成真的
不在这个子集里面的条件
都是不成真的
这个呢就叫做它的初始情态
这个词呢就是case我翻译成情态
因为case你不能把它翻译成情况
不像一个学术词汇
你也不能翻译成状态呢
它又不能体现这个条件特征
所以我给它翻译成情态
是情况又是状态
这都是我翻译的 叫做情态
在EN系统里面的状态
叫做一个情态
这个2的B次方呢是B的幂集和
就是B的所有子集的集合
我不知道大家理解不理解
为什么用2的B次方
来表示这个幂集合
其实这个也很简单
你把一个有限集的元素排成一个队
凡是这个子集里面有的
就用1来表示
这个子集里面没有的元素
就用零来表示
这样一来呢它就变成一个二进制的数
那么二进制的数一共有多少个呢
这B里面有多少个元素
它就有就是2的那么多次方那么多个
所以我们用2的B次方
来表示B的幂集合
这个B里面的元素叫做条件
是因为它只有两种状态
要么有token这个状态成真
这个条件成真
要么没有token
这个条件呢就不成真
然后事件刚才我说了
它是只跟条件有关的变迁就叫做事件
那么这个Cn我刚才也说了
是由成真的条件组成的这个条件集合
这就是这个EN网系统的四部分
它的含义
既然是个系统
那么我们就这个系统就要发生变化
那么这个变化它的规律是什么呢
它的规则是什么呢
一个事件什么时候
什么状态下 什么情态下
能够发生呢这就是
我们先不管这个情态
先把这个B的任何一个子集
就叫做一个丛
叫做constellation
这个丛我们看在一个丛底下
一个事件是不是有发生权
假定E是一个事件
在这个丛有发授权的定义是什么呢
就是写成这个样
这叫做它这个e在c有发生权
它的发生权是这样定义的
如果我们定义过了
什么叫做一个变迁元素的前集
如果这个变迁元素的前集都成真
就是包含在这个c里面
c不是这个表示的是
有token的那些条件吗
所以这就表示它的前集全都成真
它的后集不成真
所有的元素条件都不成真
那么在这样的情态下
这个e呢就有发生权
有了发生权以后它就又会发生
那么发生以后
会得到什么样的后继呢
它会把一个c这个情态
变成什么情态呢
就变成C′
C′是怎么定义呢
就是这么定义的
C′就是把原来成真的条件
全都token拿掉不成真了
把它的后继里面
原来不成真的那些条件
全都加上token就成真了
所以这就是发生权
和发生的后果它的后继
就是这么定义的
好 这我们看一个例子
这就是刚才我们只给了
这个半形式化的定义
用的是符号四元组
那么这个呢就是它的图形表示
这个图形表示呢
是更直观一些好交流一些
你看我们这里有多少
红的圈都是条件
这个黑的方框就是这个事件
这个三个圆圈里面有红颜色的
我们把它叫做token
就表示资源表示这个是成真的
所以b1这个条件成真
b0这个条件成真
b2这个条件成真
其它的条件都不成真
那么这个呢就是一个基本网系统
它有了有向网作为它的基础
有了这个资源的分布
哪一条件成真告诉你了
那么这就构成了一个网系统
好 刚才我们看了网系统
它是怎么动起来的
然后动的规律是什么
在里面呢我们发现了一些
有趣的事情
我们给它一个解释
就是刚才我们动起来的那个系统
是个什么东西呢
它是可以解释为教堂里面的婚礼
中间那个token
也就是b0它是代表的是神父
旁边那两个b1或b2呢
是一位是新娘一位是新郎
那么这个神父可以跟新郎交流
也可以跟新娘交流
但是只有一个神父
他呢只能跟一个交流
然后再跟另一个
所以这个呢
我们刚才已经说了叫冲突
教堂婚礼我不再重复过多的东西
它的解释就是b0 b1 b2分别是
新人一个新神父一个另外一位新人
然后底下的那个s元素
也就是条件它的含义呢
也已经说过了我这里就不再重复
那么大家回过头来想一想
我在讲petri的那几句话的时候
我们怎么样反过头来
反向的用它那几句话
在这儿你体会体会
我们怎么从教堂
这样一个现实事件
然后抽象成这样的一个网系统
怎么样去粗存精怎么样抽象
怎么样在一个整体
这个pragmatic unit
这样的一个concept底下
然后形成了这么一个网是不是
这么一个网系统
所以你结合这个系统呢
可以回过头来
再去体会petri的那几句话
然后再去体会
我们怎么样来用他那句话
反过来用他那几句话
这是跟应用有关的
就是我把这个网系统
解释成教堂的婚礼了
那么我们看到这里面有
t不变量有s不变量
s不变量就是每一个资源
它的活动轨迹
t不变量呢就是在教堂里面
婚礼举行完一次以后
那么这个在下一场之前
它就是一个回到了初始状态
这就是叫做t不变量
那么以后我们会
仔细的定义这些东西来介绍这些
这是跟应用有关的
就是我结合它的实际物理意义
来发现这些东西
另外一些系统的性质呢
是跟这个解释无关的
它到底是不是描述的教堂婚礼
还是描述的别的东西
跟这个无关的
那个呢叫做结构性质
比方说我们这里面有什么结构性质呢
刚才我说的不变量就是结构性质
你这里是有一个新娘也好
是有三个新娘也好 它都不变
跟这个初始状态
跟你有没有资源没关系
它是一种结构性质
另外我们看到了
在这个里面我们已经解释了
什么叫做顺序发生
什么叫做并行发生
什么叫做冲突 什么叫做冲撞
这个教堂里面这个没有冲撞
但是这个冲撞呢也是一种基本现象
什么叫做并发什么叫做同步等等
那么下面我们来仔细的推敲一下
什么叫做同步
通常我在上课的时候问同学们
什么叫做同步
没有人说他不知道
大家都知道什么叫同步
但是你让他仔细的说
你给我个定义什么叫同步
他就说不清楚了
他只能给你举例子
说比方说卫星跟地球
是同步的等等
都是一些具体的例子
到底什么叫同步搞不清楚
那么我们从这些例子
我们可以看出来
什么叫做同步呢 同步有两种
一种是两组或者两个
当然两组包括一个跟多个了
两组事件他们之间反复发生
呈现出来的规律性就叫做同步
如果有规律就叫同步
如果没有规律就叫不同步
当然这个同步也可以是加权的
比方说刚才我们这个教堂婚礼里面
神父和新人的这个活动
新人之间交换戒指这个活动
他们就是同步的
你要不同步教堂就乱套了对不对
所以这个呢是同步的
那么什么叫做全局同步呢
如果一个系统由于
事件之间的自然依赖关系
不是控制而呈现出来
任何两种事件都有一个同步关系
都是同步的
那么整个系统就叫做
同步的全局同步的
比方说我们这个教堂婚礼
它既是局部同步的
也是全局同步的
那么什么叫做异步呢
异步不是不同步
异步的意思是没有全局控制
我没有一个全局控制就叫做异步
比方说自然界到处都是异步
一亩地里的庄稼怎么长各长各的
异步的没有人能够指挥
说这颗玉米你长两寸
那颗玉米你长三寸不可能的
没有人能够做到这个
所以自然界的规律就是异步的
没有全局控制
所以petri网系统呢
是一个没有任何形式的
全局控制的系统
所以它是一个异步的系统
因为异步所以并发
我们不能说下命令
这个长多少那个长多少
它们各长各的互不相干同时在长
所以这个呢就是并发
所以这个petri网系统呢
是一个异步并发系统
异步就是没有全局控制
没有控制流没有时间控制
没有全局状态控制
那么这个全局控制
我们下面可能会提到
会产生很多不好的效果
比方说我们火车飞机
都是有个时间表
好像是全局用时间可以来控制的
但是你见过真正准时的火车吗
准点到达准点发车的火车吗
你还要问如果你说它准点
你用的是哪个表啊
你觉得准时了
我还觉得它晚了呢对不对
你像飞机也是
飞机的这个延误是经常的事情
为什么自然规律不允许它起飞
你时间规定它
几点几分起飞没有用
它到时候还是起飞不了
所以我们petri网里面
没有这种类型的控制
比方说电梯
现在的电梯如果两部电梯联运的话
往往都是全局状态控制
那么你会发现什么呢
你在那等电梯的时候
另外一部电梯明明从你这过
它就是不停下来接你
你在那生气为什么
这是全局控制的结果
内部电梯原来是可能
比它早到你这儿的
人家控制的也没错
但是呢最后的结果
就是另外一部电梯来了
所以这就是全局控制
带来的不同的后果
所以我们呢
电梯控制系统是我们的一个实例
我下面会讲
所以我们petri网系统里面呢
没有任何形式的全局控制
它是按照事件的自然依赖关系
因果关系然后在那里并发
有因果依赖关系就顺序
没有因果依赖就并发
所以这就是petri网
一个异步并发的系统
那么没有全局控制的另一句话
换个说法就是局部确定
每个事情它能不能发生
都是由它自己 它的局部决定的
不是你控制的
所以这叫局部确定
因为局部确定所以它就并发
每棵树根据它自己的局部
它长多少就是多少
好我们下面看个例子
再进一步的体会
怎么样反向来用petri的那几句话
这个例子是这样
有一个犯人呢
法官来跟他宣布了一条
这个让他有机会
获得自由的这个规定
说呀在下个礼拜
告诉他我们已经决定了
在下个礼拜之内
某一天把你处死
但是给你一条生路
这条生路是什么呢
如果你能够猜出来
到底是哪一天
比方说明天执行死刑
这是法官只有法官的决定
你提前一天猜中了
说你明天执行死刑
那么法官就把你放了
你猜中了就把你放走
如果你猜不中
包括猜错了或者不猜
那么就执行死刑了
但是他只能猜一次
你不能天天猜
说今天来我猜明天
明天来我就猜后天那不行
那你肯定猜中只能猜一次
这个实际问题
我们怎么用petri网来描述
这个犯人很落伍啊
他一想这肯定不会是礼拜天处死
因为如果是礼拜天处死
我已经活着到了礼拜六了
那么我肯定就猜中了
只有一天了嘛
所以礼拜天不可能
他想如果礼拜天
不可能是处死的日子
那就礼拜六是最后一天
那么礼拜六是最后一天
我就活到星期五了 活到星期五
那不是星期六也不行了吗
所以他越想这个法官没办法处死我
他就不猜了
结果呢执行死刑处死了
错在哪里呢
我们能不能把这个犯人的
这个活动规律建一个模型
来帮他分析他到底错在哪里呢
当然如果他已经处死以后
我们来帮他分析也没用了
他也听不见了
如果我们能够事前
他如果学了petri网的课
那么他就可能
不会犯这样的错误了对不对
结果他被处死了他自己乐观的以为
哪一天都处死不了
所以呢结果他就处死了
到底错在哪里呢
好 刚才我们分析了
这个哪些是关键性的这个事件
哪些是关键性的状态
那么我们再总结一些
给它用个符号来表示
那么就是这样
这个i呢就一共一个礼拜七天嘛
这个i就是礼拜一到礼拜七
ati呢就是犯人在周i的前一天
他的状态
比方说那个at1就是他在
那个前一周的礼拜天
他是处在这个状态等等
这个di呢就是法官决定
下一天要处死他
这个gi呢是犯人猜
说第二天要处死
只有当di或gi同时有token的时候
这个犯人才猜中了他就自由了
那么如果这两个不是同时有
或者猜错那就或者不猜
那么就会被处死
这个di di′呢
di′是什么呢
就是表示法官呢决定第二天不处死
这个gi′就是犯人猜
第二天不处死
那么所以一共只能猜一次
一共也只能够
决定执行死刑只能有一天
所以这个这里面呢
这个di里面只能有一个token
gi里面7个只能有1个token一样
这ei呢就是表示执行了
这个e呢就是execute it
这个ri呢就是释放了
这是released
那么有了这些符号以后
我们下面呢就来看看这个图形
这个网表示
就表示成这样了
表示成这样以后我们看
犯人呢一共有三个可能的行为
关键性的行为
我们不关心他那些
零七八碎的活动
一个就是刚才讲了
d1里面有token
表示法官决定周一就是下一天
就处死他了
那么g1′里面没有token
这就表示他没猜
那么既然决定处死你又没猜
他就猜错了所以就执行了
下面这个r1呢就是
d1里面有token刚才讲了
g1里面也有一个token
他决定是哪一天处死
法官猜的也是那一天
然后就自由了释放了
如果没有决定处死
那么不管这个犯人猜了没有
他都会过渡到第二天
所以只要法官不决定处死他
他就会到这一天
既然token在这儿这就没有
这儿没有他就会
这个也不能执行这也不能执行
所以他就会到下一天了
好 这个也是一样的这是第二天
一共呢一共有七天
所以这就是一个简单的
petri网的模型
描述的是这个犯人
在这个七天里面可能的活动
我为什么说可能呢
因为他可能礼拜三
就会执行死刑了
所以后面呢没他的事儿了
但是我们描述的呢是七天
那么回过头来我们要问
到底犯人犯的是什么错误呢
他为什么会那么自信的
就以为他自己不可能被处死呢
不错他说的前提不错
星期天是最后一天
如果他活到星期六他能猜中了
前提是他前面都不猜
礼拜一到礼拜五他都不猜没猜
他活到了星期六
然后法官只能星期天处死
这是第一 他都要前面不猜
第二个条件那就是
法官并没有说一定要处死他呀
所以你猜中就猜中我就放了你么
这有什么关系啊
所以他那个推理的结论
说因为星期天是最后一天
所以法官不会决定那一天处死我
我就不死了
所以法官不会选星期天
这就是一个错误
那么我们从这个网系统来描述呢
如果我们分析这个网
所有可能的状态
他既可能被处死 也可能被释放
这两种可能都有
而他的推理的前提是
我不可能被释放
所以他才说 得出那个结论来
这个呢大家仔细去这个琢磨一下
是不是他的推理错在这个地方
我们这个例子呢就是告诉大家
在复杂的现实社会当中
如果我们要想解决一个问题
我们必须有一个概念
到底我要干什么
我这个模型要干什么
有了这个概念以后
你看围绕着这个概念你去粗存精
找到关键性的状态
然后再抽象成
把它连在一起一个模型
什么又简单又清晰
而正好服务于你的那个目的
这是我们的一个例子
那么刚才那个图
大家是不是觉得有点烦了
这个决定不决定要有两个d1′
猜不猜g1 g1′
这个看起来网元素很多
所以呢就提出了一种
叫做in constraint arc
就是约束弧我给它翻译成约束弧
有人把它翻译成限制弧
我一直把它翻译成约束弧
这个弧是什么呢
就是从s元素到t元素之间的箭头
那个箭头的头
是用一个小圆圈来表示
这就表示这个s元素对这个t元素
有约束的作用它会约束它
所以你看我们那个d或d′呢
就可以合并成一个
那么d1呢如果里面有token
它就有token了如果没有token
就表示他没有决定那一天
所以我们把d1和d1′合在一起
有token表示决定执行死刑
没有token表示
没有决定那一天执行死刑
所以它就是个条件
这样一来呢
我们就可以用约束弧
来描述刚才那个系统
比方说像刚才这是两个
我们现在就用一个就行了
如果有token表示决定要执行死刑
或者执行或者猜中了释放
如果没有决定就
那里面没有token
他才能够过渡到下一天
这个约束弧的作用就是
在这个约束的s元素里面
没有token的时候
这个t元素才能够发生
如果里面有token它就不能发生
所以这样一来呢
我们这个犯人的七天呢
就大大的简化了
这个约束弧呢有人说
petri网加上约束弧以后
它的模拟能力大大的提高了
它就跟图灵机是
模拟力相等的了
但是老P说呢没有必要
这约束弧没有提高它的模拟力
没有约束弧这个petri网呢
跟图灵机的模拟能力也是一样的
我对这种理论性的东西呢
我是兴趣不是太大
所以我也没去求证它
从刚才我们例子里可以看到
没有约束弧我们也描述了
无非那个图那个网复杂一点对不对
有了约束弧我们的图简单一点
但是并没有提高
它的模拟能力对吧
你有约束弧我能描述它
没有用约束弧我同样能够描述
所以这个有兴趣的人
有兴趣的同学可以去自己研究研究
-概述
--Video
-有向网
--Video
-3-1 Petri网定义
--Video
-3-2 Petri网层次系统
--Video
-3-3 基本网(EN)系统
--第一部分
--第二部分
--第三部分
--第四部分
-第三章 Petri网--3-3 基本网系统课后思考题
-3-4 条件-事件(C-E)系统
--Video
-第三章 Petri网--3-4 条件-事件系统课后习题
-3-5 库所-变迁(P-T)系统
--Video
--Video
--Video
--Video
--Video
-3-5 库所-变迁(P-T)系统课后习题--作业
-3-6 网系统层次
--Video
-3-7 高级网系统
--Video
-3-8 化简网系统
--Video
-3-9 非线性网系统
--Video
-3-10 小结
--Video
-4-1 前言
--Video
-4-2 网拓扑
--Video
-4-3 并发论
--Video
-4-4 网逻辑
--Video
-4-5 信息流网
--Video
--Video
-4-6 同步论
--Video
--Video
-4-7 同步论-合同实例
--Video
-4-8 同步论-婚礼教堂实例
--Video
-4-9 同步论 同步器
--Video
-第四章 网论--思考题1
-4-10 实例与方法——电梯控制
--第一部分
--第二部分
--第三部分
--第四部分
-4-11 建模方法论
--Video
-4-12 汉诺塔问题
--第一部分
--第二部分
-第四章 网论--思考题2
-5-1 工作流管理联盟
--Video
-5-2 工作流网(WF_net)
--Video
-5-3 Artifacts
--Video
-5-4 BPMN2.0
--Video
-5-5 学界
--Video
-5-6 业务流程管理(BPM)
--Video
-5-7 BPM建模
--A of ARM
-5-8 流程举例
--第一部分
--第二部分
-5-9 流程之外
--Video
-Petri网小结
--Video
--Video
-6.1 过程挖掘基础
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
-6.2 过程挖掘工具
--Video
--Video
-6.3 过程挖掘算法介绍
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
-6.4 未来研究方向
--Video
-7.1 科研三要素
--Video
-7.2 Program today
--Video
-7.3 Program yesterday
--Video
-7.4 Theory of Programming
--Video
-7.5 A of ARM
--Video
-7.6 R of ARM
--Video
-7.7 M of ARM
--Video
-7.8 OESPA
--Video
-第七章 科研思考--习题
-8.1 树个靶子
--Video
-8.2 八卦与自然
--Video
-8.3 结束语和感谢
--Video
-第八章 总结--习题