本页使用了标题或全文手工转换

布尔函数

维基百科,自由的百科全书
跳转至: 导航搜索

数学中,布尔函数(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的“二进制序列”

2^{2^k}个这种函数[為何?]

代数范式[编辑]

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

f(x_1, x_2, \ldots , x_n) = \! a_0 + \!
a_1\; x_1 + a_2\; x_2 + \ldots + a_n\; x_n + \!
a_{1,2}\; x_1 x_2 + \ldots + a_{n-1,n}\; x_{n-1} x_n + \!
\ldots \quad \ldots \quad \ldots + \!
a_{1,2,\ldots,n}\; x_1 x_2 \ldots x_n \!

这里的 a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^* 。 序列a_0,a_1,\ldots,a_{1,2,\ldots,n}的值因此还唯一的表示一个布尔函数。

布尔函数的代数次数被定义为出现在乘积项中的x_i的最高次数。所以f(x_1,x_2,x_3) = x_1 + x_3有次数1(线性),而f(x_1,x_2,x_3) = x_1 + x_1x_2x_3有次数3(立方)。


对于每个函数f都有一个唯一的ANF。只有四个函数有一个参数: f(x)=0f(x)=1f(x)=xf(x)=1+x ;它们都可以在ANF中给出。要表示有多个参数的函数,可以使用如下等式:

f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) + x_1 h(x_2,\ldots,x_n)

这里的g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) 并且 h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) + f(1,x_2,\ldots,x_n)

实际上,

如果x_1=0 ,则x_1 h = 0 ,并因此f(0,\ldots) = f(0,\ldots)
如果x_1=1 ,则x_1 h = h ,并因此f(1,\ldots) = f(0,\ldots) + f(0,\ldots) + f(1,\ldots)

因为gh二者都有比f少的参数,可以得出递归的使用这个过程将完成于只有一个变量的函数。


例如,让我们构造一个f(x,y)= x \lor y(逻辑或)的ANF:

f(x,y) = f(0,y) + x(f(0,y)+f(1,y)
因为f(0,y)=0 \lor y = y 并且f(1,y)=1 \lor y = 1,可以得出f(x,y) = y + x (y + 1)
通过打开括号我们得到最终的ANF:f(x,y) = y + x y + x = x + y + x y

参见[编辑]

外部连接[编辑]