布尔函数的代数厚度研究

"布尔函数的代数厚度是布尔函数理论中的一个重要概念，涉及到布尔函数的代数性质和结构分析。本文由周宇、汪小芬、罗彦锋和肖国镇共同撰写，发表在2009年的《通信学报》上，主要探讨了布尔函数的代数厚度及其上界，并对基本对称布尔函数的代数厚度进行了深入研究。" 布尔函数是布尔代数中的核心元素，通常用于表示和分析逻辑关系。代数厚度是衡量布尔函数复杂度的一个度量，它定义为布尔函数在标准正则表达式中所需的最少项数。在布尔函数的研究中，代数厚度是一个关键参数，因为它直接影响到函数的可计算性、电路设计以及密码学应用等多个方面。 文章首先建立了布尔函数与其分解函数的代数厚度之间的关系。通过对布尔函数的代数次数（即函数的最高阶非零项的次数）的分析，作者们运用递归方法和反证法证明了n元布尔函数的代数厚度上界是2^(n-1)。这一发现解答了一个开放性问题，即是否存在代数厚度超过2^(n-1)的n元布尔函数。这意味着对于所有n元布尔函数，其代数厚度都可被限制在这个数值之内。 进一步，研究者们将焦点转向了n元k次基本对称布尔函数，其中2≤k≤(n-1)/2。他们改进了这类函数的代数厚度上界，这有助于更深入地理解这些特殊布尔函数的结构特性。同时，文章还揭示了布尔函数代数厚度的一些通用性质，这为布尔函数的理论研究和实际应用提供了理论支持。 这篇论文为布尔函数的理论研究提供了新的见解，尤其是关于代数厚度的计算和上界问题，对于理解和优化布尔函数在信息处理、计算机科学和密码学中的应用具有重要意义。通过深入研究布尔函数的代数结构，可以期望推动相关领域的理论发展和技术进步。