Petri网-3.4 C/E 系统与 3.5 P/T 系统

以你之姓@ 2024-04-01 10:43 66阅读 0赞

#### 3.4 C/E 系统 Condition/Event system ####

C/E 系统与 EN 系统的区别是 **C/E 系统没有初始状态**。

∑ = ( B , E ; F , C ) \\sum=(B,E;F,C) ∑=(B,E;F,C) 称为 C/E 系统，即条件/事件系统。其中：

*   B B B， E E E 分别为条件集和事件集
 *   F F F 是流关系
 *   ( B , E ; F ) (B,E;F) (B,E;F) 为有向网
 *  C是完全可达集

C/E 系统是通用网论的基础模型。同步论最初是借助事件正反双向发生定义的。

#### 3.5 P/T 系统（库所/变迁系统） ####

##### 3.5.1 库所/变迁系统定义 #####

*  库所：Place
 *  变迁：Transition

∑ = ( S , T ; F , K , W , M 0 ) \\sum = (S,T;F,K,W,M\_0) ∑=(S,T;F,K,W,M0) 为 P/T 系统，如果  ( S , T ; F ) (S,T;F) (S,T;F) 为有向网。

*   K : S → \{ 1 , 2 , 3 , . . . \} ∪ \{ ∞ \} K:S \\rightarrow \\\{1,2,3,...\\\}\\cup\\\{\\infty\\\} K:S→\{ 1,2,3,...\}∪\{ ∞\} ， S S S 元素的容量函数
 *   ∧ W : F → \{ 1 , 2 , 3 , . . . \} \\wedge W:F \\rightarrow \\\{1,2,3,...\\\} ∧W:F→\{ 1,2,3,...\} ， F F F 上的权函数，资源消耗或产生的量
 *   ∧ M 0 : S → \{ 0 , 1 , 2 , . . . \} \\wedge M\_0:S \\rightarrow \\\{0,1,2,...\\\} ∧M0:S→\{ 0,1,2,...\} ，初始标识（资源初始分布）
 *   ∧ ∀ s ∈ S : M 0 ( s ) ≤ K ( s ) \\wedge \\forall s \\in S: M\_0(s) \\leq K(s) ∧∀s∈S:M0(s)≤K(s)

思考：如何理解  K ( s ) = ∞ K(s)=\\infty K(s)=∞

###### 3.5.1.1 标识：资源分布 ######

定义： M : S → \{ 0 , 1 , 2 , . . . \} M:S \\rightarrow\\\{0,1,2,...\\\} M:S→\{ 0,1,2,...\} 称为  ∑ \\sum ∑ 上的标识，如果  ∀ s ∈ S : M ( s ) ≤ K ( s ) \\forall s \\in S:M(s) \\leq K(s) ∀s∈S:M(s)≤K(s)

##### 3.5.2 变迁规则 #####

![在这里插入图片描述][6a24a932f4704f298c38be7c5abe09ba.png]

###### 3.5.2.1 变迁规则：发生权 ######

t ∈ T t \\in T t∈T， M M M 为  ∑ \\sum ∑ 的标识

