3、Petri 网

3.1 Petri网定义

3.1.1 为什么叫Petri网

Carl Adam Petri( 1926—2010 )， 莱比锡。《Communication With Automata》1962（Phd论文: Petri网起源于此，1970’s 年代美国人学术会议首次称之为 Petri Net）

Prof.Petri称之为 Net Theory

There is no need for Net Theory to exist if there is no real application of it.
There could be no real applications of Net Theory if there is no General Net Theory

3.1.2 Petri 网定义

1. 有向网
2. 以有向网为基础的网系统
3. 网系统（模型）+理论（GNT）
4. 模型+理论+应用

In order to apply net theory with success, it is by no means necessary to study
physics, or to remember the physical interpretations of net theory.
Just rely on the fact that every net(draw on paper) can be connected to the physical real world by a short(≤4) chain of net morphisms.
The 4 net morphisms are:
1. An injection: your net is, unlike the universe, not a system which is closed with respect of the flow of matter, energy and information.
2. A refinement: Your net does not describe all the detailed elementary physical interactions, but rather, very much coarser.
3. A breaking of the physical symmentry: your net has a definite direction for the
execution of processes while the physical universe is time reversal invariant.
4. An abstraction: your net is an abstract from what belongs together in your purposeful activities. You need a concept that ties things to a pragmatic unit for your mind.

反向理解 Petri 教授的话（Petri网应用）

• 一个pragmatic unit
• 一个execution direction: from past to future
• 一个coarsening process (concealing details)
• 一个abstracting process (formalizing)

3.2 Petri 系统层次模型

1. 第一层
   1. EN系统：Elementary net system，对象个体模型（人、物、信息、数据）和行动轨迹
   2. C/E系统：Condition/event system，大自然
2. 第二层
   1. P/T系统：Place/transition system
3. 第三层：高级网系统
   1. Pr/T系统：Predicate/transition system
   2. Colored net system
4. 第四层：
   1. cyber net system
   2. C_net system

3.3 EN系统 Elementary net system

基本网系统，定义：

$\sum =(B,E;F,c_{in})$ 称为EN系统，如果 $(B,E;F)$ 为有向网，且 $c_{in}\subseteq 2^B$

• $2^B$ ：$B$ 的幂集合，即 $B$ 的所有子集的集合
• $B$ 中库所只有两种状态：有托肯（棋子）或无托肯。称为条件（Bedingung德语）
• $E$ 中变迁称为事件（Event ）只与条件有关
• $C_{in}$ 由成真的条件（有托肯的库所）组成，称为E的初始情态（case）

3.3.1 丛

$B$ 的子集 $c$，即 $c\subseteq B$，称为 $\sum$ 的丛（constellation）

3.3.2 变迁规则

