| 本条目存在以下问题,请协助 改善本条目或在 讨论页针对议题发表看法。
| 此条目需要 精通或熟悉相关主题的编者参与及协助编辑。 (2014年1月18日) 请邀请适合的人士改善本条目。更多的细节与详情请参见讨论页。 |
|
在数学中,布尔函数(Boolean function),又称逻辑函数,描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色,特别是在对称密钥算法的设计中(参见S-box)。
在数学中,有限布尔函数是如下形式的函数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:
。