1. 首页 / 知识 /  正文

什么是布尔函数 爱问知识人

什么是布尔函数 爱问知识人

布尔函数在数学中,布尔函数通常是如下形式的函数F(b1,b2,。。。,bn)带有n个来自两元素布尔代数{0,1}的布尔变量bi,F的取值也在{0,1}中。在一般的定义域上的,取值在{0,1}中的函数也叫做布尔值函数,所以布尔函数是它的特殊情况。
带有定义域{1,2,3,。。。}的这种函数通常叫做二进制序列,就是说0和1的无限序列;通过限制到{1,2,3,。。。,n},布尔函数是编码长度为n的序列的自然的方法。它有2^{2^n}个布尔函数;它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。
布尔函数的性质在密码学中扮演关键角色,特别是在对称密钥算法的设计中(参见S-box)。在布尔值函数上的布尔运算逐点(point-wise)组合值(比如通过XOR或其他布尔运算符)。布尔函数可以唯一的写为积(AND)之和(XOR)。这叫做代数范式(ANF)。
f(x_1,x_2,ldots,x_n)=!a_0+!a_1x_1+a_2x_2+ldots+a_nx_n+!a_{1,2}x_1x_2+a_{n-1,n}x_x_n+!ldots+!序列a_0,a_1,ldots,a_{1,2,ldots,n}的值因此还唯一的表示一个布尔函数。
布尔函数的代数度被定义为出现在乘积项中的x_i的最高数。