丁路青，李睿

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

0 引言

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

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

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

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

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

1 預備知識

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

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

其中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)絡（1）的鄰接矩陣A=（aij）n×n，其中：

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

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

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

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

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

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

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

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

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

1.3 已有結果

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

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

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

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

證明見文獻[36]。

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

即：

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

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

2 新運算與關鍵矩陣

2.1 定義運算

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

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

為A作用于x的狀態(tài)變量，記A*x的第i個分量為（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對應。對于輸出函數(shù)的鄰接矩陣和狀態(tài)變量之間同樣可定義“*”。根據(jù)以上定義，合取布爾網(wǎng)絡的表示就可以簡化，看一個例子。

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

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

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

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

2.2 運算性質

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

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

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

進而知：

其中不難驗證B?A?A=B?A（2）。

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

2.3 關鍵矩陣

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

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

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

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

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

2.4 主要結果

定理2.1合取布爾網(wǎng)絡（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)絡在[0，N]上能觀。

必要性

用反證法，即證若C≠{1，2，…，n}，推出網(wǎng)絡不能觀。定義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，不妨設j0∈li，若令

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

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

其中：

計算該網(wǎng)絡在[0，2]上的關鍵矩陣

觀察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)絡在[0，2]上能觀。

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

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

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

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

證明參見文獻[36]。

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

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

證明.設B為輸出函數(shù)的鄰接矩陣，由引理3.1知當網(wǎng)絡滿足引理條件時，有

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

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

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

4 結語

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