合取布爾網(wǎng)絡(luò)的能觀性

丁路青，李睿

（大連理工大學(xué)數(shù)學(xué)科學(xué)學(xué)院，大連116024）

0 引言

為了深入研究生物遺傳機(jī)理，20世紀(jì)60年代末Kauffman提出使用布爾網(wǎng)絡(luò)模型刻畫細(xì)胞和基因調(diào)控網(wǎng)絡(luò)的理論，用二進(jìn)制1（轉(zhuǎn)錄）和0（不轉(zhuǎn)錄）表示基因的兩種轉(zhuǎn)錄狀態(tài)，它們之間的相互作用通過以布爾函數(shù)形式給出的邏輯規(guī)則表示。布爾網(wǎng)絡(luò)模型是模擬網(wǎng)絡(luò)動(dòng)態(tài)過程的基本框架，尤其是在生物背景下，該模型已經(jīng)有了豐富的理論成果[1-3]。

程代展教授及其團(tuán)隊(duì)提出使用矩陣半張量積研究布爾網(wǎng)絡(luò)，這個(gè)方法的基本思想是把布爾網(wǎng)絡(luò)轉(zhuǎn)化成一個(gè)離散時(shí)間線性系統(tǒng)，使布爾網(wǎng)絡(luò)的表示代數(shù)化，形式變得簡單[4]，從而能夠使用許多可用于線性狀態(tài)空間模型的標(biāo)準(zhǔn)數(shù)學(xué)工具，進(jìn)而有助于在理論框架內(nèi)研究布爾網(wǎng)絡(luò)模型，為后續(xù)研究奠定了一個(gè)合理的基礎(chǔ)，獲得了一系列優(yōu)秀的研究成果[5-25]。

合取布爾網(wǎng)絡(luò)是布爾函數(shù)值的更新規(guī)則僅包含and算子的一類特殊布爾網(wǎng)絡(luò)，有著較好的性質(zhì)[26-28]，故對(duì)其研究受到特別的關(guān)注。文獻(xiàn)[29]研究了合取布爾網(wǎng)絡(luò)的軌道控制和狀態(tài)控制集，給出集合是網(wǎng)絡(luò)控制集的充要條件和確切的控制規(guī)則。文獻(xiàn)[30]考慮尋找直接影響輸入的最小狀態(tài)變量集，使最終的合取布爾網(wǎng)絡(luò)能控，給出了能控的充要條件和用于檢測能控性的算法，并證明了合取布爾網(wǎng)絡(luò)的最小能控性問題是NP難的。文獻(xiàn)[31]研究了合取布爾網(wǎng)絡(luò)的最小能觀性問題，給出了具有多項(xiàng)式復(fù)雜度的最小能觀性判斷算法。

布爾網(wǎng)絡(luò)的能觀性是研究布爾網(wǎng)絡(luò)的一個(gè)重要方向，若研究基于矩陣半張量積方法[32-34]，對(duì)有n個(gè)狀態(tài)變量能觀性的判斷是在矩陣階數(shù)為2n×2n的基礎(chǔ)上開展的。文獻(xiàn)[35]是基于圖理論方法研究的能觀性，給出了判斷能觀性的充要條件，同時(shí)證明合取布爾網(wǎng)絡(luò)的能觀性問題是NP難的。

本文第一部分是對(duì)基礎(chǔ)知識(shí)的回顧，介紹了具有n個(gè)狀態(tài)變量，m個(gè)輸出的布爾網(wǎng)絡(luò)的表示形式，給出布爾網(wǎng)絡(luò)鄰接矩陣的定義，利用已有結(jié)論，把狀態(tài)變量隨時(shí)間變化的信息轉(zhuǎn)移到矩陣的變化上。第二部分先定義了鄰接矩陣和狀態(tài)變量之間的運(yùn)算，建立了狀態(tài)變量和鄰接矩陣之間的聯(lián)系，進(jìn)而把狀態(tài)變量用鄰接矩陣和下一時(shí)刻的狀態(tài)變量表示出來，給出了用關(guān)鍵矩陣判斷網(wǎng)絡(luò)在[0，N]上能觀的充要條件并給出例子驗(yàn)證。第三部分研究了具有強(qiáng)連通圖的合取布爾網(wǎng)絡(luò)的能觀性，給出了判斷其能觀性的充要條件。最后一部分是總結(jié)。

1 預(yù)備知識(shí)

1.1 布爾網(wǎng)絡(luò)模型

具有n個(gè)狀態(tài)變量，m個(gè)輸出的布爾網(wǎng)絡(luò)表示為：

