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 系統，即條件/事件系統。其中：

• BBB，EEE 分別為條件集和事件集
• FFF 是流關系
• (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,M0)\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,...}∪{∞} ，SSS 元素的容量函數
• ∧W:F→{1,2,3,...}\wedge W:F \rightarrow \{1,2,3,...\}∧W:F→{1,2,3,...} ，FFF 上的權函數，資源消耗或產生的量
• ∧M0:S→{0,1,2,...}\wedge M_0:S \rightarrow \{0,1,2,...\}∧M0?:S→{0,1,2,...} ，初始標識（資源初始分布）
• ∧?s∈S:M0(s)≤K(s)\wedge \forall s \in S: M_0(s) \leq K(s)∧?s∈S:M0?(s)≤K(s)

思考：如何理解 K(s)=∞K(s)=\inftyK(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 變遷規則

3.5.2.1 變遷規則：發生權

t∈Tt \in Tt∈T，MMM 為 ∑\sum∑ 的標識

定義：ttt 在 MMM 有發生權，記作 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> ，則 ttt 可以發生，M′M'M′ 為 MMM 的后繼標識：
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′(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. 稱為變遷 ttt 的外延（extension）

3.5.2.3.1 局部確定原理（普適）

• 每個變遷都有它的外延
• 變遷的發生只依賴其外延，也只改變其外延
• ∑∩Env(∑)\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)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*} W′(x,y)={W(x,y)0?if(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′ 取代 WWW 會失去其物理含義；
  • 用 W′W'W′ 取代 WWW 和 FFF ，定義 ∑=(S,T;W′,M0)\sum=(S,T;W',M_0)∑=(S,T;W′,M0?) ，會失去網結構

3.5.2.5 缺省值及特例的圖示

t1t_1t1? 缺省的容量為 ∞\infty∞ ，缺省的權為 1。

t2t_2t2? 不屬于 P/T 系統，M0(s3)=3>K(s3)=2M_0(s_3)=3>K(s_3)=2M0?(s3?)=3>K(s3?)=2

t3t_3t3? 屬于 P/T 系統，只是不會發生

• 對于圖上的變遷上沒有數字的是 權函數的缺失值，一般就是1。
• 對于圖上的容量上沒有數字的是 容量函數的缺失值，一般就是 ∞\infty∞。

3.5.2.6 容量的物理含義

先舉個教堂婚禮的例子，如果忽略新郎新娘之間的差別，即從 CE 系統到 P/T 系統。

• 缺點：少了很多具體的描述，比如說 EN 系統原來的沖突消失了。
• 優點：系統變的簡單了。

思考：K≡∞K \equiv \inftyK≡∞ 還是
{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*} {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,cin)\sum = (B,E;F,c_{in})∑=(B,E;F,cin?) 是 P/T 系統的特例。

• 其中 K≡1K\equiv 1K≡1 ，W≡1W \equiv 1W≡1 ，M0M_0M0? 是 cinc_{in}cin? 的另一種表示

?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*} ?b∈B:{M0?(b)=1M0?(b)=0?if(b∈cin?)if(b∈/cin?)???

3.5.3.1 練習

將 EN 系統上定義的基本現象移植到 P/T 系統上，變遷（事件）和變遷發生權。

3.5.3.1.1 例子1

• t1t_1t1? 、t2t_2t2? 并發
• t1t_1t1? 、t2t_2t2? 分別和自己并發

3.5.3.1.2 例子2

• t1t_1t1? 、t2t_2t2? 、t3t_3t3? 兩兩并發
• t2t_2t2? 和自己并發
• 三者不能并發

3.5.3.2 并發步

在同一標識可以并發的一個或多個變遷，稱為該標識上的一個并發步。例如：

• 在 3.5.3.1.1 例子1 中 {t1,t2}\{t_1,t_2\}{t1?,t2?} 是并發步，寫成 t1+t2t_1+t_2t1?+t2? 。同時，2t12t_12t1?、2t22t_22t2? 也是并發步。
• 在 3.5.3.1.2 例子2 中 t1+t2t_1+t_2t1?+t2? ，t1+t3t_1+t_3t1?+t3? ，t2+t3t_2+t_3t2?+t3? ，2t22t_22t2? 。

3.5.3.3 可達標識集

3.5.3.3.1 定義

設 MMM 為 ∑\sum∑ 的任一標識，用 [M?[M \rangle[M? 表示符合下列條件的最小集合

• M∈[M?M \in [M \rangleM∈[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 \ranglet∈T∧M′∈[M?∧M′[t?M′′→M′′∈[M?

定義：[M0?[M_0 \rangle[M0?? 稱為 ∑\sum∑ 的可達標識集

3.5.3.3.2 自然語言定義

可達標識集 [M0?[M_0 \rangle[M0?? 的自然語言定義：

• 從 M0M_0M0? 開始，包括 M0M_0M0?
• 經有限步變遷發生
• 能到達的
• 所有標識的集合

思考：怎么證明？

3.5.3.4 變遷序列

σ=τ1τ2...τn\sigma = \tau _1 \tau _2 ... \tau _nσ=τ1?τ2?...τn? 稱為 ∑\sum∑ 的變遷序列。如果對 i=1,2,...,ni=1,2,...,ni=1,2,...,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τi?∈T∧?Mi?∈[M0??:Mi?1?[τi??Mi?，即 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_nM0?[τ1??M1?[τ2??M2?...Mn?1?[τn??Mn?

MnM_nMn? 稱為 σ\sigmaσ 的后繼標識，記作 M0[σ?MnM_0[\sigma \rangle M_nM0?[σ?Mn?

變遷序列是從 M0M_0M0? 開始可以依次發生的變遷組成的序列，不是任意的變遷組成的序列。

變遷序列可以擴展到無窮序列：

• σ′=τ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 活性

關注狀態，即 [M0?[M_0 \rangle[M0??

• 變遷 t∈Tt\in Tt∈T 是活的，如果 ?M∈[M0??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 有界性

若存在正整數 kkk ，使得 ?M∈[M0>?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 為界。哲學家就餐問題的圖如下：

3.5.3.5.3 公平性

如果不存在無窮變遷序列 σ\sigmaσ 和變遷子集 T1T_1T1? 、T2T_2T2? ，使得 #(σ,T1)=∞∧#(σ,T2)<∞\#(\sigma ,T_1)=\infty \wedge \#(\sigma, T_2)<\infty#(σ,T1?)=∞∧#(σ,T2?)<∞，則 ∑\sum∑ 是公平的， 其中 #(σ,Ti)\#(\sigma ,T_i)#(σ,Ti?) 是 TiT_iTi? 中變遷在 σ\sigmaσ 中出現的次數，i=1,2i=1,2i=1,2 。

• 教堂婚禮系統是公平的
• 不加管理的哲學家系統是不公平的
• 問題：公平性的定義合理嗎？

3.5.3.6 系統進程

狀態變遷并重：網系統進程。

3.5.3.6.1 出現網

N=(B,E;F)N=(B,E;F)N=(B,E;F) 稱為出現網，如果 NNN 為有向網，且 (?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+)

例子（出現網 N1N_1N1?）：

• N1N_1N1? 每個庫所至多一條入弧、一條出弧。（產生和消耗）
• N1N_1N1? 無環，(b2,b4)∈F2(b_2,b_4)\in F^2(b2?,b4?)∈F2，(b1,b3)∈F5(b_1,b_3)\in F^5(b1?,b3?)∈F5，F+=F∪F2∪F3∪...F^+=F\cup F^2 \cup F^3 \cup ...F+=F∪F2∪F3∪...

定義：出現網 NNN 是網系統 ∑\sum∑ 的一個進程，如果存在從 NNN 到 ∑\sum∑ 的映射。如下圖就是 出現網 N1N_1N1? 的 網系統映射 網系統 ∑1\sum _1∑1?

N1N_1N1? 是 ∑1\sum _1∑1? 的一個進程（變遷發生的記錄），從 N1N_1N1? 到 ∑1\sum _1∑1? 的映射：

• b1→s1b_1 \rightarrow s_1b1?→s1? ，b2→s3b_2 \rightarrow s_3b2?→s3?，b3→s2b_3 \rightarrow s_2b3?→s2?，b4→s4b_4 \rightarrow s_4b4?→s4?，b5→s3b_5 \rightarrow s_3b5?→s3?，b6→s1b_6 \rightarrow s_1b6?→s1?，b7→s2b_7 \rightarrow s_2b7?→s2?
• e1→t1e_1 \rightarrow t_1e1?→t1?，e2→t2e_2 \rightarrow t_2e2?→t2?，e3→t1e_3 \rightarrow t_1e3?→t1?

3.5.3.6.2 網系統進程的形式（半形式）定義很復雜

通常只給出 ∑=(S,T;F,M0)\sum=(S,T;F,M_0)∑=(S,T;F,M0?) 上的進程定義，即 K≡∞K\equiv \inftyK≡∞ ，W≡1W \equiv 1W≡1。

這里最“老”的網系統（Petri 最早的定義，在其博士論文中的定義）。

進程是并發公理基礎。

3.5.3.7 k<∞k<\inftyk<∞ 的物理含義

k(s)=5k(s)=5k(s)=5 表示 sss 有 5 個“空間資源”，或 sss 的空間至多能容納 5 個sss 類資源（如車庫）。例如下圖：

ttt 只能發生一次，再發生會引出 sss 處的沖撞。

k=∞k=\inftyk=∞：空間足夠大，不會對變遷發生構成限制。

以下就會受到影響：

3.5.3.7.1 容量函數的作用

以容量函數而非 token 表示空間資源，體現空間資源與其它資源的本質區別：被占的空間不能阻止強占，已消耗的資源已不可見。

引出 “沖撞（contact）” 這一基本現象。熟知空間資源特點后，S_補技術改用 token 表示有限的空間資源，k≡∞k \equiv \inftyk≡∞ ，沖撞從系統中消失（并非從現實消失）。

s′s's′ 和 sss 互為補庫所：

• 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)

例如下面的：

3.5.4 代數表示

限于有線網系統 ::: 全局，結構：∑=(S,T;F,W,M0)\sum =(S,T;F,W,M_0)∑=(S,T;F,W,M0?)，K≡∞K \equiv \inftyK≡∞，T={t1,t2,...,tn}T=\{t_1,t_2,...,t_n\}T={t1?,t2?,...,tn?}，S={s1,s2,...,sm}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×nm \times nm×n 階矩陣 AAA 稱為 ∑\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=s1?s2??sm???t1??t2??...?tn?????...?a(i,j)??????????
其中，a(i,j)=W′(ti,sj)?W′(sj,ti)a(i,j)=W'(t_i,s_j)-W'(s_j,t_i)a(i,j)=W′(ti?,sj?)?W′(sj?,ti?)。

關聯矩陣與 M0M_0M0? 無關，是網系統的結構描述。

3.5.4.1.1 例子 ∑1\sum _1∑1?

∑1\sum _1∑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*} A=hlcr??t1??t2??????1?210??1?401???????

3.5.4.1.2 例子 ∑2\sum _2∑2?

∑2\sum _2∑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*} A2?=s1?s2?s3???t1??t2??t3??????1?12?01?1?1?10???????

3.5.4.2 S_向量和T_向量

• τ=(a1,a2,...,an)\tau=(a_1,a_2,...,a_n)τ=(a1?,a2?,...,an?)，aia_iai? 為非負整數
• σ=(b1,b2,...,bm)\sigma = (b_1,b_2,...,b_m)σ=(b1?,b2?,...,bm?)，bjb_jbj? 為非負整數
• 分別稱為 ∑\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=???a1?a2??an???????，σT=(b1b2?bm)\sigma ^ T = \begin{array}{lc} \left(\begin{array}{cc} b_1\\ b_2\\ \vdots \\ b_m \end{array}\right) \end{array}σT=???b1?b2??bm?????? 分別是 τ\tauτ 和 σ\sigmaσ 的轉置向量。

3.5.4.2.1 狀態方程

M=M0+A?τTM=M_0+A \cdot \tau ^ TM=M0?+A?τT 稱為 ∑\sum∑ 的狀態方程，其中 τ\tauτ 為任一 T_向量，M0M_0M0? 和 MMM 分別是標識的 S_向量

命題：設 α=τ1,τ2,...\alpha = \tau _1,\tau _2,...α=τ1?,τ2?,...，τ1\tau _1τ1? 為 ∑\sum∑ 的任一變遷序列，τ=(a1,a2,...,an)\tau=(a_1,a_2,...,a_n)τ=(a1?,a2?,...,an?) 是它的 T_向量 ，即 aia_iai? 為變遷 tit_iti? 在該序列中出現的次數，i=1,2,...,ni=1,2,...,ni=1,2,...,n ，則 M=M0+A?τTM=M_0+A \cdot \tau ^ TM=M0?+A?τT，其中 MMM 是 α\alphaα 的后繼：M0[α?MM_0[\alpha \rangle MM0?[α?M。

3.5.4.2.2 T-不變量 和 S-不變量

T-不變量

• 若 T_向量 τ\tauτ 滿足 M0=M0+A?τTM_0=M_0+A \cdot \tau^TM0?=M0?+A?τT，則 τ\tauτ 稱為 ∑\sum∑ 的 T-不變量。
• 若 τ\tauτ 為 ∑\sum∑ 的 T-不變量，則 A?τT=θSTA \cdot \tau ^ T=\theta ^ T_SA?τ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?

∑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?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)σ1??A1?=(1,0,1,1)?????1?210??1?401?????=(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??A1?=(0,1,2,4)?????1?210??1?401?????=(0,0)

例子 ∑2\sum _2∑2?

∑2\sum _2∑2? 的不變量包括：

• σ=(1,1,1)\sigma=(1,1,1)σ=(1,1,1)
• τ=(1,2,1)\tau = (1,2,1)τ=(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?=(1,1,1)?????1?12?01?1?1?10?????=(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)A2??τT=????1?12?01?1?1?10?????????121?????=(0,0,0)??

練習

∑1\sum_1∑1? 是雞兔同籠問題中數雞（t1t_1t1?）數兔（t2t_2t2?）的網表示，請補上 t1t_1t1? ，t2t_2t2? 可能需要的調整變遷（并發數數，一方太快，導致頭或腿剩下）。

找一找教堂婚禮系統的不變量

找一找哲學家系統的不變量，理解 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.{A?XT=θS?Y?A=θT?? 可以求解 TTT 和 SSS 不變量或者驗證不變量。其中，X=(x1,x2,...,xn)X=(x_1,x_2,...,x_n)X=(x1?,x2?,...,xn?) 和 Y=(y1,y2,...,ym)Y=(y_1,y_2,...,y_m)Y=(y1?,y2?,...,ym?) 分別為未知變量 T_向量 和 未知S_向量 。

3.5.4.2.4 結論

T-不變量 和 S-不變量 是結構性質，與 M0M_0M0? 無關。

定義：

• 如果 ∑\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∑ 如圖所示

M0=(1,0,0)M_0=(1,0,0)M0?=(1,0,0) ，S1S_1S1?、S2S_2S2?、S3S_3S3? 的資源數

若無無窮分支，可達樹節點即為 [M0>[M_0>[M0?>

覆蓋樹算法：為無窮分支“剪枝”

• M1≤M2M_1\leq M_2M1?≤M2? ，如果 ?s∈S:M1(s)≤M2(s)\forall s \in S:M_1(s)\leq M_2(s)?s∈S:M1?(s)≤M2?(s)，M2M_2M2? 覆蓋 M1M_1M1?
• M1<M2M_1 < M_2M1?<M2? ，如果 M1≤M2∧?s∈S:M1(s)<M2(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)

最后得到的覆蓋樹

[M0>[M_0>[M0?> 中所有標識均被覆蓋樹節點覆蓋

覆蓋圖：M2M_2M2? 與 M1M_1M1? 重疊，一類葉節點。將覆蓋樹同一路徑上相同節點重疊

可達樹，覆蓋樹，覆蓋圖，可用以檢查驗證活性，有界性，公平性及不變量。

• 如例子中的系統是不公平的，不活的，無界的，沒有不變量。

3.5.5.2 求解不變量法

3.5.5.3 化簡法：忽略網結構細節

3.5.5.4 提高層次法：提高抽象度以減少節點數

總結

以上是生活随笔為你收集整理的Petri网-3.4 C/E 系统 与 3.5 P/T 系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。