布尔函数

汉漢▼▲

在数学中，布尔函数描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中(参见 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_1x_1 + a_2x_2 + \ldots + a_nx_n + \!$
	$a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!$
	$\ldots + \!$
	$a_{1,2,\ldots,n}x_1x_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 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 + x y + x = x + y + x y$ 。