其中xi∈{0，1}，yj∈{0，1}，yj表示輸出，fi:{0，1}n→{0，1}，f=（f1，f2，…，fn）T稱為布爾函數(shù)或邏輯函數(shù)，gj:{0，1}n→{0，1}，g=（g1，g2，…，gm）T稱為輸出函數(shù)，這里i=1，2，…，n；j=1，2，…，m。

1.2 鄰接矩陣和能觀性

定義1.1定義網(wǎng)絡(luò)（1）的鄰接矩陣A=（aij）n×n，其中：

類似的可以定義輸出函數(shù)的鄰接矩陣，B=（bij）m×n，其中：

定義1.2如果布爾網(wǎng)絡(luò)的函數(shù)僅是AND算子“∧”，則稱該布爾網(wǎng)絡(luò)為合取布爾網(wǎng)絡(luò)。

假設(shè)以下涉及的布爾網(wǎng)絡(luò)都是合取布爾網(wǎng)絡(luò)。由狀態(tài)變量的取值可以知道xi∧xi=xi，xi∈{0，1}，為方便記x1∧x2∧…∧xn=∧j∈{1，2，…，n}xj以下敘述中省略算子“∧”。下面先給出網(wǎng)絡(luò)在[0，N]上能觀的定義。

定義1.3對(duì)上述布爾網(wǎng)絡(luò)，設(shè)t時(shí)網(wǎng)絡(luò)的狀態(tài)x（t）=（x1（t），x2（t），…，xn（t））T，輸出y（t）=（y1（t），y2（t），…，ym（t））T，稱網(wǎng)絡(luò)在[0，N]上是能觀的，如果對(duì)任意兩個(gè)不同的初始狀態(tài)x（0），x(0)產(chǎn)生兩個(gè)不同的輸出序列{y（0），y（1），…，y（N）}，{y(0)，y(1)，…，y(N)}。

注：在[0，N]上能觀意味著對(duì)任意給定的輸出序列{y（0），y（1），…，y（N）}總能唯一地確定出初始狀態(tài)x（0）。

例1.1考慮合取布爾網(wǎng)絡(luò)在[0，1]上的能觀性。

（1）若輸出為y1（t）=x1（t），則該網(wǎng)絡(luò)在[0，1]上能觀：給定{y（0），y（1）}={y1（0），y1（1）}，因?yàn)閥1（0）=x1（0），y1（1）=x1（1）=x2（0），這意味著輸出{y（0），y（1）}能唯一地確定原始狀態(tài)x（0）=（x1（0），x2（0））T，因此網(wǎng)絡(luò)在[0，1]上能觀。

（2）若輸出為y1（t）=x2（t），則該網(wǎng)絡(luò)在[0，1]上不能觀：給定{y（0），y（1）}={y1（0），y1（1）}，因?yàn)閥1（0）=x2（0），y1（1）=x2（1）=x1（0）x2（0），若取x2（0）=0，那么x1（0）取任意值都會(huì)使輸出相同，因此網(wǎng)絡(luò)在[0，1]上不能觀。

由上例可見網(wǎng)絡(luò)是否能觀與輸出函數(shù)的選取有關(guān)。觀察網(wǎng)絡(luò)（1）可以發(fā)現(xiàn)t+1時(shí)的狀態(tài)依賴t時(shí)的狀態(tài)，t時(shí)的狀態(tài)依賴t?1時(shí)的狀態(tài)，…，這些依賴關(guān)系可以由布爾函數(shù)多次復(fù)合得到，也即是狀態(tài)變量隨時(shí)間的變化表現(xiàn)到布爾函數(shù)的多次復(fù)合上。接下來定義鄰接矩陣之間的運(yùn)算，使布爾函數(shù)的復(fù)合對(duì)應(yīng)到鄰接矩陣的運(yùn)算上，即給出函數(shù)復(fù)合與矩陣運(yùn)算之間的關(guān)系。

1.3 已有結(jié)果

定義1.4設(shè)A=（aij）n×n，B=（bij）n×n是兩個(gè)合取布爾網(wǎng)絡(luò)的鄰接矩陣，定義A?B=（cij）n×n，其中cij=max{ai1b1j，ai2b2j，…，ainbnj}。

可以驗(yàn)證上述定義有意義，參見文獻(xiàn)[36]。不難把定義推廣到A和B為非方陣的情形（A，B有適當(dāng)維數(shù)）。

引理1.1設(shè)f，g:{0，1}n→{0，1}n是兩個(gè)合取布爾網(wǎng)絡(luò)的布爾函數(shù)，A，B分別為其鄰接矩陣，則f°g的鄰接矩陣為A?B。

