布尔函数

在数学中，布尔函数（Boolean function）描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中（参见S-box）。在数学中，有限布尔函数是如下形式的函数f : Bk → B，这里的B = {0, 1}是布尔域，而k是非负整数。在k = 0的情况下，函数简单的是B的一个恒定元素。更一般的说，形如f : X → B函数，这里的X是任意集合，是布尔值函数。如果X = M = {1, 2, 3, …}，则f是“二进制序列”，就是说0和1的无限序列。如果X = = {1, 2, 3, …, k}，则f是长度为k的“二进制序列”有 2 2 k {displaystyle 2^{2^{k}}} 个这种函数。布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。这里的 a 0 , a 1 , … , a 1 , 2 , … , n ∈ { 0 , 1 } ∗ {displaystyle a_{0},a_{1},ldots ,a_{1,2,ldots ,n}in {0,1}^{*}} 。 序列 a 0 , a 1 , … , a 1 , 2 , … , n {displaystyle a_{0},a_{1},ldots ,a_{1,2,ldots ,n}} 的值因此还唯一的表示一个布尔函数。布尔函数的代数次数被定义为出现在乘积项中的 x i {displaystyle x_{i}} 的最高次数。所以 f ( x 1 , x 2 , x 3 ) = x 1 + x 3 {displaystyle 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 {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中给出。要表示有多个参数的函数，可以使用如下等式：这里的 g ( x 2 , … , x n ) = f ( 0 , x 2 , … , x n ) {displaystyle g(x_{2},ldots ,x_{n})=f(0,x_{2},ldots ,x_{n})} 并且 h ( x 2 , … , x n ) = f ( 0 , x 2 , … , x n ) + f ( 1 , x 2 , … , x n ) {displaystyle h(x_{2},ldots ,x_{n})=f(0,x_{2},ldots ,x_{n})+f(1,x_{2},ldots ,x_{n})} 。实际上，因为 g {displaystyle g} 和 h {displaystyle h} 二者都有比 f {displaystyle f} 少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。例如，让我们构造一个 f ( x , y ) = x ∨ y {displaystyle f(x,y)=xlor y} （逻辑或）的ANF：