第十一章petri网.doc

PETRI网
本章研究Petri网及其在操作系统中的应用。
包(bag)
一个包(bag)是某个定义域上的元素集合,但是包不像集合,它允许元素的多次出现。一个元素或者是一个集合中的元素,或者不是一个集合中的元素。在包理论中,一个元素可以在一个包中0次(不在包中),或一次,两次,或任意规定次数。
例1。考虑在域{a,b,c,d}上的下列包:
B1={a,b,c} B4 = {a,a,a}
B2 = {a} B5 ={a,a,a,b,b,c,d,d}
B3 = {a,b,c,c} B6 = {a,b,c,c}
某些包是集合,例如,B1和B2,,和集合一样,元素的次序是不重要的。所以B3和B6是相同包(有序包是序列)。
包的元素关系
定义1 一个元素x在一个包B中的出现次数为#(x, B)。
对所有的x和B#(x, B)≥0。若#(x, B)>0,则元素x是包B的一个成员,标志为x∈B。类似地,若#(x, B)=0,则元素x不是包B的一个成员,xÏB。
我们定义空包φ为没有元素的包。
包的运算
在包上定义四个运算。对两个包A和B定义:
包联合 A∪B #(x, A∪B )=max(#(x,A),#(x,B))
包交 A∩B #(x, A∩B )=min (#(x,A),#(x,B))
包和 A+B #(x,A+B)= #(x,A)+#(x,B)
包差 A-B #(x,A-B)= #(x,A)-#(x, A∩B )
包的联合,交,及和满足交换律和结合律。此外,成立下列包含关系:
A∩B ÍA Í A∪B
A-B Í A Í A+B
包A的基数(cardinality)|A|是包中元素出现总数:
|A| =
联合与和之间的差别显然是
| A∪B |≤|A| + |B|
|A+B| = |A| + |B|
包的包含和相等
如果一个包A的每个元素也是包B的元素,并且至少有那么多次,即包A是包B的子包,标志为A Í B。A ÍB当且仅当对所有x满足#(x, A) ≤#(x, B)。
如果对所有x,#(x, A) = #(x, B),则两个包相等A=B。
由上述定义,我们可以立即得到A = B当且仅当A Í B且B Í A。
对所有包B,成立φÍ B 。
A = B蕴涵|A| = |B|。
A Í B蕴涵|A|≤|B|。
如果A Í B且A ¹ B,则称包A被严格地包含在包B中。记为A Ì B。
注意,A Ì B蕴涵|A| < |B|,但不能得到#(x, A) < #(x, B)。例如,A={a,b},B={a,a,b},#(b,A)=#(b,B)
包空间
我们定义一个定义域D作为一个元素集合。从D来构造包。
定义3 包空间Dn是其元素在D中的所有包的集合,使得没有元素出现次数超过n。即对所有B∈Dn成立如下:
⑴若x∈B,则x∈D。
⑵对所有x, #(x, B)≤n。
包空间D∞是D上的所有包的集合,在一个包中,一个元素出现次数无限制。
Parikh映射
对一个有限域D={d1, ..., dn},存在D上每个包B和n-向量f=(f1, ..., fn)之间的一个自然对应,定义为
fi = #(di, B)
这个向量称为Parikh映射。
例如,设D={a,b,c,d}是