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