Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity. For both Boolean values $b\in\{0,1\}$, we obtain a formula for $b$-certificate complexity and consequently, we develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean NCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetric Boolean NCFs.
翻译:布尔巢型运河功能(NCFs)在分子监管网络、工程和计算机科学中具有重要的应用性。在本文中,我们研究了它们的证书复杂性。对于布尔值 $b\ in ⁇ 0,1 ⁇ $,我们获得了一个美元证书复杂性的公式,因此,我们开发了一个关于NCF证书复杂性公式的直接证明。对称是布尔函数的另一个有趣的属性,我们大大简化了最近一些理论的证明,以证明NCFs部分对称。我们还描述了美元对称NCFs的正数正数形式。我们获得了一套美元可变值美元对称布伦型NCFs的基本公式,用于$=1,\dots,n美元。我们特别列举了强称不对称布尔值的NCFs。