引理1.2若A是f的鄰接矩陣，則A（k）是fk的鄰接矩陣。

證明見文獻(xiàn)[36]。

例1.2考慮例1.1中網(wǎng)絡(luò)，其鄰接矩陣計(jì)算，且有：

即：

可以看出A（2）為f2的鄰接矩陣。

設(shè)網(wǎng)絡(luò)（1）的鄰接矩陣為A，fk就表示狀態(tài)x（t）和狀態(tài)x（t?k）之間的依賴關(guān)系，由引理1.2.知，fk的變化體現(xiàn)到A（k）的變化上，這樣就把狀態(tài)變量隨時(shí)間變化的依賴關(guān)系轉(zhuǎn)移到鄰接矩陣的變化上了。

2 新運(yùn)算與關(guān)鍵矩陣

2.1 定義運(yùn)算

為了將布爾網(wǎng)絡(luò)代數(shù)化，需要建立網(wǎng)絡(luò)的鄰接矩陣和狀態(tài)變量之間的聯(lián)系，為此定義鄰接矩陣和狀態(tài)變量之間的運(yùn)算“*”。

定義2.1設(shè)A為一合取布爾網(wǎng)絡(luò)的鄰接矩陣，狀態(tài)變量x=（x1，x2，…，xn）T，記Ii={j|aij=1}，定義：

為A作用于x的狀態(tài)變量，記A*x的第i個(gè)分量為（A*x）i，其中i=1，…，n。

注：A*x=（∧j∈I1xj,∧j∈I2xj,…,∧j∈Inxj）T直接取決于集合Ii={j|aij=1}，不妨稱A*x與（I1，I2，…，In）T對(duì)應(yīng)。對(duì)于輸出函數(shù)的鄰接矩陣和狀態(tài)變量之間同樣可定義“*”。根據(jù)以上定義，合取布爾網(wǎng)絡(luò)的表示就可以簡化，看一個(gè)例子。

例2.1上例1.2中網(wǎng)絡(luò)可如下等階：

對(duì)形如（1）的合取布爾網(wǎng)絡(luò)，若用A表示鄰接矩陣，B表示輸出函數(shù)的鄰接矩陣，采用上述定義的矩陣和向量之間的運(yùn)算，則：

（1）?x(t+1)=A*x(t),

（2）?y(t)=B*x(t).

2.2 運(yùn)算性質(zhì)

引理2.1設(shè)A為合取布爾網(wǎng)絡(luò)的鄰接矩陣，B為輸出函數(shù)的鄰接矩陣，x=（x1，x2，…，xn）T為狀態(tài)變量，則（B?A）*x=B*（A*x）。

證 明：（B?A）ij=max{bi1a1j，bi2a2j，…，binanj}，設(shè)A*x與（I1，I2，…，In）T對(duì)應(yīng)，B*x與（J1，J2，…，Im）T對(duì)應(yīng)，B*（A*x）與（Z1，Z2，…，Zm）T對(duì)應(yīng)，（B?A）*x與（K1，K2，…，Km）T對(duì)應(yīng)，則要證Zi=Ki，i=1，2，…，m。由定義2.1知：

容易看出Zi=Ki，i=1，2，…，m，得證。

進(jìn)而知：

其中不難驗(yàn)證B?A?A=B?A（2）。

可見，網(wǎng)絡(luò)在t時(shí)的輸出由B?A（t）和初始狀態(tài)決定，由于初始狀態(tài)的任意性，矩陣B?A（t）就顯得尤為重要。

2.3 關(guān)鍵矩陣

定義2.2稱為合取布爾網(wǎng)絡(luò)在[0，N]上的關(guān)鍵矩陣。

記li={j|Lij=1}，由“*”的 定 義 易 知

其中i=1，…，（N+1）m。

這提示我們合取布爾網(wǎng)絡(luò)的輸出序列完全由其初始狀態(tài)和鄰接矩陣以及輸出函數(shù)的鄰接矩陣決定，于是有：

記C為只含一個(gè)元素的li的并集，于是C?{1，2，…，n}。

2.4 主要結(jié)果

定理2.1合取布爾網(wǎng)絡(luò)（1），（2）在[0，N]上能觀的充要條件是C={1，2，…，n}。

證明：充分性

若C={1，2，…，n}，則?i1,i2,…,in使lik={jk}，?k=1，2，…，n，且 有{j1，j2，…，jn}={1，2，…，n}，故 有(L*x)ik=xjk，于是若初始狀態(tài)的分量xjk(0)≠xjk(0)就一定 有從 而 有 若x(0)≠x(0)，就一定有，網(wǎng)絡(luò)在[0，N]上能觀。

