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