布尔函数

在数学中，布尔函数（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多项式。

$f(x_1, x_2, \ldots , x_n) = \!$	$a_0 + \!$
	$a_1\; x_1 + a_2\; x_2 + \ldots + a_n\; x_n + \!$
	$a_{1,2}\; x_1 x_2 + \ldots + a_{n-1,n}\; x_{n-1} x_n + \!$
	$\ldots \quad \ldots \quad \ldots + \!$
	$a_{1,2,\ldots,n}\; x_1 x_2 \ldots x_n \!$

这里的$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_1x_2x_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 + x y + x = x + y + x y$ 。

参见

• 布尔代数主题列表
• 真值函数
• 零阶逻辑

外部链接

• Boolean Planet —boolean functions in cryptography.