布尔函数

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

 有限布尔函数 

在数学中，有限布尔函数是如下形式的函数，这里的是布尔域，而  是非负整数。在  的情况下，函数简单的是  的一个恒定元素。

更一般的说，形如  函数，这里的  是任意集合，是布尔值函数。如果，则  是“二进制序列”，就是说0和1的无限序列。如果，则  是长度为  的“二进制序列”

有个这种函数。

 代数范式 

布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。

这里的。
序列的值因此还唯一的表示一个布尔函数。

布尔函数的代数次数被定义为出现在乘积项中的  的最高次数。所以有次数1（线性），而有次数3（立方）。

对于每个函数都有一个唯一的ANF。只有四个函数有一个参数:  ， ， ， ；它们都可以在ANF中给出。要表示有多个参数的函数，可以使用如下等式：
 ，
这里的 并且  。

实际上，
如果 ，则 ，并因此 ；
如果 ，则 ，并因此 。
因为和二者都有比少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。

例如，让我们构造一个（逻辑或）的ANF：
 ；
因为 并且，可以得出；
通过打开括号我们得到最终的ANF： 。

 参见 
 布尔代数主题列表
 真值函数
 零阶逻辑

 外部链接 
 Boolean Planet —boolean functions in cryptography.

B
B
B