布尔函数可以唯一的写为积(AND)之和(XOR)。这叫做代数范式(ANF),也叫做Zhegalkin多项式。
|
|
|
|
|
|
|
|
|
|
这里的 。
序列 的值因此还唯一的表示一个布尔函数。
布尔函数的代数次数被定义为出现在乘积项中的 的最高次数。所以 有次数1(线性),而 有次数3(立方)。
对于每个函数 都有一个唯一的ANF。只有四个函数有一个参数: , , , ;它们都可以在ANF中给出。要表示有多个参数的函数,可以使用如下等式:
- ,
这里的 并且 。
实际上,
- 如果 ,则 ,并因此 ;
- 如果 ,则 ,并因此 。
因为 和 二者都有比 少的参数,可以得出递归的使用这个过程将完成于只有一个变量的函数。
例如,让我们构造一个 (逻辑或)的ANF:
- ;
- 因为 并且 ,可以得出 ;
- 通过打开括号我们得到最终的ANF: 。