1. $e\in E$，在丛 $c$ 有发生权，记为：$c[e>$，如果 ${}^{.}e\subseteq c\wedge e^{.}\cap c=\varnothing$
2. $c[e>$，$c^{.}=(c{-}^{.}e)\cup e^{.}$ 称为 $c$ 的后继丛，记为 $c[e>c^{\prime }$

3.3.2.1 解释和不解释

例1

• ${\sum }_1$ 的动态变化：周而复始的教堂婚礼，三个token代表神父（$b_0$）和两位新人（$b_0,b_1$）（$T$ 不变量）
• $b_0,b_1,b_2...b_9$ ：三位参与者的状态
• $b_0,b_3,b_4,b_9$ ：神父（S不变量1）
• $b_1,b_3,b_5,b_7$ ：一位新人（S不变量2）
• $b_2,b_4,b_6,b_8$ ：另一位新人（S不变量3）

结构性质：不变量

基本现象：冲突，顺序，并发，同步，异步

3.3.3.2 同步与异步

• 同步（局部）：两组（个）事件反复发生呈现的规律
• 同步（全局）：任何两组事件都（加权）同步
• 异步（全局）： 没有全局控制，局部确定
• Petri 网是异步并发系统（局部确定，所以并发）

例2-法官和犯人

法官向犯人宣布

• 下周选一日执行死刑，执行前一天会向犯人宣布
• 允许犯人预猜行刑日，只能猜一次，猜中即可获释

犯人推理：

• 周日为最后一天，不会周日执行，因为周六即可猜中，于是周六不会被选…
• 结论：不会被处死
• 结果：执行了
• ？错在哪里

用petri 网描述，体会要素和抽象

• $i=1,2,3,4,5,6,7$
• $a{t}_i$：等待的犯人，周 $i$ 前一日
• $d_i$ ：定于周 $i$ 执行，$d{’}_i$：周 $i$ 不执行
• $g_i$：犯人猜周 $i$ 执行，$g{’}_i$ ：未猜周 $i$ 执行
• $d_i,d{’}_i$：共有 7 个token ，恰有一个 $d_i$ 有（执行日）
• $g{’}_i$ ：共有 7 个token ，犯人可将其中一个移入 $g_i$ （猜一次）
• $e_i$：周 $i$ 执行
• $r_i$：周 $i$ 释放

3.3.3约束弧

引入约束弧，简化 ${\sum }_2$ 为 ${\sum }_2^{\prime }$。

3.3.4 条件、事件的物理意义

3.3.4.1 条件的物理意义

• 物理对象（人和物）个体的一种状态，如神父、犯人
• 若干对象作为一个整体的状态(如对话中的神父与新娘)
• 一位（one bit）信息的值（真或假），如 ${\sum }_2$ 中的 $d_i$，$g_i$
• 作为状态的信息必须可观察（有确定的值）
• 注意：信息系统中的一位信息和条件不同

3.3.4.2 事件的物理意义

• 可观察的变化：有确定的观察结果。不因观察者或观察手段而改变（不关心变化原理）
• 原子变化：变化或发生或不发生。不会中断，无中间状态

特例：

• a，$b_1$ 和 $b_2$，$b_3$ 和 $b_4$ 结构上一样，非简单网

  • 

• b，$e$ 不可能发生，冲撞

  • 

• c，$e_3$ 不能发生，非单纯

  • $b_7$ 中的 token：工具或化学催化剂
  • 自用工具不必出现在模型中
  • 催化剂必须出现，但模型不能是EN系统，应该是有未知的中间状态
  • “好”的EN系统应该是单纯的
  • 非单纯结构是不适合用EN系统描述的物理对象
  • 

例4-四季变化

${\sum }_3$ 是四季变化合格的EN系统吗？

• 条件（状态）可观察吗？
• 事件（季节改变）可观察吗？

合格的四季系统什么样？

• 本季为主，上一季的影子，下一季的味道
• 满足并发（出现）公理的最小系统
• 有向网上的完备化操作+同步距离计算

3.3.5 可达情态集

3.3.5.1 定义

3.3.5.1.1 自然语言定义

从 $C_{in}$ （初始情态）开始，经有限多个事件发生所产生的所有后继丛构成的集合称为EN系统 $\sum =(B,E,F,C_{in})$ 的可达集，用 $C_{\sum }$ 表示。 $C_{\sum }$ 中的丛称为 $\sum$ 的情态。

• 那么初始状态算可达情态集吗？即 $C_{in}\in C_{\sum }$ ？

3.3.5.1.2 半形式化定义

$2^B$ 的子集 $R$ 称为 EN系统 $\sum =(B,E,F,C_{in})$ 的可达情态集，

$$\begin{gathered} C_{in}\in R\wedge C\in R\wedge \exists e\in E:C[e>C^{\prime } \\ \to C^{\prime }\in R \end{gathered}$$

，此外 $R$ 中没有别的丛。$R$ 中的丛称为情态（case）。通常用 $C_{\sum }$ 表示可达情态集。

3.3.5.1.3 构造法

1. 令集合 $R=\{(c_{in},0)\}$ ，

2. 从 $R$ 中任取 $(c,0)$，

∀ e ∈ E : ( c [ e > c ′ ∧ { ( c ′ , 0 ) , ( c ′ , 1 } ) ∩ R = ∅ → R : = R ∪ { c ′ , 0 } → R : = R ∪ { ( c , 1 ) − ( c , 0 ) } \forall e\in E:(c[e>c' \wedge \{(c',0),(c',1\}) \cap R=\empty \\ \rightarrow R:=R\cup\{c',0\} \\ \rightarrow R:=R \cup \{(c,1)-(c,0)\} ∀e∈E:(c[e>c′∧{(c′,0),(c′,1})∩R=∅→R:=R∪{c′,0}→R:=R∪{(c,1)−(c,0)}

直到 $R$ 中不再有以 0 标注的 $c$ 。

3. C ∑ = { c ∣ ( c , 1 ) ∈ R } C_{\sum}=\{c|(c,1)\in R\} C∑​={c∣(c,1)∈R}

3.3.5.1.4 形式化定义

$C_{\sum }$ 为可达情态集，如果 $RC(C_{\sum })$

$$\begin{gathered} FR(R):⟺R\subseteq 2^B\wedge c_{in}\wedge \forall c\in R:(\exists e\in E\wedge c[e>c^{\prime } \\ \to c^{\prime }\in R \\ RC(C):⟺FR(C)\wedge \forall C^{\prime }:FR(C^{\prime }) \\ \to C\subseteq C^{\prime } \end{gathered}$$

对于形式化定义一定要考虑 定义的唯一性：
$$\begin{gathered} RC(C)\wedge RC(D) \\ \to C=D \end{gathered}$$
证明：需要定义 $C\subseteq D\wedge D\subseteq C$

定理（算法终止）：构造方法一定会终止，基本网系统中定义 因为 $B$ 为有限集，$2^B$ 也为有限集。

3.3.5.2 基本现象

$c\in C_{\sum }$ ，$e_1,e_2\in E$，$b\in B$

$e_1,e_2$ 在 $c$ 有顺序关系，如果 $c[e_1>c^{\prime }\wedge c^{\prime }[e_2>\wedge \neg c[e_2>$

$e_1,e_2$ 在 $c$ 有并发，如果 $c[e_1>\wedge c[e_2>\wedge {(}^{.}{e}_1\cup e_1^{.})\cap {(}^{.}{e}_2\cup e_2^{.})=\varnothing$

$e_1,e_2$ 在 $c$ 冲突（conflict），如果 $c[e_1>\wedge c[e_2>\wedge {(}^{.}{e}_1\cup e_1^{.})\cap {(}^{.}{e}_2\cup e_2^{.})\ne \varnothing$

情态 $c$ 之下在条件 $b$ 有冲撞（contact），如果 $\exists e\in E{:}^{.}e\subseteq c\wedge b\in e^{.}\cap c$

3.3.5.2.1 例5（参看教堂婚礼系统）

$e_1$ 和 $e_2$ 有顺序关系，$e_1$ 和 $e_3$ 有并发关系

一型冲突，竞争的是资源

二型冲突，竞争的是空间资源

冲撞

3.3.6 结构互补条件

$b_1$ 和 $b_2$ 称为结构互补条件，如果一方前集后集为另一方后集前集，即 ${}^{.}{b}_1=b_2^{.}\wedge b_1^{.}{=}^{.}{b}_2$ ，例如：

补操作可以将二型冲突改为一型冲突

不操作可以消除冲撞

3.3.6.1 例7

根据定义，b 处有一冲撞：

自己跟自己争空间？观察不到的“事件”。没有必要修改定义，排除此种冲撞。

3.3.6.2 思考：四季系统有初始状态吗？

自然界变化无始无终，没有初态，只有当前状态，事件反向发生即可算出过去的状态。所有可能的过去、现在和未来状态构成“完全可达情态集”C。

3.3.6.3 例子

初始状态：

一次变迁：

二次变迁，此时只有红色的可以发生新的变迁：

三次变迁：

四次变迁：

五次变迁：

六次变迁：

七次变迁：

八次同第七次变迁，九次变迁：

红的 token 只能在四个地方出现，所以会有一个 s 不变量，即在这四个地方的 token 的量是一个固定值，只有一个。同样黄色的两个 token 也有自己的 基本 s 不变量。同样，把它们几个加起来可以组成 组合型的 s 不变量。

替补变量：每一个 方格（变迁）都有自己出现的次数，比如其他的都是一次，只有下面的出现了两次：

这个例子可以用到教堂婚礼，红色的是神父，其他的两个是新人。