檢視布尔函数的原始碼

{| class="wikitable" align="right"

|-

| style="background: #66CCFF" align= center|  '''<big>布尔函数</big> '''

|-

|[[File:布尔函数.jpg|缩略图|居中| [https://img.wesiedu.com/upload/c/ce/cce14a650426e3e6894bc380d32c1367.jpg 原图链接]]] 

|-

| style="background: #66CCFF" align= center|

|-

| align= light|

中文名: 布尔函数

外文名: Boolean function

|}
在数学中，'''[[布尔函数]]'''（Boolean function）描述如何基于对布尔输入的某种逻辑计算确定布尔值输出，它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中（参见S-box）。
在数学中，布尔函数通常是如下形式的函数：
F(b1,b2,...,bn)
带有 n 个来自两元素布尔代数 {0,1} 的布尔变量 bi，F 的取值也在 {0,1} 中。
在一般的定义域上的，取值在 {0,1} 中的函数也叫做布尔值函数，所以布尔函数是它的特殊情况。<ref>[ https://img.wesiedu.com/upload/c/ce/cce14a650426e3e6894bc380d32c1367.jpg], 微思i, </ref>
==简介==
布尔函数是研究密码算法和密码技术的重要工具，无论在流密码还是在分组密码中，在对称还是在非对称密码中都有重要的应用。
 
带有定义域 {1,2,3,... } 的这种函数通常叫做二进制序列，就是说 0 和 1 的无限序列；通过限制到 { 1,2,3,...,n }，布尔函数是编码长度为 n 的序列的自然的方法。
它有 2^{2^n} 个布尔函数；它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中(参见 S-box)。
在布尔值函数上的布尔运算逐点（point-wise）组合值（比如通过 XOR 或其他布尔运算符）。
布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式 (ANF），也叫做Zhegalkin多项式。
f(x1,x2,...,xn) =a0 +a1x1 + a2x2 + ... + anxn +
a{1,2}x1x2 + a{n-1,n}x(n-1）xn +
... +
a{1,2,...,n}x1x2...xn
序列 a0,a1,...,a{1,2,...,n} 的值因此还唯一的表示一个布尔函数。布尔函数的代数度被定义为出现在乘积项中的 xi 的最高数。所以 f(x1,x2,x3） = x1 + x3 有度数 1 （线性），而 f(x1,x2,x3） = x1 + x1x2x3 有度数 3 （立方）。
 
==特点==
布尔函数必须满足一定的密码学性质，以保证密码系统符合安全性的基本要求，并能抵抗现有的各种攻击。下面介绍几条衡量布尔函数密码学性质的指标。
为了抵抗最佳仿射逼近攻击，布尔函数必须与仿射函数保持尽可能大的汉明距离。为了衡量布尔函数抵抗“仿射攻击”的能力，引入了非线性度的概念。
 
==代数范式==
布尔函数可以唯一的写为[[积（AND）]]之[[和（XOR）]]。这叫做[[代数范式（ANF]]），也叫做[[Zhegalkin多项式]]。
这里的序列 的值因此还唯一的表示一个布尔函数。布尔函数的代数次数被定义为出现在乘积项中的 xi 的最高次数。所以 f(x1,x2,x3） = x1 + x3 有次数 1 （线性），而 f(x1,x2,x3） = x1 + x1x2x3 有次数 3 （立方）。
对于每个函数 f 都有一个唯一的 ANF。只有四个函数有一个参数: f(x) = 0,f(x) = 1,f(x) = x,f(x) = 1 + x （它们都可以在 ANF 中给出），要表示有多个参数的函数，可以使用如下等式： ，这里的 并且。实际上，如果 x1 = 0 则 x1h = 0 并因此 ；如果 x1 = 1 则 x1h = h 并因此。因为 g 和 h 二者都有比 f 少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。例如，让我们构造一个 （逻辑或）的 ANF: f(x,y) = f(0,y) + x(f(0,y) + f（1,y））；因为 并且 ，可以得出 f(x,y) = y + x(y + 1）；通过打开括号我们得到最终的 ANF: f(x,y) = y + xy + x = x + y + xy。
一个布尔函数介绍了如何确定一个布尔值输出基于某种逻辑输入计算的布尔值。这些职能发挥作用的问题的基本理论，复杂性 ，以及作为设计的电路芯片和数字电脑。布尔函数的性质研究中发挥关键作用密码学 ，特别是在设计的对称密钥算法 （见替代框）。
布尔函数通常代表中的句子命题逻辑 ，有时作为多元多项式超过绿 ⑵，但更有效的申述， 二元决策图 （BDD）的， 正常的否定形式 ，与命题向无环图 （PDAG）。
在合作博弈论，布尔函数被称为游戏） 简单的游戏 （表决；这个概念应用到解决问题的社会选择理论。
 
==密码学中==
布尔函数是流密码系统的核心部件，研究布尔函数是流密码系统重点。代数攻击是密码学的研究热点。布尔函数必须具有好的密码性质:平衡，高的代数免疫，高的代数次数，高的非线性度，代数攻击的能力。
==对称布尔函数==
对于 n元d次初等对称布尔函数 X(d,n) ，当，即证明了 X(d,n)不是平衡的，并且利用泰勒展式估计了w的大小；对于给定的 wq 和 t，证明了如果s 充分大，则
即证明了 X(d,n)不是平衡的
==参见==
代数集
布尔代数（逻辑）
布尔代数主题
布尔域
布尔逻辑
布尔值函数
逻辑连词
真值函数
真值表
对称布尔函数
决策树模型
回避的布尔函数
 

== 参考来源 ==
{{reflist}}

[[Category: 310 數學總論]]