合取布尔网络的能观性

丁路青，李睿

（大连理工大学数学科学学院，大连116024）

0 引言

为了深入研究生物遗传机理，20世纪60年代末Kauffman提出使用布尔网络模型刻画细胞和基因调控网络的理论，用二进制1（转录）和0（不转录）表示基因的两种转录状态，它们之间的相互作用通过以布尔函数形式给出的逻辑规则表示。布尔网络模型是模拟网络动态过程的基本框架，尤其是在生物背景下，该模型已经有了丰富的理论成果[1-3]。

程代展教授及其团队提出使用矩阵半张量积研究布尔网络，这个方法的基本思想是把布尔网络转化成一个离散时间线性系统，使布尔网络的表示代数化，形式变得简单[4]，从而能够使用许多可用于线性状态空间模型的标准数学工具，进而有助于在理论框架内研究布尔网络模型，为后续研究奠定了一个合理的基础，获得了一系列优秀的研究成果[5-25]。

合取布尔网络是布尔函数值的更新规则仅包含and算子的一类特殊布尔网络，有着较好的性质[26-28]，故对其研究受到特别的关注。文献[29]研究了合取布尔网络的轨道控制和状态控制集，给出集合是网络控制集的充要条件和确切的控制规则。文献[30]考虑寻找直接影响输入的最小状态变量集，使最终的合取布尔网络能控，给出了能控的充要条件和用于检测能控性的算法，并证明了合取布尔网络的最小能控性问题是NP难的。文献[31]研究了合取布尔网络的最小能观性问题，给出了具有多项式复杂度的最小能观性判断算法。……