定义： t t t 在  M M M 有发生权，记作  M \[ t > M\[t> M\[t> ，如果  ∀ s ∈ . t : M ( s ) ≥ W ( s , t ) ∧ ∀ s ∈ t . : M ( s ) + W ( s , t ) ≤ K ( s ) \\forall s\\in ^.t:M(s) \\geq W(s,t) \\wedge \\forall s \\in t^.: M(s) + W(s,t) \\leq K(s) ∀s∈.t:M(s)≥W(s,t)∧∀s∈t.:M(s)\+W(s,t)≤K(s)

###### 3.5.2.2 变迁规则：后继 ######

若 M \[ t > M\[t> M\[t> ，则  t t t 可以发生， M ′ M' M′ 为  M M M 的后继标识：  
 M ′ ( s ) = \{ M ( s ) − W ( s , t ) i f ( s ∈ . t − t . ) M ( s ) + W ( t , s ) i f ( s ∈ t . − . t ) M ( s ) + W ( t , s ) − W ( s , t ) i f ( s ∈ . t ∩ t . ) M ( s ) i f ( s ∉ . t ∪ t . ) \\begin\{align\*\} \\begin\{split\} M'(s)= \\left \\\{ \\begin\{array\}\{ll\} M(s)-W(s,t) & if(s\\in^.t-t^.)\\\\ M(s)+W(t,s) & if(s\\in t^.-^.t)\\\\ M(s)+W(t,s)-W(s,t) & if(s\\in ^.t \\cap t^.)\\\\ M(s) & if(s\\notin ^.t \\cup t^.) \\end\{array\} \\right. \\end\{split\} \\end\{align\*\} M′(s)=⎩⎨⎧M(s)−W(s,t)M(s)\+W(t,s)M(s)\+W(t,s)−W(s,t)M(s)if(s∈.t−t.)if(s∈t.−.t)if(s∈.t∩t.)if(s∈/.t∪t.)  
后继关系记作  M \[ t > M ′ M\[t>M' M\[t>M′

###### 3.5.2.3 变迁外延，局部确定原理 ######

. t ∪ t . ^.t \\cup t^. .t∪t. 称为变迁  t t t 的外延（extension）

###### 3.5.2.3.1 局部确定原理（普适） ######

*  每个变迁都有它的外延
 *  变迁的发生只依赖其外延，也只改变其外延
 *   ∑ ∩ E n v ( ∑ ) \\sum \\cap Env(\\sum) ∑∩Env(∑) 无冲突

###### 3.5.2.4 广义权函数 ######

W ′ : S × T ∪ T × S → \{ 0 , 1 , 2 , . . . \} W':S \\times T \\cup T \\times S \\rightarrow \\\{0,1,2,...\\\} W′:S×T∪T×S→\{ 0,1,2,...\} 称为  ∑ \\sum ∑ 的广义权函数，如果  ∀ ( x , y ) ∈ S × T ∪ T × S \\forall(x,y)\\in S \\times T \\cup T \\times S ∀(x,y)∈S×T∪T×S  
 W ′ ( x , y ) = \{ W ( x , y ) i f ( x , y ) ∈ F 0 i f ( x , y ) ∉ F \\begin\{align\*\} \\begin\{split\} W'(x,y)= \\left \\\{ \\begin\{array\}\{ll\} W(x,y) & if(x,y)\\in F\\\\ 0 & if(x,y)\\notin F \\end\{array\} \\right. \\end\{split\} \\end\{align\*\} W′(x,y)=\{ W(x,y)0if(x,y)∈Fif(x,y)∈/F

###### 3.5.2.4.1 定义，用广义权函数给出变迁规则 ######

M \[ t > : ⟺ ∀ s ∈ S : M ( s ) ≥ W ′ ( s , t ) ∧ M ( s ) + W ′ ( s , t ) ≤ K ( s ) M \[ t > M ′ : ⟺ M \[ t > ∧ ∀ s ∈ S : M ′ ( s ) = M ( s ) − W ′ ( s , t ) + W ′ ( t , s ) M\[t>: \\Longleftrightarrow \\forall s \\in S: M(s) \\geq W'(s,t) \\wedge M(s) + W'(s,t) \\leq K(s) \\\\ M\[t>M': \\Longleftrightarrow M\[t> \\wedge \\forall s \\in S: M'(s) = M(s) - W'(s,t) + W'(t,s) M\[t>:⟺∀s∈S:M(s)≥W′(s,t)∧M(s)\+W′(s,t)≤K(s)M\[t>M′:⟺M\[t>∧∀s∈S:M′(s)=M(s)−W′(s,t)\+W′(t,s)

这仅仅是技术上的处理，而不是概念上的更新

*  得：广义权函数使变迁规则看上去简洁
 *  失：
    
     *  技术处理，用  W ′ W' W′ 取代  W W W 会失去其物理含义；
     *  用  W ′ W' W′ 取代  W W W 和  F F F ，定义  ∑ = ( S , T ; W ′ , M 0 ) \\sum=(S,T;W',M\_0) ∑=(S,T;W′,M0) ，会失去网结构

###### 3.5.2.5 缺省值及特例的图示 ######

t 1 t\_1 t1 缺省的容量为  ∞ \\infty ∞ ，缺省的权为 1。

![在这里插入图片描述][7888d576930346e0869b145eb5c915c4.png]

t 2 t\_2 t2 不属于 P/T 系统， M 0 ( s 3 ) = 3 > K ( s 3 ) = 2 M\_0(s\_3)=3>K(s\_3)=2 M0(s3)=3>K(s3)=2

![在这里插入图片描述][07e464788df94c4697165bd1f728ff43.png]

t 3 t\_3 t3 属于 P/T 系统，只是不会发生

![在这里插入图片描述][df6ef74db8e24949902185ac1b02c87f.png]

*  对于图上的变迁上没有数字的是 **权函数的缺失值**，一般就是1。
 *  对于图上的容量上没有数字的是 **容量函数的缺失值**，一般就是  ∞ \\infty ∞。

###### 3.5.2.6 容量的物理含义 ######

先举个**教堂婚礼**的例子，如果忽略新郎新娘之间的差别，即从 CE 系统到 P/T 系统。

![在这里插入图片描述][2be365a8b4c4486980c359c95223d530.png]

*  缺点：少了很多具体的描述，比如说 EN 系统原来的冲突消失了。
 *  优点：系统变的简单了。

思考： K ≡ ∞ K \\equiv \\infty K≡∞ 还是  
 \{ K ( s 1 ) = K ( s 3 ) = K ( s 4 ) = 2 K ( s 0 ) = K ( s 2 ) = K ( s 5 ) = 1 \\begin\{align\*\} \\begin\{split\} \\left \\\{ \\begin\{array\}\{ll\} K(s\_1)=K(s\_3)=K(s\_4)=2\\\\ K(s\_0)=K(s\_2)=K(s\_5)=1 \\end\{array\} \\right. \\end\{split\} \\end\{align\*\} \{ K(s1)=K(s3)=K(s4)=2K(s0)=K(s2)=K(s5)=1  
就这个例子而言，其实认为它的容量是 2 还是  ∞ \\infty ∞ 都可以，因为都不会影响系统的后继和运行。

###### 3.5.2.7 库所的物理含义 ######

*  可观察的同类资源
    
     *  同类是指在系统中作用相同，如新浪新娘
 *  例子（桶装水和瓶装水不同类）
    
     *  如果要描述的是出门旅游：它们属于不同变迁的外延。
     *  它们参与的变迁不同。
        
         *  对于桶装水，需要把水倒到瓶装水，然后饮用。
         *  对于瓶装水，直接可以饮用。

###### 3.5.2.8 变迁的物理含义 ######

*  可观察的资源消耗和新资源的产生
    
     *  有确定不变的观察结果，不因观察者或观察方式而改变，包括质变和量变。
     *  原子性：不中断，无中间状态。中断属于意外。
 *  网系统只描述正常变化，不描述意外。观察意外会得到不确定的结果，且不能枚举。

思考：库所元素和变迁元素是否一目了然？

并没有想象中的一目了然，需要分清楚边界和切口。

##### 3.5.3 EN 系统  ⊂ \\subset ⊂ P/T 系统 #####

EN 系统  ∑ = ( B , E ; F , c i n ) \\sum = (B,E;F,c\_\{in\}) ∑=(B,E;F,cin) 是 P/T 系统的特例。

*  其中  K ≡ 1 K\\equiv 1 K≡1 ， W ≡ 1 W \\equiv 1 W≡1 ， M 0 M\_0 M0 是  c i n c\_\{in\} cin 的另一种表示

∀ b ∈ B : \{ M 0 ( b ) = 1 i f ( b ∈ c i n ) M 0 ( b ) = 0 i f ( b ∉ c i n ) \\begin\{align\*\} \\begin\{split\} \\forall b \\in B : \\left \\\{ \\begin\{array\}\{ll\} M\_0(b)=1 &if(b\\in c\_\{in\})\\\\ M\_0(b)=0 &if(b\\notin c\_\{in\}) \\end\{array\} \\right. \\end\{split\} \\end\{align\*\} ∀b∈B:\{ M0(b)=1M0(b)=0if(b∈cin)if(b∈/cin)

###### 3.5.3.1 练习 ######

将 EN 系统上定义的基本现象移植到 P/T 系统上，变迁（事件）和变迁发生权。

###### 3.5.3.1.1 例子1 ######

![在这里插入图片描述][886a9fcfc5fe4af7a4a60596a4682cbb.png]

*   t 1 t\_1 t1 、 t 2 t\_2 t2 并发
 *   t 1 t\_1 t1 、 t 2 t\_2 t2 分别和自己并发

###### 3.5.3.1.2 例子2 ######

![在这里插入图片描述][4238831ed84a4ceeb00bf2ba13498b0d.png]

*   t 1 t\_1 t1 、 t 2 t\_2 t2 、 t 3 t\_3 t3 两两并发
 *   t 2 t\_2 t2 和自己并发
 *  三者不能并发

###### 3.5.3.2 并发步 ######

在同一标识可以并发的一个或多个变迁，称为该标识上的一个并发步。例如：

*  在 `3.5.3.1.1 例子1` 中  \{ t 1 , t 2 \} \\\{t\_1,t\_2\\\} \{ t1,t2\} 是并发步，写成  t 1 + t 2 t\_1+t\_2 t1\+t2 。同时， 2 t 1 2t\_1 2t1、 2 t 2 2t\_2 2t2 也是并发步。
 *  在 `3.5.3.1.2 例子2` 中  t 1 + t 2 t\_1+t\_2 t1\+t2 ， t 1 + t 3 t\_1+t\_3 t1\+t3 ， t 2 + t 3 t\_2+t\_3 t2\+t3 ， 2 t 2 2t\_2 2t2 。

###### 3.5.3.3 可达标识集 ######

###### 3.5.3.3.1 定义 ######

设  M M M 为  ∑ \\sum ∑ 的任一标识，用  \[ M ⟩ \[M \\rangle \[M⟩ 表示符合下列条件的**最小**集合

*   M ∈ \[ M ⟩ M \\in \[M \\rangle M∈\[M⟩
 *   t ∈ T ∧ M ′ ∈ \[ M ⟩ ∧ M ′ \[ t ⟩ M ′ ′ → M ′ ′ ∈ \[ M ⟩ t\\in T \\wedge M' \\in \[M \\rangle \\wedge M'\[t \\rangle M'' \\\\ \\rightarrow M'' \\in \[M \\rangle t∈T∧M′∈\[M⟩∧M′\[t⟩M′′→M′′∈\[M⟩

定义： \[ M 0 ⟩ \[M\_0 \\rangle \[M0⟩ 称为  ∑ \\sum ∑ 的可达标识集

###### 3.5.3.3.2 自然语言定义 ######

可达标识集  \[ M 0 ⟩ \[M\_0 \\rangle \[M0⟩ 的自然语言定义：

*  从  M 0 M\_0 M0 开始，包括  M 0 M\_0 M0
 *  经有限步变迁发生
 *  能到达的
 *  所有标识的集合

思考：怎么证明？

###### 3.5.3.4 变迁序列 ######

σ = τ 1 τ 2 . . . τ n \\sigma = \\tau \_1 \\tau \_2 ... \\tau \_n σ=τ1τ2...τn 称为  ∑ \\sum ∑ 的变迁序列。如果对  i = 1 , 2 , . . . , n i=1,2,...,n i=1,2,...,n ， τ i ∈ T ∧ ∃ M i ∈ \[ M 0 ⟩ : M i − 1 \[ τ i ⟩ M i \\tau \_i \\in T \\wedge \\exists M\_i \\in \[M\_0 \\rangle : M\_\{i-1\}\[\\tau \_i \\rangle M\_i τi∈T∧∃Mi∈\[M0⟩:Mi−1\[τi⟩Mi，即  M 0 \[ τ 1 ⟩ M 1 \[ τ 2 ⟩ M 2 . . . M n − 1 \[ τ n ⟩ M n M\_0 \[\\tau \_1 \\rangle M\_1\[ \\tau \_2 \\rangle M\_2... M\_\{n-1\}\[\\tau \_n \\rangle M\_n M0\[τ1⟩M1\[τ2⟩M2...Mn−1\[τn⟩Mn

M n M\_n Mn 称为  σ \\sigma σ 的后继标识，记作  M 0 \[ σ ⟩ M n M\_0\[\\sigma \\rangle M\_n M0\[σ⟩Mn

变迁序列是从  M 0 M\_0 M0 开始可以依次发生的变迁组成的序列，不是任意的变迁组成的序列。

变迁序列可以扩展到无穷序列：

*   σ ′ = τ 1 τ 2 τ 3 . . . \\sigma ' = \\tau \_1 \\tau \_2 \\tau \_3... σ′=τ1τ2τ3... 为无穷序列，如果它的任何有限前缀均为变迁序列，则  σ ′ \\sigma ' σ′ 是（无穷）变迁序列。

###### 3.5.3.5 P/T 系统性质 ######

###### 3.5.3.5.1 活性 ######

关注状态，即  \[ M 0 ⟩ \[M\_0 \\rangle \[M0⟩

*  变迁  t ∈ T t\\in T t∈T 是活的，如果  ∀ M ∈ \[ M 0 ⟩ ∃ M ′ ∈ \[ M ⟩ : M ′ \[ t ⟩ \\forall M \\in \[M\_0 \\rangle \\exists M' \\in \[ M \\rangle : M'\[t \\rangle ∀M∈\[M0⟩∃M′∈\[M⟩:M′\[t⟩ 。
 *   ∑ \\sum ∑ 是活的，如果它的所有变迁都是活的。

###### 3.5.3.5.2 有界性 ######

若存在正整数  k k k ，使得  ∀ M ∈ \[ M 0 > ∀ s ∈ S : M ( s ) ≤ k \\forall M \\in \[M\_0 > \\forall s \\in S:M(s) \\leq k ∀M∈\[M0>∀s∈S:M(s)≤k ，则  ∑ \\sum ∑ 称为有界系统。

*  教堂婚礼系统是活的，以 2 为界。
 *  哲学家系统的网系统是活的，以 1 为界。哲学家就餐问题的图如下：

![在这里插入图片描述][50aa1f91b4d54f55897c1a1c9ec3086f.png]

###### 3.5.3.5.3 公平性 ######

如果不存在无穷变迁序列  σ \\sigma σ 和变迁子集  T 1 T\_1 T1 、 T 2 T\_2 T2 ，使得  \# ( σ , T 1 ) = ∞ ∧ \# ( σ , T 2 ) < ∞ \\\#(\\sigma ,T\_1)=\\infty \\wedge \\\#(\\sigma, T\_2)<\\infty \#(σ,T1)=∞∧\#(σ,T2)<∞，则  ∑ \\sum ∑ 是公平的， 其中  \# ( σ , T i ) \\\#(\\sigma ,T\_i) \#(σ,Ti) 是  T i T\_i Ti 中变迁在  σ \\sigma σ 中出现的次数， i = 1 , 2 i=1,2 i=1,2 。

*  教堂婚礼系统是公平的
 *  不加管理的哲学家系统是不公平的
 *  问题：公平性的定义合理吗？

###### 3.5.3.6 系统进程 ######

状态变迁并重：网系统进程。

###### 3.5.3.6.1 出现网 ######

N = ( B , E ; F ) N=(B,E;F) N=(B,E;F) 称为出现网，如果  N N N 为有向网，且  ( ∀ b ∈ B : ∣ . b ∣ ≤ 1 ∧ ∣ b . ∣ ≤ 1 ) ∧ ( ∀ x ∈ B ∪ E : ( x , x ) ∉ F + ) (\\forall b \\in B:|^.b| \\leq 1 \\wedge |b^.| \\leq 1) \\wedge (\\forall x \\in B \\cup E:(x,x) \\notin F^+) (∀b∈B:∣.b∣≤1∧∣b.∣≤1)∧(∀x∈B∪E:(x,x)∈/F\+)

例子（出现网  N 1 N\_1 N1）：

![在这里插入图片描述][91d12947eb0d4250b668662e64ed575c.png]

*   N 1 N\_1 N1 每个库所至多一条入弧、一条出弧。（产生和消耗）
 *   N 1 N\_1 N1 无环， ( b 2 , b 4 ) ∈ F 2 (b\_2,b\_4)\\in F^2 (b2,b4)∈F2， ( b 1 , b 3 ) ∈ F 5 (b\_1,b\_3)\\in F^5 (b1,b3)∈F5， F + = F ∪ F 2 ∪ F 3 ∪ . . . F^+=F\\cup F^2 \\cup F^3 \\cup ... F\+=F∪F2∪F3∪...

定义：出现网  N N N 是网系统  ∑ \\sum ∑ 的一个进程，如果存在从  N N N 到  ∑ \\sum ∑ 的映射。如下图就是 出现网  N 1 N\_1 N1 的 网系统映射 网系统  ∑ 1 \\sum \_1 ∑1

![在这里插入图片描述][49f48aec684346ffb5db88862f490824.png]

N 1 N\_1 N1 是  ∑ 1 \\sum \_1 ∑1 的一个进程（变迁发生的记录），从  N 1 N\_1 N1 到  ∑ 1 \\sum \_1 ∑1 的映射：

*   b 1 → s 1 b\_1 \\rightarrow s\_1 b1→s1 ， b 2 → s 3 b\_2 \\rightarrow s\_3 b2→s3， b 3 → s 2 b\_3 \\rightarrow s\_2 b3→s2， b 4 → s 4 b\_4 \\rightarrow s\_4 b4→s4， b 5 → s 3 b\_5 \\rightarrow s\_3 b5→s3， b 6 → s 1 b\_6 \\rightarrow s\_1 b6→s1， b 7 → s 2 b\_7 \\rightarrow s\_2 b7→s2
 *   e 1 → t 1 e\_1 \\rightarrow t\_1 e1→t1， e 2 → t 2 e\_2 \\rightarrow t\_2 e2→t2， e 3 → t 1 e\_3 \\rightarrow t\_1 e3→t1

###### 3.5.3.6.2 网系统进程的形式（半形式）定义很复杂 ######

通常只给出  ∑ = ( S , T ; F , M 0 ) \\sum=(S,T;F,M\_0) ∑=(S,T;F,M0) 上的进程定义，即  K ≡ ∞ K\\equiv \\infty K≡∞ ， W ≡ 1 W \\equiv 1 W≡1。

这里最“老”的网系统（Petri 最早的定义，在其博士论文中的定义）。

进程是并发公理基础。

###### 3.5.3.7  k < ∞ k<\\infty k<∞ 的物理含义 ######

k ( s ) = 5 k(s)=5 k(s)=5 表示  s s s 有 5 个“空间资源”，或  s s s 的空间至多能容纳 5 个 s s s 类资源（如车库）。例如下图：

![在这里插入图片描述][46ad68ec04d94df8988b2994b4180370.png]

t t t 只能发生一次，再发生会引出  s s s 处的冲撞。

k = ∞ k=\\infty k=∞：空间足够大，不会对变迁发生构成限制。

![在这里插入图片描述][5b7f185bfae6407bb42ac8615ea6d80d.png]

以下就会受到影响：

![在这里插入图片描述][bbec98ca4ae8497596ea662a51543b98.png]

###### 3.5.3.7.1 容量函数的作用 ######

以容量函数而非 token 表示空间资源，体现空间资源与其它资源的本质区别：**被占的空间不能阻止强占，已消耗的资源已不可见**。

引出 “冲撞（contact）” 这一基本现象。熟知空间资源特点后，**S\_补技术**改用 token 表示有限的空间资源， k ≡ ∞ k \\equiv \\infty k≡∞ ，冲撞从系统中消失（并非从现实消失）。

s ′ s' s′ 和  s s s 互为补库所：

*   s ′ . = . s ∧ . s ′ = s . s'^.=^.s \\wedge ^.s'=s^. s′.=.s∧.s′=s.
 *   W ( s ′ , t ) = W ( t , s ) W(s',t)=W(t,s) W(s′,t)=W(t,s)
 *   M ( s ′ ) + M ( s ) = k ( s ) M(s')+M(s)=k(s) M(s′)\+M(s)=k(s)

例如下面的：

![在这里插入图片描述][27ba70ae1f2d4a87aab3a41114686844.png]

##### 3.5.4 代数表示 #####

限于有线网系统  : : : 全局，结构： ∑ = ( S , T ; F , W , M 0 ) \\sum =(S,T;F,W,M\_0) ∑=(S,T;F,W,M0)， K ≡ ∞ K \\equiv \\infty K≡∞， T = \{ t 1 , t 2 , . . . , t n \} T=\\\{t\_1,t\_2,...,t\_n\\\} T=\{ t1,t2,...,tn\}， S = \{ s 1 , s 2 , . . . , s m \} S=\\\{s\_1,s\_2,...,s\_m\\\} S=\{ s1,s2,...,sm\}， W ′ : S × T ∪ T × S → \{ 0 , 1 , 2 , . . . \} W':S \\times T \\cup T \\times S \\\\ \\rightarrow \\\{0,1,2,...\\\} W′:S×T∪T×S→\{ 0,1,2,...\} 为广义权函数。

###### 3.5.4.1 关联矩阵 ######

定义： m × n m \\times n m×n 阶矩阵  A A A 称为  ∑ \\sum ∑ 的关联矩阵。如果  
 A = t 1 t 2 . . . t n s 1 s 2 ⋮ s m ( a ( i , j ) . . . ⋮ ) \\begin\{align\*\} \\begin\{split\} A= \\begin\{array\}\{lc\} \{\}& \\begin\{array\}\{cc\}t\_1&t\_2&...&t\_n \\end\{array\}\\\\ \\begin\{array\}\{c\}s\_1\\\\s\_2\\\\ \\vdots \\\\s\_m\\end\{array\}& \\left(\\begin\{array\}\{cc\} &&&\\\\ &a(i,j)&&\\\\ ...&\\vdots&&\\\\ &&& \\end\{array\}\\right) \\end\{array\} \\end\{split\} \\end\{align\*\} A=s1s2⋮smt1t2...tn⎝⎛...a(i,j)⋮⎠⎞  
其中， a ( i , j ) = W ′ ( t i , s j ) − W ′ ( s j , t i ) a(i,j)=W'(t\_i,s\_j)-W'(s\_j,t\_i) a(i,j)=W′(ti,sj)−W′(sj,ti)。

关联矩阵与  M 0 M\_0 M0 无关，是网系统的结构描述。

###### 3.5.4.1.1 例子  ∑ 1 \\sum \_1 ∑1 ######

![在这里插入图片描述][cef0a7f5a34342038ab5137a395c98d8.png]

∑ 1 \\sum \_1 ∑1 的关联矩阵  
 A = t 1 t 2 h l c r ( − 1 − 1 − 2 − 4 1 0 0 1 ) \\begin\{align\*\} \\begin\{split\} A= \\begin\{array\}\{lc\} \{\}& \\begin\{array\}\{cc\}t\_1&t\_2 \\end\{array\}\\\\ \\begin\{array\}\{c\}h\\\\l\\\\c\\\\r\\end\{array\}& \\left(\\begin\{array\}\{cc\} -1&-1\\\\ -2&-4\\\\ 1&0\\\\ 0&1 \\end\{array\}\\right) \\end\{array\} \\end\{split\} \\end\{align\*\} A=hlcrt1t2⎝⎛−1−210−1−401⎠⎞

###### 3.5.4.1.2 例子  ∑ 2 \\sum \_2 ∑2 ######

![在这里插入图片描述][a85bd8dbc539445286c55c29a2f97ef1.png]

∑ 2 \\sum \_2 ∑2 的关联矩阵  
 A 2 = t 1 t 2 t 3 s 1 s 2 s 3 ( − 1 0 1 − 1 1 − 1 2 − 1 0 ) \\begin\{align\*\} \\begin\{split\} A\_2= \\begin\{array\}\{lc\} \{\}& \\begin\{array\}\{cc\}t\_1&t\_2&t\_3 \\end\{array\}\\\\ \\begin\{array\}\{c\}s\_1\\\\s\_2\\\\s\_3\\end\{array\}& \\left(\\begin\{array\}\{cc\} -1&0&1\\\\ -1&1&-1\\\\ 2&-1&0 \\end\{array\}\\right) \\end\{array\} \\end\{split\} \\end\{align\*\} A2=s1s2s3t1t2t3⎝⎛−1−1201−11−10⎠⎞

###### 3.5.4.2 `S_向量`和`T_向量` ######

*   τ = ( a 1 , a 2 , . . . , a n ) \\tau=(a\_1,a\_2,...,a\_n) τ=(a1,a2,...,an)， a i a\_i ai 为非负整数
 *   σ = ( b 1 , b 2 , . . . , b m ) \\sigma = (b\_1,b\_2,...,b\_m) σ=(b1,b2,...,bm)， b j b\_j bj 为非负整数
 *  分别称为  ∑ \\sum ∑ 的 `T_向量` 和 `S_向量`
 *   τ T = ( a 1 a 2 ⋮ a n ) \\tau ^ T = \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} a\_1\\\\ a\_2\\\\ \\vdots \\\\ a\_n \\end\{array\}\\right) \\end\{array\} τT=⎝⎛a1a2⋮an⎠⎞， σ T = ( b 1 b 2 ⋮ b m ) \\sigma ^ T = \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} b\_1\\\\ b\_2\\\\ \\vdots \\\\ b\_m \\end\{array\}\\right) \\end\{array\} σT=⎝⎛b1b2⋮bm⎠⎞ 分别是  τ \\tau τ 和  σ \\sigma σ 的转置向量。

###### 3.5.4.2.1 状态方程 ######

M = M 0 + A ⋅ τ T M=M\_0+A \\cdot \\tau ^ T M=M0\+A⋅τT 称为  ∑ \\sum ∑ 的状态方程，其中  τ \\tau τ 为任一 `T_向量`， M 0 M\_0 M0 和  M M M 分别是标识的 `S_向量`

命题：设  α = τ 1 , τ 2 , . . . \\alpha = \\tau \_1,\\tau \_2,... α=τ1,τ2,...， τ 1 \\tau \_1 τ1 为  ∑ \\sum ∑ 的任一变迁序列， τ = ( a 1 , a 2 , . . . , a n ) \\tau=(a\_1,a\_2,...,a\_n) τ=(a1,a2,...,an) 是它的 `T_向量` ，即  a i a\_i ai 为变迁  t i t\_i ti 在该序列中出现的次数， i = 1 , 2 , . . . , n i=1,2,...,n i=1,2,...,n ，则  M = M 0 + A ⋅ τ T M=M\_0+A \\cdot \\tau ^ T M=M0\+A⋅τT，其中  M M M 是  α \\alpha α 的后继： M 0 \[ α ⟩ M M\_0\[\\alpha \\rangle M M0\[α⟩M。

###### 3.5.4.2.2 `T-不变量` 和 `S-不变量` ######

**`T-不变量`**

*  若 `T_向量`  τ \\tau τ 满足  M 0 = M 0 + A ⋅ τ T M\_0=M\_0+A \\cdot \\tau^T M0=M0\+A⋅τT，则  τ \\tau τ 称为  ∑ \\sum ∑ 的 `T-不变量`。
 *  若  τ \\tau τ 为  ∑ \\sum ∑ 的 `T-不变量`，则  A ⋅ τ T = θ S T A \\cdot \\tau ^ T=\\theta ^ T\_S A⋅τT=θST，其中  θ S \\theta \_S θS 是分量全为 0 的 `S_向量` 。

**`S-不变量`**

若 `S_向量`  σ \\sigma σ 满足  σ ⋅ A = θ T \\sigma \\cdot A = \\theta \_T σ⋅A=θT ，则  σ \\sigma σ 称为  ∑ \\sum ∑ 的 `S-不变量`。其中  θ T \\theta \_T θT 是分量全为 0 的 `T_向量` 。

**例子**  ∑ 1 \\sum \_1 ∑1

![在这里插入图片描述][45683e48cb904eaa9e28303d079281f5.png]

∑ 1 \\sum \_1 ∑1 的 `S-不变量` 包括：

*   σ 1 = ( 1 , 0 , 1 , 1 ) \\sigma \_1=(1,0,1,1) σ1=(1,0,1,1)
 *   σ 2 = ( 0 , 1 , 2 , 4 ) \\sigma \_2=(0,1,2,4) σ2=(0,1,2,4)
 *   σ 1 ⋅ A 1 = ( 1 , 0 , 1 , 1 ) ⋅ ( − 1 − 1 − 2 − 4 1 0 0 1 ) = ( 0 , 0 ) \\sigma \_1 \\cdot A\_1 = (1,0,1,1)\\cdot \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} -1 & -1\\\\ -2 & -4\\\\ 1 & 0\\\\ 0 & 1 \\end\{array\}\\right) \\end\{array\} = (0,0) σ1⋅A1=(1,0,1,1)⋅⎝⎛−1−210−1−401⎠⎞=(0,0)
 *   σ 2 ⋅ A 1 = ( 0 , 1 , 2 , 4 ) ⋅ ( − 1 − 1 − 2 − 4 1 0 0 1 ) = ( 0 , 0 ) \\sigma \_2 \\cdot A\_1 = (0,1,2,4)\\cdot \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} -1 & -1\\\\ -2 & -4\\\\ 1 & 0\\\\ 0 & 1 \\end\{array\}\\right) \\end\{array\} = (0,0) σ2⋅A1=(0,1,2,4)⋅⎝⎛−1−210−1−401⎠⎞=(0,0)

**例子**  ∑ 2 \\sum \_2 ∑2

![在这里插入图片描述][9f31f5f6d828452e8210f20c2bd490ac.png]

∑ 2 \\sum \_2 ∑2 的不变量包括：

*   σ = ( 1 , 1 , 1 ) \\sigma=(1,1,1) σ=(1,1,1)
 *   τ = ( 1 , 2 , 1 ) \\tau = (1,2,1) τ=(1,2,1)
 *   σ ⋅ A 2 = ( 1 , 1 , 1 ) ⋅ ( − 1 0 1 − 1 1 − 1 2 − 1 0 ) = ( 0 , 0 , 0 ) \\sigma \\cdot A\_2 = (1,1,1)\\cdot \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} -1 & 0 & 1\\\\ -1 & 1 & -1\\\\ 2 & -1 & 0 \\end\{array\}\\right) \\end\{array\} = (0,0,0) σ⋅A2=(1,1,1)⋅⎝⎛−1−1201−11−10⎠⎞=(0,0,0)
 *   A 2 ⋅ τ T = ( − 1 0 1 − 1 1 − 1 2 − 1 0 ) ⋅ ( 1 2 1 ) = ( 0 , 0 , 0 ) A\_2 \\cdot \\tau ^ T = \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} -1 & 0 & 1\\\\ -1 & 1 & -1\\\\ 2 & -1 & 0 \\end\{array\}\\right) \\end\{array\} \\cdot \\begin\{array\}\{lc\} \\left(\\begin\{array\}\{cc\} 1\\\\ 2\\\\ 1 \\end\{array\}\\right) \\end\{array\} = (0,0,0) A2⋅τT=⎝⎛−1−1201−11−10⎠⎞⋅⎝⎛121⎠⎞=(0,0,0)

**练习**

∑ 1 \\sum\_1 ∑1 是鸡兔同笼问题中数鸡（ t 1 t\_1 t1）数兔（ t 2 t\_2 t2）的网表示，请补上  t 1 t\_1 t1 ， t 2 t\_2 t2 可能需要的调整变迁（并发数数，一方太快，导致头或腿剩下）。

找一找教堂婚礼系统的不变量

找一找哲学家系统的不变量，理解 `S-不变量` 和 `T-不变量` 的物理意义。

###### 3.5.4.2.3 求解不变量 ######

\{ A ⋅ X T = θ S Y ⋅ A = θ T \\left \\\{ \\begin\{array\}\{ll\} A \\cdot X^T = \\theta \_S \\\\ Y \\cdot A = \\theta \_T \\end\{array\} \\right. \{ A⋅XT=θSY⋅A=θT 可以求解  T T T 和  S S S 不变量或者验证不变量。其中， X = ( x 1 , x 2 , . . . , x n ) X=(x\_1,x\_2,...,x\_n) X=(x1,x2,...,xn) 和  Y = ( y 1 , y 2 , . . . , y m ) Y=(y\_1,y\_2,...,y\_m) Y=(y1,y2,...,ym) 分别为未知变量 `T_向量` 和 `未知S_向量` 。

###### 3.5.4.2.4 结论 ######

`T-不变量` 和 `S-不变量` 是结构性质，与  M 0 M\_0 M0 无关。

定义：

*  如果  ∑ \\sum ∑ 有非零 `T-不变量` ，则  θ T \\theta \_T θT 也是  ∑ \\sum ∑ 的 `T-不变量` ；否则不是
 *  如果  ∑ \\sum ∑ 有非零 `S-不变量` ，则  θ S \\theta \_S θS 也是  ∑ \\sum ∑ 的 `S-不变量` ；否则不是

命题：

*  `T-不变量`（`S-不变量`）的线性组合也是 `T-不变量`（`S-不变量`）。

##### 3.5.5 通用分析方法 #####

*  可达树与覆盖树算法
 *  求解不变量法
 *  化简法：忽略网结构细节
 *  提高层次法：提高抽象度以减少节点数

###### 3.5.5.1 可达树与覆盖树算法 ######

###### 3.5.5.1.1 例： ∑ \\sum ∑ 如图所示 ######

![在这里插入图片描述][bffa1cc45b2a495ea9ed390691461b59.png]

M 0 = ( 1 , 0 , 0 ) M\_0=(1,0,0) M0=(1,0,0) ， S 1 S\_1 S1、 S 2 S\_2 S2、 S 3 S\_3 S3 的资源数

![在这里插入图片描述][01c90882733845538bf93de457963d4e.png]

若无无穷分支，可达树节点即为  \[ M 0 > \[M\_0> \[M0>

覆盖树算法：为无穷分支“剪枝”

*   M 1 ≤ M 2 M\_1\\leq M\_2 M1≤M2 ，如果  ∀ s ∈ S : M 1 ( s ) ≤ M 2 ( s ) \\forall s \\in S:M\_1(s)\\leq M\_2(s) ∀s∈S:M1(s)≤M2(s)， M 2 M\_2 M2 覆盖  M 1 M\_1 M1
 *   M 1 < M 2 M\_1 < M\_2 M1<M2 ，如果  M 1 ≤ M 2 ∧ ∃ s ∈ S : M 1 ( s ) < M 2 ( s ) M\_1 \\leq M\_2 \\wedge \\exists s \\in S:M\_1(s)<M\_2(s) M1≤M2∧∃s∈S:M1(s)<M2(s)

![在这里插入图片描述][4240e76ec0154e0a8eeb78b79aac6741.png]

最后得到的覆盖树

![在这里插入图片描述][060c65185c3e4481bdfe961a59d39c30.png]

\[ M 0 > \[M\_0> \[M0> 中所有标识均被覆盖树节点覆盖

![在这里插入图片描述][1b11fea0a7034e1bb5933e3ccd8f7ffc.png]

覆盖图： M 2 M\_2 M2 与  M 1 M\_1 M1 重叠，一类叶节点。将覆盖树同一路径上相同节点重叠

![在这里插入图片描述][9067602da8aa4631bbe6b907accdc2ba.png]

可达树，覆盖树，覆盖图，可用以检查验证活性，有界性，公平性及不变量。

*  如例子中的系统是不公平的，不活的，无界的，没有不变量。

###### 3.5.5.2 求解不变量法 ######

###### 3.5.5.3 化简法：忽略网结构细节 ######

###### 3.5.5.4 提高层次法：提高抽象度以减少节点数 ######

[6a24a932f4704f298c38be7c5abe09ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/65d0647c7701490fa50fbe8f99a681dd.png
[7888d576930346e0869b145eb5c915c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8bb7f81215064d2cb36def55445a8a5a.png
[07e464788df94c4697165bd1f728ff43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fc253a1e3b344d48a70325cc8d3fc654.png
[df6ef74db8e24949902185ac1b02c87f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6549d37cf3264185bc55b1902a5109d5.png
[2be365a8b4c4486980c359c95223d530.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9022f5f34ede46a687319fc48af22da9.png
[886a9fcfc5fe4af7a4a60596a4682cbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/79f10a92fa154b23ac47f570703c98b3.png
[4238831ed84a4ceeb00bf2ba13498b0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/83dda917515b49f9bff0a3fa4d0d8ca8.png
[50aa1f91b4d54f55897c1a1c9ec3086f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7044e802f24f43339f46fe6fc66f97d6.png
[91d12947eb0d4250b668662e64ed575c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/44a754529fcc43e885cc3d023e5ffffb.png
[49f48aec684346ffb5db88862f490824.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a1d8f51f9c6c4e31ae90ff14cc27d931.png
[46ad68ec04d94df8988b2994b4180370.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b541e98c4aae4045b0674bbf6df7e276.png
[5b7f185bfae6407bb42ac8615ea6d80d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b738a52106d04ce382925a1fa5d0b877.png
[bbec98ca4ae8497596ea662a51543b98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f237fd122875418bafd61cf2e3e8a7f7.png
[27ba70ae1f2d4a87aab3a41114686844.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bc960a53f9c34ca0a8640616408bbcd3.png
[cef0a7f5a34342038ab5137a395c98d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b8eeec33418e49e283e69bbf8669684c.png
[a85bd8dbc539445286c55c29a2f97ef1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c58f0bc8e1f2433c8db2c185b2ffd03b.png
[45683e48cb904eaa9e28303d079281f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e9ed8bf4e8e44229a313f590acf266c2.png
[9f31f5f6d828452e8210f20c2bd490ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4bfffa1ffaa5487ba205794c4bf9c13a.png
[bffa1cc45b2a495ea9ed390691461b59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/57cef777600144ccafd3dc433bff2477.png
[01c90882733845538bf93de457963d4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3c9614bf8be947aab29bcda42294935b.png
[4240e76ec0154e0a8eeb78b79aac6741.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4a094e81b9644196b034cdba33f3501e.png
[060c65185c3e4481bdfe961a59d39c30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3206de154c754c74bc57e58c784eeebf.png
[1b11fea0a7034e1bb5933e3ccd8f7ffc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f9722e23871f4935a397a8fbec4cc4a8.png
[9067602da8aa4631bbe6b907accdc2ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/34592360693d4d6f95e4fa67e9493b99.png