張 靜，樊永艷

(滄州師范學院)

1 布爾網(wǎng)絡

近年來布爾型網(wǎng)絡以及同步分析被逐漸運用于大型基因調(diào)節(jié)網(wǎng)絡全局行為的分析研究，其優(yōu)點是結構簡單明了.另外，它在生命科學、金融科學以及其他一些典型復雜系統(tǒng)研究中都起到非常重要的作用.布爾網(wǎng)絡［1-2］G(V，F(xiàn))由結點狀態(tài)集V={X1，X2，…，Xn}和布爾函數(shù)集F={f1，f2，…，fn}組成.結點i在t+1時刻的狀態(tài)Xi∈{0，1}是由其他一些與它相連通的結點，，…在t時刻的狀態(tài)，，…，決定的，即

網(wǎng)絡在t時刻的狀態(tài)由所有結點的狀態(tài)向量→X(t)=X1(t)X2(t)…Xn(t)來描述.很明顯，對于一個有n個結點的網(wǎng)絡，它的狀態(tài)空間由00…0到11…1的2n種狀態(tài)組成的.

圖1 節(jié)點A和B組成的布爾網(wǎng)絡

圖1［3］是由兩個節(jié)點A和B組成的布爾網(wǎng)絡，它的動態(tài)系統(tǒng)為

其 中 ∨ (∧)意 思 是 max(A(t)，B(t))(min(A(t)，B(t))).

2 半張量積

矩陣的半張量積是近期中科院系統(tǒng)所程代展教授在文獻［4］中提出的一種新的矩陣乘法，它是對普通矩陣乘法的推廣.對于普通矩陣，矩陣A、B只有矩陣A的列數(shù)與矩陣B的行數(shù)相等才可以相乘.而矩陣的半張量積可以解決非等維數(shù)的矩陣相乘，即矩陣A的列數(shù)與矩陣B的行數(shù)不相等的矩陣相乘.矩陣的半張量積的應用領域很廣，它主要用來處理多維數(shù)組及處理非線性問題，在邏輯、幾何、代數(shù)、物理、控制系統(tǒng)及Morgan等等問題中均可找到它的應用［4-6］.

定義1［4］設 A ∈ Mm×n，B ∈ Mp×q.記 n 與 p的最小公倍數(shù)為t=lcm{n，p}.定義A與B的半張量積為

這里Mm×n表示所有m×n矩陣的集合，?表示kronecker積，?代表左半張量積.

定義2［4］換位矩陣 W［m，n］是一個 mn × mn矩陣，定義如下:它的行和列都是由雙指標(i，j)標注，列是按照索引Id(i，j;m，n)排列，行是按照索引 Id(j，i;n，m)排列，并且位于［(I，J)，(i，j)］上的元素的值為

命題1［4］(1)換位矩陣的逆和轉(zhuǎn)置為

(2)當m=n時，上式變?yōu)?/p>

m=n的情形特別重要，為了簡化符號，記

引理1［4］設A是一個邏輯變量，定義降冪矩陣為，那么對于任意的p×4q矩陣Ψ有ΨA2=ΨMrA.

定義3［4］(1)(經(jīng)典)邏輯論域Dt是指

(2)(經(jīng)典)邏輯變量P是指在Dt中取值的變量，即P∈Dt;

記T0≡T≡1和F0≡F≡0分別表示“真”和“假”.

定義4［4］(1)r元邏輯算子是指映射 σ:

為了使用矩陣表示，記

定義5［4］稱2×2r矩陣Mσ為r元邏輯算子σ的機構矩陣，如果

考慮4個基本的二元邏輯算子;析取，P∨Q;合取，P∧Q;蘊涵，P→Q;等值，P?Q.4個基本二元邏輯算子的結構矩陣如下:

3 半張量積在布爾網(wǎng)絡中的應用

應用半張量積，就可以將布爾網(wǎng)絡的邏輯方程轉(zhuǎn)化成為代數(shù)方程［7］，邏輯變量就表達成了向量形式，定義T=1 ～，F(xiàn)=0 ～，其中是單位陣In的第i列，則邏輯變量A(t)在D:={，}中取值.

對于每個邏輯算子ξ=ξ(A1，…，An)存在一個 ξ的結構矩陣，記為 Mξ∈ M2×2n，表示為

例如，對于∧和∨，分別為Mc和Md，Mc= σ2［1，2，2，2，2］，Md= σ2［1，1，1，2］.例如 A(t+1)=A(t)∨B(t)可以被表示為代數(shù)形式:

B(t+1)=A(t)∧B(t)可以被表示為代數(shù)形式:

基于以上，將一個邏輯動態(tài)系統(tǒng)轉(zhuǎn)化為一離散時間動態(tài)系統(tǒng)的方法，可以得到一個網(wǎng)絡過渡矩陣L.把邏輯動態(tài)方程轉(zhuǎn)化為離散時間的動態(tài)方程，一個有 n個節(jié)點 Ai，i=1，2，…，n的布爾網(wǎng)絡被表示為

其中 ξi，i=1，2，…，n 是邏輯函數(shù)(算子).

應用(12)，Ai(t+1)=WiA1(t)A2(t)…An(t)，i=1，2，…，n，定義 x(t)=A1(t)A2(t)…An(t).可以得出

應用半張量積性質(zhì)以及降冪矩陣Mr=σ4［1，4］，(16)可以被表示為x(t+1)=Lx(t).其中L被叫做過渡矩陣.