必要性

用反證法，即證若C≠{1，2，…，n}，推出網(wǎng)絡(luò)不能觀。定義C0={j|?i∈{1，2，…，（N+1）m}且|li|>1;j∈li}，有C∪C0={1，2，…，n}。因 為C≠{1，2，…，n}。于是?j0∈{1 ,2,…,n}，j0?C。

（1）若j0?C0，則?i∈{1，2，…，（N+1）m}，j0?li。若令

（2）若j0∈C0，不妨設(shè)j0∈li，若令

注：由定理知判斷網(wǎng)絡(luò)在[0，N]上的能觀性只需計(jì)算[0，N]上的關(guān)鍵矩陣L，矩陣L的階數(shù)是（N+1）m×n。

例2.2考慮以下合取布爾網(wǎng)絡(luò)

其中：

計(jì)算該網(wǎng)絡(luò)在[0，2]上的關(guān)鍵矩陣

觀察L可以發(fā)現(xiàn)l1={1}，l2={2}，l3={4}，l5={3}，l6={6}，l9={5}，故C={1，2，3，4，5，6}，因此網(wǎng)絡(luò)在[0，2]上能觀。

3 具有強(qiáng)連通圖的合取布爾網(wǎng)絡(luò)的能觀性

定義3.1若?N>0，使得布爾網(wǎng)絡(luò)在[0，N]上能觀，則稱該網(wǎng)絡(luò)能觀。

布爾函數(shù)f的依賴圖是一個(gè)有向圖，它有n個(gè)對(duì)應(yīng)于f的n個(gè)變量x1，x2，…，xn的頂點(diǎn)，如果fj依賴xi就有一條由頂點(diǎn)i指向頂點(diǎn)j的有向邊，記為i→j。如果對(duì)有向圖的任意兩個(gè)頂點(diǎn)i，j都存在互通的邊，則稱有向圖是強(qiáng)連通的。強(qiáng)連通圖的循環(huán)數(shù)是它簡單（最短）定向循環(huán)（頂點(diǎn)不重復(fù)）長度的最大公約數(shù)。

引理3.1考慮一合取布爾網(wǎng)絡(luò)，A為鄰接矩陣，假設(shè)網(wǎng)絡(luò)具有強(qiáng)連通圖，l為循環(huán)數(shù)，則?k0使A（k）=A（k+l）對(duì)任意k≥k0成立。

證明參見文獻(xiàn)[36]。

由上述引理知對(duì)具有強(qiáng)連通圖的合取布爾網(wǎng)絡(luò)來說其鄰接矩陣A的冪次在足夠大時(shí)（設(shè)大于等于k0），A（k）按周期為l的規(guī)律出現(xiàn)重復(fù)（k≥k0），也即是當(dāng)N充分大時(shí)[0，N]上的關(guān)鍵矩陣L后面的行出現(xiàn)重復(fù)。由定理2.1知判斷網(wǎng)絡(luò)在[0，N]上的能觀性時(shí)L中重復(fù)出現(xiàn)的行沒有作用，于是我們考慮刪去L中重復(fù)出現(xiàn)的行。

定理3.1在引理3.1的條件下，網(wǎng)絡(luò)的能觀性等價(jià)于網(wǎng)絡(luò)在[0，k0+l?1]上的能觀性。

證明.設(shè)B為輸出函數(shù)的鄰接矩陣，由引理3.1知當(dāng)網(wǎng)絡(luò)滿足引理?xiàng)l件時(shí)，有

為[0，k0+l?1]上的關(guān)鍵矩陣。由定理2.1知判斷有強(qiáng)連通圖的合取布爾網(wǎng)絡(luò)的能觀性就等價(jià)于判斷網(wǎng)絡(luò)在[0，k0+l?1]上的能觀性，得證。

例3.1考慮以下布爾網(wǎng)絡(luò)的能觀性

該網(wǎng)絡(luò)有強(qiáng)連通圖且其循環(huán)數(shù)為2（參考文獻(xiàn)[36]）。設(shè)輸出函數(shù)y（t）=y1（t）=x1（t），有

4 結(jié)語

本文研究了一類特殊的布爾網(wǎng)絡(luò)——合取布爾網(wǎng)絡(luò)的能觀性。由主要結(jié)果定理2.1可見，判斷合取布爾網(wǎng)絡(luò)在[0，N]上的能觀性所用到的矩陣階數(shù)為（N+1）m×n，對(duì)于具有強(qiáng)連通圖的合取布爾網(wǎng)絡(luò)判斷能觀性最多計(jì)算的矩陣階數(shù)為（k0+l）m×n。