基于半张量积方法的布尔函数矩阵表示的一些应用

doi:10.7523/j.issn.2095-6134.2012.6.004

中国科学院大学学报 ›› 2012, Vol. ›› Issue (6): 743-749.DOI: 10.7523/j.issn.2095-6134.2012.6.004

基于半张量积方法的布尔函数矩阵表示的一些应用

赵寅¹, 高旭², 程代展¹

1. 中国科学院数学与系统科学研究院系统控制重点实验室, 北京 100190;
2. 伊利诺伊大学芝加哥分校数学、统计与计算机科学系, 芝加哥 60607

收稿日期:2011-06-28 修回日期:2011-09-27 发布日期:2012-11-15
通讯作者: 程代展

Some applications of the matrix expression of Boolean function via semi-tensor product

ZHAO Yin¹, GAO Xu², CHENG Dai-Zhan¹

1. Key Lab of Systems and Control, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
2. Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago 60607, USA

Received:2011-06-28 Revised:2011-09-27 Published:2012-11-15
Supported by:
Supported by National Natural Science Foundation of China(61074114,60821091) 

摘要/Abstract

摘要： 利用矩阵的半张量积, 布尔函数可以被表示为矩阵形式. 通过这个方法, 我们给出了布尔函数从真值表到多项式形式转换的一个简洁的证明, 并研究了布尔函数的线性结构.

关键词: 布尔函数, 半张量积, 真值表, 多项式表示, 线性结构

Abstract: 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.

Key words: Boolean function, semi-tensor product, truth table, polynomial form, linear structure

中图分类号:

O141

赵寅, 高旭, 程代展. 基于半张量积方法的布尔函数矩阵表示的一些应用[J]. 中国科学院大学学报, 2012, (6): 743-749.

ZHAO Yin, GAO Xu, CHENG Dai-Zhan. Some applications of the matrix expression of Boolean function via semi-tensor product[J]. , 2012, (6): 743-749.

参考文献

[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.

基于半张量积方法的布尔函数矩阵表示的一些应用

Some applications of the matrix expression of Boolean function via semi-tensor product

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	宋佳, 陈玉福. Hamming约束集的计数问题[J]. 中国科学院大学学报, 2015, 32(6): 721-727.
[2]	孙光洪, 武传坤. Gold 型Bent函数的两个注记[J]. 中国科学院大学学报, 2010, 27(2): 257-262.