由圖 1，計算其過渡矩陣，設 x(t)=A(t)B(t)，那么

則 L=Md(I4? Mc)(I2? w［2］)Mr(I2? Mr)= δ4［1，2，2，4］

4 布爾網(wǎng)絡的同步分析

在生態(tài)環(huán)境中，存在著許多同步現(xiàn)象，如夏日青蛙，知了的齊鳴，螢火蟲一致發(fā)光，蟋蟀群的叫聲有節(jié)奏地唱和，鳥兒成群的飛;不僅是生態(tài)，從核子到宇宙、從物理到化學，乃至人類社會，都廣泛存在著同步現(xiàn)象，如心肌細胞和大腦神經(jīng)網(wǎng)絡的同步，鐘擺同步現(xiàn)象，劇場中觀眾自發(fā)鼓掌同步等.對于復雜系統(tǒng)內(nèi)部個體之間通過局部相互作用(耦合)，從一種狀態(tài)突然變成另一種狀態(tài)，逐漸的自組織形成了每個個體狀態(tài)一致的現(xiàn)象，稱作同步現(xiàn)象.

布爾網(wǎng)絡可以用邏輯函數(shù)來表示，如圖2.假設有一個簡單的布爾網(wǎng)絡，有四個結點，分別為A、B、C、D，并且兩兩相連，假設結點 A受結點 B和結點D的狀態(tài)控制，節(jié)點B則受結點A和結點C的狀態(tài)控制，結點C受結點B和結點D的狀態(tài)控制，結點D受結點C和結點A的狀態(tài)控制.如果給結點A、C“或”布爾作用，給結點B、D“與”布爾作用，分別用“0”和“1”表示結點處于“是”和“否”兩種狀態(tài).

圖2 邏輯函數(shù)布爾網(wǎng)絡

則邏輯函數(shù)為:

通過給定的布爾作用，如果四個結點在某一時刻T的狀態(tài)確定，則各結點在下一時刻T+1的狀態(tài)也可以相應地確定，表1給出了四個結點在不同時刻可能的16種狀態(tài)的真值.若在某一時刻T0，四個結點的狀態(tài)均為0或1，則這個布爾網(wǎng)絡同步.通過計算，得出，A、B、C、D初始狀態(tài)為1011、1110、1111時可以達到同步狀態(tài)為1，初始狀態(tài)為0000時可以達到同步狀態(tài)為0.其余的初始狀態(tài)最終進入循環(huán)狀態(tài)，達不到同步.

表1 邏輯函數(shù)布爾網(wǎng)絡真值表

利用邏輯算子研究布爾網(wǎng)絡的同步.

一個邏輯變量是指一個命題，如果這個命題是真的，就說這個邏輯變量取值為“真”或“1”，如果這個命題是假的，就說這個邏輯變量取值為“假”或“0”.

對于上面的四個節(jié)點有布爾作用的網(wǎng)絡同步問題，可以把每個節(jié)點的狀態(tài)看成一個邏輯變量，狀態(tài)為1代表這個命題是真的，狀態(tài)為0代表這個命題是假的.

可以將以上問題轉(zhuǎn)化為以下邏輯方程:

若在T+k時刻網(wǎng)絡同步，則A、B、C、D四個邏輯變量在T+k時刻同時取值為“真(即1)”或“假(0)”.那么，應用邏輯算子，給出(19)式和(20)式:

對(19)式在T+1時刻的邏輯值，有如下計算:

根據(jù)(21)式可以得出ac(b+d-bd)=1，則共有三個解:

這就意味著，對于在T時刻為上面解中的三種狀態(tài)時，在下一時刻該網(wǎng)絡可以達到同步狀態(tài)為1.同樣地，可以用式(20)解出，對于在T時刻四個結點狀態(tài)只有為0000時，在下一時刻該網(wǎng)絡可以達到同步狀態(tài)為0，與真值表分析法結果相同.

在第3部分中，介紹了一個邏輯函數(shù)，可以找到一個過渡矩陣L，使下一狀態(tài)x(t+1)=Lx(t).對于一個已知的初始狀態(tài)，在何時可以達到同步狀態(tài)為1的問題，可以歸納為解x(t)=的問題.同樣的，當 x(t)=時，可以達到同步狀態(tài)為0.

［1］ Liang S，F(xiàn)uhrman S，Somogyi R.A general reverse engineering algorithm for inference of genetic network architectures［J］.In Paciac Symposium on Biocomputing，1998，3:18-29.

［2］ Pal R.Generating Boolean Networks with a Prescribed Attractor Structure［J］.Bioinformatics，2002，18:261-274.

［3］ Cheng D.Controllability and Observability of Boolean control networks.IEEE Trans，2009，45:1659-1667.

［4］ 程代展，齊洪勝.矩陣的半張量積［M］.北京:科學出版社，2007.

［5］ Cheng Daizhan.Semi-tensor product of matrices and its app lication to morgen’s problem［J］.Science in China(Series F)，2001，44(3):195-212.

［6］ Cheng Daizhan.Some application s of Semi-tensor product of m atrices in algebra［J］.Computers and Mathematics with Applications，2006，52:1045.

［7］ Zhou J，Chen T.Synchronization in general complex delayed dynamical Networks IEEE Trans on Circuit System，2006，53(3):7332-44.