布尔函数的代数厚度

Algebraic Thickness of Boolean Functions

基于布尔函数的代数次数和代数厚度,给出了布尔函数和其分解函数的代数厚度的关系,利用递归和反证法导出了n元布尔函数代数厚度的上界是2**(n-1),这个上界回答了"是否存在代数厚度大于2**(n-1)的n元布尔函数"这个公开问题.在此基础上改进了n元k(2≤k≤(n-1)/2)次基本对称布尔函数的代数厚度的上界,同时也得到了布尔函数的代数厚度的一些性质.

Based on the algebraic degree and the algebraic thickness of Boolean functions, the relationship of algebraic thickness between a Boolean function and their decomposing Boolean functions is given, and the upper bound on the algebraic thickness of Boolean functions with n variables is 2 ＊ ＊ （ n - 1） by the recurrence method and the reduction to absurdity. The upper bound answers the open problem： ＂whether there exists a Boolean function with n variables whose algebraic thickness is strictly greater than 2 ＊ ＊ （ n - 1）＂. At the end of this paper, according to this fact an upper bound on algebraic thickness of elementary symmetric Boolean functions of n variables with algebraic degree k （ 2 ≤ k ≤ （ n - 1 ）/2） is improved, and some properties on algebraic thickness of Boolean functions are derived.