布尔函数

函数的一种,描述如何基于对布尔输入的某种逻辑计算确定布尔值输出


数学中,布尔函数(Boolean function),又称逻辑函数,描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字电脑晶片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色,特别是在对称密钥算法的设计中(参见S-box)。

有限布尔函数

数学中,有限布尔函数是如下形式的函数f : BkB,这里的B = {0, 1}是布尔域,而k是非负整数。在k = 0的情况下,函数简单的是B的一个恒定元素。

更一般的说,形如f : XB函数,这里的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: 

参见

外部链接