利用矩阵的半张量积, 布尔函数可以被表示为矩阵形式. 通过这个方法, 我们给出了布尔函数从真值表到多项式形式转换的一个简洁的证明, 并研究了布尔函数的线性结构.
Boolean function can be expressed in matrix form using semi-tensor product of matrices. Using this approach, we give a neat proof of the conversion of a Boolean function from the truth table to the polynomial form. The linear structure of Boolean functions is also investigated.
[1] Macwilliams F, Sloane N. The theory of error-correcting codes[M]. Amsterdam: North-Holland, 1977.
[2] 温巧燕, 钮心忻, 杨义先. 现代密码学中的布尔函数[M]. 北京: 科学出版社, 2000.
[3] Carlet C. Boolean functions for cryptography and error-correcting codes [C]//Crama Y, Hammer P (ed). Boolean Methods and Models in Mathematics, Computer Science, and Engineering. Cambridge: Cambridge Univ Press, 2010.
[4] Zhang Y J. Cryptographic properties of permutation symmetric Boolean functions [D]. Beijing: Graduate University of Chinese Academy of Sciences, 2010(in Chinese). 张艳娟. 置换对称布尔函数的密码学性质 [D]. 北京: 中国科学院研究生院, 2010.
[5] Kauffman S A. Metabolic stability and epigenesis in randomly constructed genetic nets[J]. J Theoretical Biology, 1969, 22(3): 437-467.
[6] Ideker T, Galitski T, Hood L. A new approach to decoding life: systems biology[J]. Annu Rev Genomics Hum Genetic, 2001, 2: 343-372.
[7] Farrow C, Heidel J, Maloney H, et al. Scalar equations for synchronous Boolean networks with biological applications[J]. IEEE Trans Neural Networks, 2004, 15(2): 348-354.
[8] Ben-Or M, Linial N. Collective coin flipping[M]. Israel: Leibniz Center for Research in Computer Science, Dept of Computer Science, Hebrew University of Jerusalem, 1987.
[9] Hammer P, Holzman R. Approximations of pseudo-Boolean functions: applications to game theory[J]. Mathematical Methods of Operations Research, 1992, 36(1): 3-21.
[10] O'Donnell R. Some topics in analysis of Boolean functions [C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing. Canada: Victoria, 2008: 569-578.
[11] Akers S. Binary decision diagrams[J]. IEEE Trans Computer, 1978, C-27(6): 509-516.
[12] Wachter M, Haenni R. Propositional DAGs: a new graph-based language for representing Boolean functions [C]//Proc KR'06, 10th International Conference on Principles of Knowledge Representation and Reasoning. UK: Lake District, 2006, 6: 275-285.
[13] Dubuc S. Characterization of linear structures[J]. Designs, Codes and Cryptography, 2001, 22(1): 33-45.
[14] Cheng D. Semi-tensor product of matrices and its applications-A survey [C]//ICCM 2007. Zhejiang, China, 2007, 3: 641-668.
[15] Cheng D, Qi H, Li Z. Analysis and control of Boolean networks: a semi-tensor product approach[M]. London: Springer, 2011.
