查看“︁布尔函数”︁的源代码

{{Multiple issues|
{{expert|time=2014-01-18}}
{{Unreferenced|time=2022-10-09T15:09:29+00:00}}
}}
{{NoteTA
|T=zh-cn:布尔函数; zh-tw:布林函數
|G1 = IT
|G2 = Math
}}

{{各種函數}}


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

== 有限布尔函数 ==

在[[数学]]中，'''有限布尔函数'''是如下形式的[[函数]]f : '''B'''<sup>''k''</sup> → '''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''的“二进制序列”

有<math>2^{2^k}</math>个这种函数。

== 代数范式 ==

布尔函数可以唯一的写为积（[[逻辑合取|AND]]）之和（[[逻辑异或|XOR]]）。这叫做'''代数范式'''（ANF），也叫做[[Zhegalkin多项式]]。

{| cellpadding="4"
|-
|<math>f(x_1, x_2, \ldots , x_n) = \!</math>
|<math>a_0 + \!</math>
|-
|
|<math>a_1\; x_1 + a_2\; x_2 + \ldots + a_n\; x_n + \!</math>
|-
|
|<math>a_{1,2}\; x_1 x_2 + \ldots + a_{n-1,n}\; x_{n-1} x_n + \!</math>
|-
|
|<math>\ldots \quad \ldots \quad \ldots + \!</math>
|-
|
|<math>a_{1,2,\ldots,n}\; x_1 x_2 \ldots x_n \!</math>
|}

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

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


对于每个函数<math>f</math>都有一个唯一的ANF。只有四个函数有一个参数: <math>f(x)=0</math> ，<math>f(x)=1</math> ，<math>f(x)=x</math> ，<math>f(x)=1+x</math> ；它们都可以在ANF中给出。要表示有多个参数的函数，可以使用如下等式：
:<math>f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) + x_1 h(x_2,\ldots,x_n)</math> ，
这里的<math>g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n)</math> 并且 <math>h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) + f(1,x_2,\ldots,x_n)</math> 。

实际上，
:如果<math>x_1=0</math> ，则<math>x_1 h = 0</math> ，并因此<math>f(0,\ldots) = f(0,\ldots)</math> ；
:如果<math>x_1=1</math> ，则<math>x_1 h = h</math> ，并因此<math>f(1,\ldots) = f(0,\ldots) + f(0,\ldots) + f(1,\ldots)</math> 。
因为<math>g</math>和<math>h</math>二者都有比<math>f</math>少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。


例如，让我们构造一个<math>f(x,y)= x \lor y</math>（逻辑或）的ANF：
:<math>f(x,y) = f(0,y) + x(f(0,y)+f(1,y))</math> ；
:因为<math>f(0,y)=0 \lor y = y</math> 并且<math>f(1,y)=1 \lor y = 1</math>，可以得出<math>f(x,y) = y + x (y + 1)</math>；
:通过打开括号我们得到最终的ANF：<math>f(x,y) = y + x y + x = x + y + x y</math> 。

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

== 外部链接 ==
* [http://www.isrc.qut.edu.au/people/fuller/ Boolean Planet] {{Wayback|url=http://www.isrc.qut.edu.au/people/fuller/ |date=20080820091031 }}—boolean functions in cryptography.

{{数理逻辑|state=expanded}}
[[Category:密码学|B]]
[[Category:布尔代数|B]]
[[Category:函数|B]]