布尔函数

维库，知识与思想的自由文库

在数学中，布尔函数通常是如下形式的函数

F(b₁, b₂, ..., b_n)

带有 n 个来自两元素布尔代数 {0,1} 的布尔变量 b_i，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_{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 (立方)。