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

3.4 C/E 系统 Condition/Event system

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

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

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

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

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

3.5.1 库所/变迁系统定义

库所：Place
变迁：Transition

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

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

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

3.5.1.1 标识：资源分布

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

3.5.2 变迁规则

3.5.2.1 变迁规则：发生权

$\in T$ ， $M$ 为 $∑\sum$ 的标识

定义： $t$ 在 $M$ 有发生权，记作 $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)$

3.5.2.2 变迁规则：后继

若 $M [t >$ ，则 $t$ 可以发生， $M^{'}$ 为 $M$ 的后继标识：
$M′(s)={M(s)−W(s,t)if(s∈.t−t.)M(s)+W(t,s)if(s∈t.−.t)M(s)+W(t,s)−W(s,t)if(s∈.t∩t.)M(s)if(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 [t > M^{'}$

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

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

3.5.2.3.1 局部确定原理（普适）

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

3.5.2.4 广义权函数

$\times T \cup T \times S \rightarrow \{0,1,2,…\}$ 称为 $∑\sum$ 的广义权函数，如果 $∀(x,y)∈S×T∪T×S\forall(x,y)\in S \times T \cup T \times S$
$W′(x,y)={W(x,y)if(x,y)∈F0if(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*}$

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

$\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)$

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

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

3.5.2.5 缺省值及特例的图示

$t_1$ 缺省的容量为 $∞\infty$ ，缺省的权为 1。

$t_2$ 不属于 P/T 系统， $M_0(s_3)=3>K(s_3)=2$

$t_3$ 属于 P/T 系统，只是不会发生

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

3.5.2.6 容量的物理含义

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

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

思考： $\equiv \infty$ 还是
${K(s1)=K(s3)=K(s4)=2K(s0)=K(s2)=K(s5)=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*}$
就这个例子而言，其实认为它的容量是 2 还是 $∞\infty$ 都可以，因为都不会影响系统的后继和运行。

3.5.2.7 库所的物理含义

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

3.5.2.8 变迁的物理含义

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

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

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

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

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

其中 $K≡1K\equiv 1$ ， $\equiv 1$ ， $M_0$ 是 $c_{in}$ 的另一种表示

$∀b∈B:{M0(b)=1if(b∈cin)M0(b)=0if(b∉cin)\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*}$

3.5.3.1 练习

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

3.5.3.1.1 例子1

$t_1$ 、 $t_2$ 并发
$t_1$ 、 $t_2$ 分别和自己并发

3.5.3.1.2 例子2

$t_1$ 、 $t_2$ 、 $t_3$ 两两并发
$t_2$ 和自己并发
三者不能并发

3.5.3.2 并发步

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

在 3.5.3.1.1 例子1 中 ${t_1,t_2\}$ 是并发步，写成 $t_1+t_2$ 。同时， $2t_1$ 、 $2t_2$ 也是并发步。
在 3.5.3.1.2 例子2 中 $t_1+t_2$ ， $t_1+t_3$ ， $t_2+t_3$ ， $2t_2$ 。

3.5.3.3 可达标识集

3.5.3.3.1 定义

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

$\in [M \rangle$
$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$

定义： $[M0⟩[M_0 \rangle$ 称为 $∑\sum$ 的可达标识集

3.5.3.3.2 自然语言定义

可达标识集 $[M0⟩[M_0 \rangle$ 的自然语言定义：

从 $M_0$ 开始，包括 $M_0$
经有限步变迁发生
能到达的
所有标识的集合

思考：怎么证明？

3.5.3.4 变迁序列

$σ=τ1τ2…τn\sigma = \tau _1 \tau _2 … \tau _n$ 称为 $∑\sum$ 的变迁序列。如果对 $i = 1, 2, \dots, n$ ， $τi∈T∧∃Mi∈[M0⟩:Mi−1[τi⟩Mi\tau _i \in T \wedge \exists M_i \in [M_0 \rangle : M_{i-1}[\tau _i \rangle M_i$ ，即 $M0[τ1⟩M1[τ2⟩M2…Mn−1[τn⟩MnM_0 [\tau _1 \rangle M_1[ \tau _2 \rangle M_2… M_{n-1}[\tau _n \rangle M_n$

$M_n$ 称为 $σ\sigma$ 的后继标识，记作 $M0[σ⟩MnM_0[\sigma \rangle M_n$

变迁序列是从 $M_0$ 开始可以依次发生的变迁组成的序列，不是任意的变迁组成的序列。

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

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

3.5.3.5 P/T 系统性质

3.5.3.5.1 活性

关注状态，即 $[M0⟩[M_0 \rangle$

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

3.5.3.5.2 有界性

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

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

3.5.3.5.3 公平性

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

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

3.5.3.6 系统进程

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

3.5.3.6.1 出现网

$N = (B, E; F)$ 称为出现网，如果 $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^+)$

例子（出现网 $N_1$ ）：

$N_1$ 每个库所至多一条入弧、一条出弧。（产生和消耗）
$N_1$ 无环， $(b2,b4)∈F2(b_2,b_4)\in F^2$ ， $(b1,b3)∈F5(b_1,b_3)\in F^5$ ， $F+=F∪F2∪F3∪…F^+=F\cup F^2 \cup F^3 \cup …$

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

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

$b1→s1b_1 \rightarrow s_1$ ， $b2→s3b_2 \rightarrow s_3$ ， $b3→s2b_3 \rightarrow s_2$ ， $b4→s4b_4 \rightarrow s_4$ ， $b5→s3b_5 \rightarrow s_3$ ， $b6→s1b_6 \rightarrow s_1$ ， $b7→s2b_7 \rightarrow s_2$
$e1→t1e_1 \rightarrow t_1$ ， $e2→t2e_2 \rightarrow t_2$ ， $e3→t1e_3 \rightarrow t_1$

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

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

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

进程是并发公理基础。

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

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

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

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

以下就会受到影响：

3.5.3.7.1 容量函数的作用

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

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

$s^{'}$ 和 $s$ 互为补库所：

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

例如下面的：

3.5.4 代数表示

限于有线网系统 $:$ 全局，结构： $∑=(S,T;F,W,M0)\sum =(S,T;F,W,M_0)$ ， $\equiv \infty$ ， $T=\{t_1,t_2,…,t_n\}$ ， $S=\{s_1,s_2,…,s_m\}$ ， $\times T \cup T \times S \\ \rightarrow \{0,1,2,…\}$ 为广义权函数。

3.5.4.1 关联矩阵

定义： $\times n$ 阶矩阵 $A$ 称为 $∑\sum$ 的关联矩阵。如果
$A=t1t2…tns1s2⋮sm(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(i,j)=W'(t_i,s_j)-W'(s_j,t_i)$ 。

关联矩阵与 $M_0$ 无关，是网系统的结构描述。

3.5.4.1.1 例子 $∑1\sum _1$

$∑1\sum _1$ 的关联矩阵
$A=t1t2hlcr(−1−1−2−41001)\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*}$

3.5.4.1.2 例子 $∑2\sum _2$

$∑2\sum _2$ 的关联矩阵
$A2=t1t2t3s1s2s3(−101−11−12−10)\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*}$

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

$τ=(a1,a2,…,an)\tau=(a_1,a_2,…,a_n)$ ， $a_i$ 为非负整数
$σ=(b1,b2,…,bm)\sigma = (b_1,b_2,…,b_m)$ ， $b_j$ 为非负整数
分别称为 $∑\sum$ 的 T_向量 和 S_向量
$τT=(a1a2⋮an)\tau ^ T = \begin{array}{lc} \left(\begin{array}{cc} a_1\\ a_2\\ \vdots \\ a_n \end{array}\right) \end{array}$ ， $σT=(b1b2⋮bm)\sigma ^ T = \begin{array}{lc} \left(\begin{array}{cc} b_1\\ b_2\\ \vdots \\ b_m \end{array}\right) \end{array}$ 分别是 $τ\tau$ 和 $σ\sigma$ 的转置向量。

3.5.4.2.1 状态方程

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

命题：设 $α=τ1,τ2,…\alpha = \tau _1,\tau _2,…$ ， $τ1\tau _1$ 为 $∑\sum$ 的任一变迁序列， $τ=(a1,a2,…,an)\tau=(a_1,a_2,…,a_n)$ 是它的 T_向量 ，即 $a_i$ 为变迁 $t_i$ 在该序列中出现的次数， $i = 1, 2, \dots, n$ ，则 $M=M0+A⋅τTM=M_0+A \cdot \tau ^ T$ ，其中 $M$ 是 $α\alpha$ 的后继： $M0[α⟩MM_0[\alpha \rangle M$ 。

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

T-不变量

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

S-不变量

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

例子 $∑1\sum _1$

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

$σ1=(1,0,1,1)\sigma _1=(1,0,1,1)$
$σ2=(0,1,2,4)\sigma _2=(0,1,2,4)$
$σ1⋅A1=(1,0,1,1)⋅(−1−1−2−41001)=(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)$
$σ2⋅A1=(0,1,2,4)⋅(−1−1−2−41001)=(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\sum _2$

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

$σ=(1,1,1)\sigma=(1,1,1)$
$τ=(1,2,1)\tau = (1,2,1)$
$σ⋅A2=(1,1,1)⋅(−101−11−12−10)=(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⋅τT=(−101−11−12−10)⋅(121)=(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)$

练习

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

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

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

3.5.4.2.3 求解不变量

${A⋅XT=θSY⋅A=θT\left \{ \begin{array}{ll} A \cdot X^T = \theta _S \\ Y \cdot A = \theta _T \end{array} \right.$ 可以求解 $T$ 和 $S$ 不变量或者验证不变量。其中， $X=(x_1,x_2,…,x_n)$ 和 $Y=(y_1,y_2,…,y_m)$ 分别为未知变量 T_向量 和 未知S_向量 。

3.5.4.2.4 结论

T-不变量 和 S-不变量 是结构性质，与 $M_0$ 无关。

定义：

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

命题：

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

3.5.5 通用分析方法

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

3.5.5.1 可达树与覆盖树算法

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

$M_0=(1,0,0)$ ， $S_1$ 、 $S_2$ 、 $S_3$ 的资源数

若无无穷分支，可达树节点即为 $M_0>$

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

$M1≤M2M_1\leq M_2$ ，如果 $∀s∈S:M1(s)≤M2(s)\forall s \in S:M_1(s)\leq M_2(s)$ ， $M_2$ 覆盖 $M_1$
$M_1 < M_2$ ，如果 $M1≤M2∧∃s∈S:M1(s)<M2(s)M_1 \leq M_2 \wedge \exists s \in S:M_1(s)<M_2(s)$