布尔函数的代数厚度  

Algebraic Thickness of Boolean Functions

作　　者：周宇[1] 汪小芬[1] 罗彦锋[2] 肖国镇[1] 

机构地区：[1]西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071 [2]兰州大学数学与统计学院,甘肃兰州730000

出　　处：《电子学报》2009年第7期1412-1415,共4页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60773003;60503010;60603010);中国科学院研究生院信息安全国家重点实验室开放课题(No.03-06);陕西省自然科学基金(No.2006F19);陕西省自然科学基础计划基金(No.SJ08-ZT14)

摘　　要：基于布尔函数的代数次数和代数厚度,给出了布尔函数和其分解函数的代数厚度的关系,利用递归和反证法导出了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.

关 键 词：布尔函数 代数正规型 代数厚度 基本对称布尔函数 

分 类 号：TN918.1[电子电信—通信与信息系统]