布尔函数

在数学中，布尔函数（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的“二进制序列”

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

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

这里的 $a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}$ 。序列 $a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}$ 的值因此还唯一的表示一个布尔函数。

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

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

f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})+x_{1}h(x_{2},\ldots ,x_{n})

，

这里的 $g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})$ 并且 $h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})+f(1,x_{2},\ldots ,x_{n})$ 。

实际上，

如果

x_{1}=0

，则

x_{1}h=0

，并因此

f(0,\ldots )=f(0,\ldots )

；

如果

x_{1}=1

，则

x_{1}h=h

，并因此

f(1,\ldots )=f(0,\ldots )+f(0,\ldots )+f(1,\ldots )

。

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

例如，让我们构造一个 $f(x,y)=x\lor y$ （逻辑或）的ANF：

f(x,y)=f(0,y)+x(f(0,y)+f(1,y))

；

因为

f(0,y)=0\lor y=y

并且

f(1,y)=1\lor y=1

，可以得出

f(x,y)=y+x(y+1)

；

通过打开括号我们得到最终的ANF：

f(x,y)=y+xy+x=x+y+xy

。