Cfxtrjtrk

在数学中，布尔函数（Boolean function）描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中（参见S-box）。

有限布尔函数

在数学中，有限布尔函数是如下形式的函数f : B^k → B，这里的B = {0, 1}是布尔域，而k是非负整数。在k = 0的情况下，函数简单的是B的一个恒定元素。

更一般的说，形如f : X → B函数，这里的X是任意集合，是布尔值函数。如果X = M = {1, 2, 3, …}，则f是“二进制序列”，就是说0和1的无限序列。如果X = [k] = {1, 2, 3, …, k}，则f是长度为k的“二进制序列”

有22k{displaystyle 2^{2^{k}}}个这种函数。

代数范式

布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。

f(x1,x2,…,xn)={displaystyle f(x_{1},x_{2},ldots ,x_{n})=!}	a0+{displaystyle a_{0}+!}
	a1x1+a2x2+…+anxn+{displaystyle a_{1};x_{1}+a_{2};x_{2}+ldots +a_{n};x_{n}+!}
	a1,2x1x2+…+an−1,nxn−1xn+{displaystyle a_{1,2};x_{1}x_{2}+ldots +a_{n-1,n};x_{n-1}x_{n}+!}
	………+{displaystyle ldots quad ldots quad ldots +!}
	a1,2,…,nx1x2…xn{displaystyle a_{1,2,ldots ,n};x_{1}x_{2}ldots x_{n}!}

这里的a0,a1,…,a1,2,…,n∈{0,1}∗{displaystyle a_{0},a_{1},ldots ,a_{1,2,ldots ,n}in {0,1}^{*}}。
序列a0,a1,…,a1,2,…,n{displaystyle a_{0},a_{1},ldots ,a_{1,2,ldots ,n}}的值因此还唯一的表示一个布尔函数。

布尔函数的代数次数被定义为出现在乘积项中的xi{displaystyle x_{i}}的最高次数。所以f(x1,x2,x3)=x1+x3{displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{3}}有次数1（线性），而f(x1,x2,x3)=x1+x1x2x3{displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}}有次数3（立方）。

对于每个函数f{displaystyle f}都有一个唯一的ANF。只有四个函数有一个参数: f(x)=0{displaystyle f(x)=0} ，f(x)=1{displaystyle f(x)=1} ，f(x)=x{displaystyle f(x)=x} ，f(x)=1+x{displaystyle f(x)=1+x} ；它们都可以在ANF中给出。要表示有多个参数的函数，可以使用如下等式：

f(x1,x2,…,xn)=g(x2,…,xn)+x1h(x2,…,xn){displaystyle f(x_{1},x_{2},ldots ,x_{n})=g(x_{2},ldots ,x_{n})+x_{1}h(x_{2},ldots ,x_{n})} ，

这里的g(x2,…,xn)=f(0,x2,…,xn){displaystyle g(x_{2},ldots ,x_{n})=f(0,x_{2},ldots ,x_{n})} 并且 h(x2,…,xn)=f(0,x2,…,xn)+f(1,x2,…,xn){displaystyle h(x_{2},ldots ,x_{n})=f(0,x_{2},ldots ,x_{n})+f(1,x_{2},ldots ,x_{n})} 。

实际上，

如果x1=0{displaystyle x_{1}=0} ，则x1h=0{displaystyle x_{1}h=0} ，并因此f(0,…)=f(0,…){displaystyle f(0,ldots )=f(0,ldots )} ；

如果x1=1{displaystyle x_{1}=1} ，则x1h=h{displaystyle x_{1}h=h} ，并因此f(1,…)=f(0,…)+f(0,…)+f(1,…){displaystyle f(1,ldots )=f(0,ldots )+f(0,ldots )+f(1,ldots )} 。

因为g{displaystyle g}和h{displaystyle h}二者都有比f{displaystyle f}少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。

例如，让我们构造一个f(x,y)=x∨y{displaystyle f(x,y)=xlor y}（逻辑或）的ANF：

f(x,y)=f(0,y)+x(f(0,y)+f(1,y){displaystyle f(x,y)=f(0,y)+x(f(0,y)+f(1,y)} ；

因为f(0,y)=0∨y=y{displaystyle f(0,y)=0lor y=y} 并且f(1,y)=1∨y=1{displaystyle f(1,y)=1lor y=1}，可以得出f(x,y)=y+x(y+1){displaystyle f(x,y)=y+x(y+1)}；

通过打开括号我们得到最终的ANF：f(x,y)=y+xy+x=x+y+xy{displaystyle f(x,y)=y+xy+x=x+y+xy} 。

参见

• 布尔代数主题列表


• 真值函数


• 零阶逻辑

外部链接

• 
  Boolean Planet^{[永久失效連結]}—boolean functions in cryptography.