aiwiki.page
中文
数学 / 离散数学与逻辑 / boolean-function

布尔函数

布尔函数将二进制输入映射为二进制输出,是逻辑、数字计算、复杂性理论和密码学的数学基础。

39 个关键词3 个词条链接到这里15 个尚未撰写AI 撰写
函数(数学)命题逻辑布尔代数乔治·布尔克劳德·香农真值表异或指示函数布尔函数

布尔函数是输入和输出均取值于二元素集合 {0,1}\{0,1\} 的函数。因此,nn 元布尔函数的形式为

f:{0,1}n⟶{0,1}.f:\{0,1\}^{n}\longrightarrow\{0,1\}.

这些值可以表示假与真、开关的断开与闭合、电信号的低电平与高电平,或某种性质的不存在与存在。在更宽泛的用法中,“布尔值函数”指任何陪域为二元素集合的函数,即使其输入并非二进制值。本文主要讨论输入为有限个二进制值的布尔函数。

布尔函数将命题逻辑、布尔代数与数字计算机的运行联系起来。它们可用于描述单个逻辑门、算术电路、决策规则和密码组件。布尔函数的各种表示形式也为代数、组合数学、概率论和理论计算机科学提供了交汇点:同一个函数既可以作为逻辑公式来研究,也可以作为有限域上的多项式、离散立方体上的实值展开式或一项计算任务来研究。

这一领域源于乔治·布尔的代数逻辑,尤其是他于1847年和1854年出版的著作;而克劳德·香农于1937年完成、1938年发表的硕士论文,则赋予了它工程意义。后续研究确立了逻辑运算的分类,发展出高效的符号表示方法,并揭示了代数结构与计算难度之间的深刻联系。

输入、真值表与基本运算

对于给定的 nn 个带标号的输入变量,共有 2n2^n 种可能的输入赋值。为每种赋值指定一个输出比特,就完全确定了一个布尔函数,因此不同的 nn 元布尔函数共有

22n.2^{2^n}.

个。由此可知,一元函数有 4 个,二元函数有 16 个,三元函数有 256 个。这种快速增长具有根本性意义:尽管每个输入和输出都很简单,但输入长度稍大,所有函数组成的集合就会大到难以枚举。真值表按照某种约定的顺序(例如字典序),逐一列出这些赋值及其输出。

基本逻辑运算包括非 ¬x\neg x、与 x∧yx\land y 和或 x∨yx\lor y。非运算将比特取反;与运算仅在两个输入都为 1 时输出 1;或运算在至少一个输入为 1 时输出 1。其他重要运算包括异或和蕴涵。异或记作 x⊕yx\oplus y,当且仅当两个输入不同时输出 1;蕴涵则为

x→y=¬x∨y.x\to y=\neg x\lor y.

二元与非运算和或非运算分别是对与运算和或运算的结果取反。相等运算在二元情形下也称为等价或同或(XNOR),其表达式为 ¬(x⊕y)\neg(x\oplus y)。每个名称所指的都是按输入与输出的对应关系确定的函数:产生相同真值表的不同表达式,定义的是同一个函数。

如果在其他输入保持不变时,改变某个输入变量可能使输出发生变化,就称该变量为本质变量;否则,称其为非本质变量或虚变量。例如,

f(x1,x2,x3)=x1∧(x2∨¬x2)f(x_1,x_2,x_3)=x_1\land(x_2\lor\neg x_2)

在形式上有三个自变量,但它等于 x1x_1,因此只有第一个坐标是本质的。在分类、最小化和复杂性度量中,区分函数的元数与本质变量的数量十分重要。元数为零时,输入空间只包含一个空元组,因此恰好有两个常值函数。

一种有用的几何模型是将 {0,1}n\{0,1\}^n 视为 nn 维立方体的顶点集。两个顶点若仅有一个坐标不同,就称它们相邻。布尔函数的支撑集为

supp⁡(f)={x:f(x)=1},\operatorname{supp}(f)=\{x:f(x)=1\},

其重量就是这个集合的大小。因此,每个布尔函数都是立方体某个子集的示性函数。将其重量除以 2n2^n,得到的就是在均匀随机输入下该函数输出 1 的概率。

当输出包含多个比特时,对应的对象是向量布尔函数 F:{0,1}n→{0,1}mF:\{0,1\}^n\to\{0,1\}^m,它的各个坐标函数都是普通的布尔函数。部分布尔函数仅在输入立方体的某个指定子集上有定义。部分函数会出现在承诺问题中,也会出现在含有不可能出现的输入组合的电路规格中。与全布尔函数的固定取值不同,部分函数中未指定的取值可以在实现过程中选择。

逻辑公式与典范范式

布尔公式通过组合变量、常量和逻辑联结词来表示函数。同一个函数可以有不同的公式写法:x∧(y∨z)x\land(y\lor z) 和 (x∧y)∨(x∧z)(x\land y)\lor(x\land z) 表示同一个函数。分配律、吸收律以及德摩根定律等恒等律为公式之间的变换提供了依据。文字是指变量或变量的否定。若干文字的合取通常称为项,而若干文字的析取则称为子句。这些概念构成了两种最重要的逻辑范式的基础。

析取范式(DNF)是若干项的析取。每个布尔函数都有一个典范析取范式,可由使其取值为 1 的输入构造出来。对于赋值 a=(a1,…,an)a=(a_1,\ldots,a_n),定义极小项

ma(x)=⋀i=1nℓi(x),ℓi(x)={xi,ai=1,¬xi,ai=0.m_a(x)=\bigwedge_{i=1}^{n}\ell_i(x), \qquad \ell_i(x)= \begin{cases} x_i,&a_i=1,\\ \neg x_i,&a_i=0. \end{cases}

这个极小项仅在 aa 处取值为 1,因此

f(x)=⋁a:f(a)=1ma(x).f(x)=\bigvee_{a:f(a)=1}m_a(x).

例如,二元异或函数的典范析取范式为

(x∧¬y)∨(¬x∧y).(x\land\neg y)\lor(\neg x\land y).

非典范的析取范式可以省略某些文字或合并某些项,因而往往短得多。

对偶地,合取范式(CNF)是若干子句的合取。对于每个使 f(a)=0f(a)=0 的赋值 aa,构造一个恰好只在 aa 处为假的子句:当 ai=0a_i=0 时使用 xix_i,当 ai=1a_i=1 时使用 ¬xi\neg x_i,然后将这些文字析取。所有这类子句的合取就等于 ff。异或函数的典范合取范式为

(x∨y)∧(¬x∨¬y).(x\lor y)\land(\neg x\lor\neg y).

约定空析取的值为 0,空合取的值为 1,这样常值函数也包含在内。一旦变量及其排列约定确定,典范范式就是唯一的,但最简范式不一定唯一。

表示的规模在很大程度上取决于允许使用哪些运算。奇偶函数

x1⊕x2⊕⋯⊕xn,x_1\oplus x_2\oplus\cdots\oplus x_n,

可以用异或运算写成线性规模的表达式,但表示它的任何析取范式都需要 2n−12^{n-1} 项。这是因为,只要某一项省略了哪怕一个变量,它就会覆盖两个相邻输入,而奇偶函数在这两个输入上的取值不同。因此,每个有效的项都必须指定唯一一个满足赋值。其合取范式也有类似的指数下界。

逻辑范式还将函数与布尔可满足性问题联系起来。如果一个公式所表示的函数不恒为 0,就称该公式可满足;如果其函数恒为 1,则称该公式为重言式。可以通过判断两个公式的异或是否可满足,来检验它们是否等价。一个关键区别在于,真值表显式列出了指数多个值,而一个简短的公式可能隐式编码了同一张真值表。因此,相对于真值表长度而言高效的算法,其运行时间相对于变量个数而言仍可能是指数级的。

结构类别与函数完备性

布尔函数可按对称性、序性质或代数约束划分为相互重叠的类别。若只要每个坐标都满足 xi≤yix_i\leq y_i,就有 f(x)≤f(y)f(x)\leq f(y),则称其为单调布尔函数。合取和析取是单调的;否定和非常值的奇偶函数则不是。如果一个函数的值仅取决于输入中 1 的个数,就称它为对称函数。奇偶函数、判定 1 的个数是否恰为指定值的谓词,以及多数函数,都是对称函数。nn 个变量上的对称函数共有 2n+12^{n+1} 个,因为对于从 0 到 nn 的每一种可能的输入重量,都可以独立选择一个输出值。

阈值函数检验加权和是否达到某个阈值:

f(x)=1 ⁣[∑i=1nwixi≥θ].f(x)=\mathbf 1\!\left[\sum_{i=1}^{n}w_i x_i\geq\theta\right].

实数权重可以为正,也可以为负。非负权重产生单调函数,合取、析取和多数函数都属于此类。一般的阈值函数描述了用超平面对立方体顶点进行线性分离的方式。并非所有布尔函数都是阈值函数:二元异或就是最简单的反例。这一局限性在对简单人工神经元的数学研究中具有重要意义。

在函数复合的研究中,还有几个重要类别。如果 f(0,…,0)=0f(0,\ldots,0)=0,就称函数为保 0 函数;如果 f(1,…,1)=1f(1,\ldots,1)=1,就称其为保 1 函数。如果满足

f(¬x1,…,¬xn)=¬f(x1,…,xn).f(\neg x_1,\ldots,\neg x_n)=\neg f(x_1,\ldots,x_n).

则称其为自对偶函数。仿射布尔函数具有如下形式:

a0⊕a1x1⊕⋯⊕anxn,ai∈{0,1}.a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n, \qquad a_i\in\{0,1\}.

仿射函数包括常值函数、投影函数、否定函数和奇偶函数。这里的“仿射”指的是二元域上的代数结构,而不是实值线性阈值。

如果每个布尔函数都能通过一组运算的复合并使用变量来表示,就称这组运算具有函数完备性。范式的构造表明,集合 {∧,∨,¬}\{\land,\lor,\neg\} 是完备的。{∧,¬}\{\land,\neg\} 和 {∨,¬}\{\lor,\neg\} 也都完备,因为利用德摩根定律可以构造出缺少的运算。更引人注目的是,仅用与非运算或仅用或非运算,也都能实现完备性。对于与非运算,将同一个输入送入两个输入端即可得到否定;随后再通过更多次与非运算,就能构造出合取和析取。

埃米尔·波斯特于 1941 年发表的分类给出了精确的完备性判据。在不默认提供常量的标准约定下,一组布尔运算具有函数完备性,当且仅当它不完全包含于以下五个类别中的任何一个:保 0 函数、保 1 函数、单调函数、仿射函数或自对偶函数。每一类对复合运算都是封闭的,因此都会阻碍任意函数的表达。对复合封闭函数族的更广泛分类构成了波斯特格,表明逻辑运算的表达能力具有细致的代数结构,而不仅仅是一份完备逻辑门集合的清单。

有限域和实数上的多项式表示

布尔输入有两种特别有用的多项式描述方式。第一种将 {0,1}\{0,1\} 视为有限域 F2\mathbb F_2,其中加法对应异或,乘法对应合取。每个布尔函数都有唯一的多重线性代数范式(ANF):

f(x)=⨁S⊆[n]aS∏i∈Sxi,aS∈F2.f(x)=\bigoplus_{S\subseteq[n]}a_S\prod_{i\in S}x_i, \qquad a_S\in\mathbb F_2.

这里,[n]={1,…,n}[n]=\{1,\ldots,n\},空乘积为 1。多重线性是指每个变量的指数都不超过一。对于二进制输入,恒有 xi2=xix_i^2=x_i,因此无需使用更高次幂。

这些系数可以直接由真值表求出。若 1T1_T 表示取值为 1 的坐标所组成的集合为 TT 的输入,则

aS=⨁T⊆Sf(1T).a_S=\bigoplus_{T\subseteq S}f(1_T).

这是 F2\mathbb F_2 上的子集莫比乌斯变换。其快速算法只需 O(n2n)O(n2^n) 次域运算即可算出全部系数。对于非零函数,使 aS=1a_S=1 成立的最大 ∣S∣|S| 就是该函数的代数次数。例如,

x∨y=x⊕y⊕xyx\lor y=x\oplus y\oplus xy

的代数次数为 2,而奇偶函数无论涉及多少个变量,代数次数都为 1。

这一代数框架可以表述为商环

F2[x1,…,xn]/(x12−x1,…,xn2−xn).\mathbb F_2[x_1,\ldots,x_n]\big/ (x_1^2-x_1,\ldots,x_n^2-x_n).

其中的元素与布尔函数一一对应,环中的加法和乘法分别对应函数的逐点加法和逐点乘法。这就建立了与环(数学)及多项式方程求解之间的联系。一组布尔约束可以转化为 F2\mathbb F_2 上的方程组;例如,方程 f(x)=1f(x)=1 可表示为 f(x)+1=0f(x)+1=0。较低的代数次数往往能使单个约束的表示更紧凑,但这本身并不意味着整个方程组容易求解。

第二种表示使用通常的实数算术。定义在 {0,1}n\{0,1\}^n 上的每个函数,包括布尔值函数,都有唯一的实系数多重线性多项式表示。例如,

x∨y=x+y−xy,x⊕y=x+y−2xy.x\lor y=x+y-xy,\qquad x\oplus y=x+y-2xy.

其中 ∏i∈Sxi\prod_{i\in S}x_i 的系数为

cS=∑T⊆S(−1)∣S∣−∣T∣f(1T).c_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(1_T).

所选的域至关重要:nn 个变量的奇偶函数在 F2\mathbb F_2 上的次数为 1,但其精确的实系数多重线性表示的次数为 nn。因此,谈论“布尔函数的次数”时,必须明确采用哪一种约定。

精确表示与近似表示也有所不同。实数域上的 ε\varepsilon-近似次数,是在每个二进制输入上都满足 ∣p(x)−f(x)∣≤ε|p(x)-f(x)|\leq\varepsilon 的实系数多项式 pp 所能达到的最低次数。近似次数可能远低于精确次数,并且与查询复杂度密切相关。阈值表示的要求又不一样:它只要求由多项式的符号或经阈值判定后的值来确定答案。精确次数、近似次数和多项式阈值次数,衡量的是同一张真值表的不同方面。

离散立方体上的傅里叶分析

为便于分析,布尔输入常被编码为符号值 zi∈{−1,1}z_i\in\{-1,1\}。布尔输出也可以表示为 g(z)∈{−1,1}g(z)\in\{-1,1\},例如采用 zi=(−1)xiz_i=(-1)^{x_i} 和 g(z)=(−1)f(x)g(z)=(-1)^{f(x)}。在立方体上的均匀分布下,坐标乘积

χS(z)=∏i∈Szi\chi_S(z)=\prod_{i\in S}z_i

构成立方体上实值函数空间的一组标准正交基,其内积为 ⟨g,h⟩=E[g(z)h(z)]\langle g,h\rangle=\mathbb E[g(z)h(z)]。这些乘积称为特征标或奇偶函数。

立方体上的每个实值函数都有傅里叶展开

g(z)=∑S⊆[n]g^(S)χS(z),g^(S)=E[g(z)χS(z)].g(z)=\sum_{S\subseteq[n]}\widehat g(S)\chi_S(z), \qquad \widehat g(S)=\mathbb E[g(z)\chi_S(z)].

因此,这些系数衡量了函数与各个奇偶函数的相关性。常数项系数就是均值,即 g^(∅)=E[g]\widehat g(\varnothing)=\mathbb E[g],而单元素集合对应的系数则衡量函数与各个坐标的相关性。这一展开是傅里叶变换在有限群上的形式,具体而言,是归一化的沃尔什–哈达玛变换。由完整的真值表出发,经过 O(n2n)O(n2^n) 次算术运算即可计算出全部系数。

由正交性可得帕塞瓦尔恒等式:

∑S⊆[n]g^(S)2=E[g2].\sum_{S\subseteq[n]}\widehat g(S)^2=\mathbb E[g^2].

对于取符号值的布尔函数,右端为 1。其非常数项的傅里叶质量等于它的方差:

∑S≠∅g^(S)2=1−E[g]2.\sum_{S\ne\varnothing}\widehat g(S)^2 =1-\mathbb E[g]^2.

常数函数的全部傅里叶质量都集中在空集上。奇偶函数 χT\chi_T 只有一个非零系数,对应的集合为 TT。大多数函数的傅里叶质量分布在许多子集上,而这些质量的分布位置蕴含了从逻辑公式中无法直接看出的结构信息。

傅里叶分析在研究随机扰动时尤其有效。对 zz 的每个坐标,以概率 (1−ρ)/2(1-\rho)/2 独立翻转,得到 z′z',其中 0≤ρ≤10\leq\rho\leq1。噪声算子

Tρg(z)=E[g(z′)∣z]T_\rho g(z)=\mathbb E[g(z')\mid z]

在傅里叶基下具有对角形式:

Tρg=∑Sρ∣S∣g^(S)χS.T_\rho g=\sum_S\rho^{|S|}\widehat g(S)\chi_S.

高次项比低次项受到更强的衰减。由此得到的噪声稳定性为

E[g(z)g(z′)]=∑Sρ∣S∣g^(S)2.\mathbb E[g(z)g(z')] =\sum_S\rho^{|S|}\widehat g(S)^2.

因此,频谱信息可以直接转化为对函数抵抗随机比特翻转能力的定量描述。

这些公式为学习理论、社会选择理论和复杂性理论中的相关结果提供了支撑。若傅里叶质量集中在较小的子集上,函数就可能适合用低次多项式逼近。若傅里叶质量集中在某个较小坐标集合的各个子集上,则表明函数近似地只依赖于较少的输入。对于非均匀乘积分布,可以利用经过中心化和归一化的坐标变量构造类似的标准正交基,但系数和影响度公式都必须根据该分布作相应调整。因此,底层测度是分析设定的一部分,而非无关紧要的约定。

影响度、敏感度与随机扰动

在均匀分布下,坐标 ii 的影响度是指翻转该位后输出发生变化的概率:

Inf⁡i(f)=Pr⁡[f(x)≠f(x⊕i)],\operatorname{Inf}_i(f) =\Pr[f(x)\ne f(x^{\oplus i})],

其中,x⊕ix^{\oplus i} 由翻转 xx 的第 ii 位得到。总影响度是所有坐标影响度之和。从几何角度看,它衡量了函数的取值为 0 的集合与取值为 1 的集合之间的边边界。如果立方体中有 BB 条边的两个端点对应不同的输出,那么

∑iInf⁡i(f)=B2n−1.\sum_i\operatorname{Inf}_i(f)=\frac{B}{2^{n-1}}.

它也等于对所有输入取平均后,能够改变输出的单比特翻转的数量。

以下例子展示了不同的依赖形式。对于奇偶函数,翻转任意一个坐标都会改变输出,因此每个坐标的影响度都是 1,总影响度为 nn。对于 nn 个变量的合取函数,只有当其余 n−1n-1 个坐标全为 1 时,某个坐标的翻转才会改变输出,因此每个坐标的影响度为 2−(n−1)2^{-(n-1)},总影响度为 n2−(n−1)n2^{-(n-1)}。输入个数为奇数的多数函数介于这两个极端之间:每个坐标的影响度为 n−1/2n^{-1/2} 量级,总影响度为 n\sqrt n 量级。这些数值体现了均衡的集体决策与稀有事件判定条件之间的差别。

采用符号编码时,影响度具有如下谱表示:

Inf⁡i(g)=∑S∋ig^(S)2,I(g)=∑S∣S∣g^(S)2.\operatorname{Inf}_i(g)=\sum_{S\ni i}\widehat g(S)^2, \qquad I(g)=\sum_S |S|\widehat g(S)^2.

对每个输入,统计翻转后能改变输出的坐标数量,再对所有输入取最大值,便得到敏感度 s(f)s(f)。块敏感度则允许考虑一组两两不相交的坐标块,要求翻转任一块中的所有比特都能改变输出。某个输入的证书是一组固定的坐标取值;无论其余坐标如何取值,这组取值都足以确定输出。这些概念分别衡量局部脆弱性、协同变化下的脆弱性,以及足以确定答案的证据量。

1988 年证明的卡恩–卡莱–利尼尔定理指出,如果一个布尔函数的方差足够大,那么它必定至少有一个坐标,其影响度不小于 (log⁡n)/n(\log n)/n 的某个常数倍。更一般地,这一下界还包含方差因子。与简单的平均法下界相比,这一对数因子的改进十分重要:均衡函数不可能以任意均匀且微弱的方式将其依赖性分散到所有坐标上。部落构造由若干互不相交的变量块上的合取再取析取组成,通过适当选择块的大小,可以说明该下界在量级上是紧的。

噪声敏感度衡量的是 Pr⁡[f(x)≠f(y)]\Pr[f(x)\ne f(y)],其中 yy 由以指定概率独立翻转输入的各个比特得到。它与单比特影响度有关,但并不相同。2019 年,黄皓证明了敏感度猜想,补上了局部度量与全局度量之间的一项重要联系。特别地,对于全布尔函数,其精确实多项式表示的次数满足 deg⁡R(f)≤s(f)2\deg_{\mathbb R}(f)\leq s(f)^2。结合此前已经确立的不等式,这一结果表明,敏感度与块敏感度以及确定性查询复杂度之间均存在多项式关系。在许多此类关系中,将讨论范围限定为全函数是必不可少的。

紧凑表示与逻辑最小化

真值表是一种规范表示,但需要 2n2^n 个输出位。公式可以更小,但其树状结构会重复表示任何被多次使用的子表达式。布尔电路允许共享:它是一个有向无环图,包含输入节点、逻辑门节点以及指定的输出。例如,一个公共的中间条件可以馈送到后续的多个逻辑门,而无须重新计算。电路规模按约定通过逻辑门数或连线数来衡量,深度则衡量相互依赖的逻辑门所构成的最长序列。因此,电路最小化不同于单纯缩短书面公式。

香农展开是许多表示方法所依据的一种基本分解:

f(x)=(¬xi∧f∣xi=0)∨(xi∧f∣xi=1).f(x)= (\neg x_i\land f|_{x_i=0}) \lor (x_i\land f|_{x_i=1}).

这两个受限函数称为余因子。从运算角度看,该公式根据 xix_i 的值选择一个余因子,其作用与多路选择器完全相同。反复展开便会得到一棵决策树。共享相同的子问题可得到二叉决策图(BDD),它可能比完整的树紧凑得多。

在有序 BDD 中,每条路径都按同一个固定顺序测试变量。删除两个分支均指向同一子节点的节点,再合并测试变量和子节点均相同的节点,就得到简约有序 BDD。对于固定的变量顺序,这种表示是规范的。兰德尔·布赖恩特于 1986 年发表的研究确立了它在符号操作中的实用价值。不过,变量顺序仍可能使表示规模产生指数级差异。对于比较两个 mm 位二进制串是否相等的谓词,交错测试两个串的对应位,可以得到线性规模的图;而先测试一个串的所有位,再测试另一个串的所有位,则需要指数多个不同状态来记住第一个串。

两级逻辑最小化旨在得到较小的积之和或和之积。卡诺图对真值表中的条目进行排列,使相邻单元格仅有一位不同,从而可以将相邻的值为 1 的区域分组,化为简化的项。奎因–麦克拉斯基算法系统地合并可合并的最小项,以找出质蕴涵项,再从中选出一个覆盖。蕴涵项是指不会覆盖任何函数值为 0 的输入的项;质蕴涵项则是无法在保持这一性质的前提下删去任何文字的蕴涵项。寻找最优覆盖的计算开销可能很高,因此大规模综合通常依赖启发式方法,而非穷尽搜索式的最小化。

最佳表示取决于预期进行的操作。BDD 一旦构建完成,就可以支持高效的等价性检验,但在构建过程中规模可能呈指数增长。合取范式(CNF)很适合用于可满足性求解,而与非反相图则支持电路重写和工艺映射。文字数较少的设计,并不一定具有最低的延迟、布线成本或功耗。不可达的输入模式会引入“无关项”,从而允许进一步优化,但前提是外围系统能够保证这些模式不会出现。表示规模、操作成本和实现成本是彼此不同的目标。

计算复杂性与下界

布尔函数是一个有限对象,但计算复杂性理论通常研究函数族 (fn)(f_n),其中每种输入长度对应一个函数。所关心的问题是,计算 fnf_n 所需的资源如何随 nn 增长。决策树以自适应的方式查询输入位,根据已经得到的答案选择下一次查询。确定性查询复杂度 D(f)D(f) 是精确计算 ff 所需的最坏情况查询次数的最小值。每个 nn 元函数都满足 D(f)≤nD(f)\leq n,但有些函数可以用小得多的树来计算,因为并非对每个输入都需要检查所有变量。

合取运算体现了平均情况与最坏情况之间的区别。只要找到一个 0,就能确定与运算的结果为 0;但对于全为 1 的输入,必须检查每个坐标,因此 D(ANDn)=nD(\mathrm{AND}_n)=n。允许有界错误的随机化经典算法在最坏情况下仍需 nn 量级的查询,而量子算法只需 n\sqrt n 量级的查询。多项式表示有助于在这些模型中建立下界。深度为 dd 的确定性决策树给出一个次数不超过 dd 的精确实系数多重线性表示;进行 TT 次查询的量子算法,其接受概率可由次数不超过 2T2T 的多项式表示。

电路复杂度研究由指定门基构成的电路的规模与深度。扇入、允许使用的门以及一致性条件都很重要。香农的计数论证表明,在标准的有限、完备且扇入有界的门基上,几乎所有 nn 元布尔函数都需要规模为 2n/n2^n/n 量级的电路。原因在于,小规模电路的描述数量远少于真值表的数量 22n2^{2^n}。这证明了难计算函数的大量存在,却没有指出某个能够高效描述的具体难函数。

为显式函数证明下界要困难得多。由扇入无界的与门、或门以及输入端的取反构成的常数深度、多项式规模电路,形成了通常称为 AC0\mathrm{AC}^0 的类。奇偶函数无法由这样的电路族计算;这一具有里程碑意义的分离结果,是通过始于 20 世纪 80 年代的一系列研究确立的。加入奇偶门会改变模型,加入阈值门又会带来不同的模型。因此,同一个函数在某种电路模型中可能容易计算,在另一种模型中却可能很难;解释下界时,不能脱离模型所允许的基本运算。

对于不受限制的一般电路,为主要的一致复杂性类中的显式函数证明超多项式规模下界,仍是一个核心开放问题。函数的表示方式也决定了有关函数的一些基本问题的复杂度。判断两个显式真值表是否相等,相对于其长度而言很容易;但判断任意两个电路描述是否等价,则是 coNP 完全问题。同样,扫描真值表即可直接判定可满足性,但对于一般的合取范式(CNF)描述,可满足性却是 NP 完全问题。一旦明确输入长度,这种表面上的反差就消失了:真值表已经为列出每一种赋值付出了指数级的代价。

密码学准则与纠错码

在密码学中,布尔函数用于组合比特、过滤内部状态,以及定义代换盒各坐标的输出。所需的性质取决于具体的构造。平衡性是指函数输出 0 和 1 的次数相同。代数次数衡量其代数正规形的复杂程度,而非线性度衡量它与所有仿射布尔函数之间的距离。这些准则针对不同的数学弱点;任何一项都不足以单独确立密码算法或生成器的安全性。

以真值表之间的汉明距离为度量,非线性度为

NL⁡(f)=min⁡a∈F2n, b∈F2dH(f,a⋅x⊕b).\operatorname{NL}(f) =\min_{a\in\mathbb F_2^n,\ b\in\mathbb F_2} d_H(f,a\cdot x\oplus b).

定义未归一化的沃尔什变换为

Wf(a)=∑x∈F2n(−1)f(x)⊕a⋅x.W_f(a)=\sum_{x\in\mathbb F_2^n}(-1)^{f(x)\oplus a\cdot x}.

则有

NL⁡(f)=2n−1−12max⁡a∣Wf(a)∣.\operatorname{NL}(f) =2^{n-1}-\frac12\max_a|W_f(a)|.

较大的沃尔什系数表明函数与某个仿射函数具有较强的相关性。这一公式将对仿射逼近的搜索转化为谱计算,也解释了为什么傅里叶方法在密码函数设计中具有核心地位。

当 nn 为偶数时,Bent 函数对每个 aa 都满足 ∣Wf(a)∣=2n/2|W_f(a)|=2^{n/2}。Bent 函数达到了非线性度的最大可能值,

2n−1−2n/2−1.2^{n-1}-2^{n/2-1}.

这一术语由奥斯卡·罗特豪斯在 1976 年发表的研究中引入。Bent 函数并不平衡,因为其在零处的沃尔什系数不为零。这体现了设计中切实存在的权衡:优化一项准则可能导致另一项准则无法满足。相关免疫性则是另一种性质,它要求在输入均匀且相互独立的条件下,输出与任何不超过指定数量的输入坐标集合都在统计上独立。具有平衡性的相关免疫函数称为弹性函数。

向量布尔函数用于描述代换盒 F:F2n→F2mF:\mathbb F_2^n\to\mathbb F_2^m。仅单独考察各个坐标函数,并不能完整刻画其行为:对于线性逼近,输出坐标的每个非零线性组合都很重要。其差分行为由下式描述:

DaF(x)=F(x⊕a)⊕F(x),D_aF(x)=F(x\oplus a)\oplus F(x),

而差分均匀度是指遍历所有非零 aa 和所有 bb 时,方程 DaF(x)=bD_aF(x)=b 的解的个数的最大值。这类量衡量的是具有特定结构的统计模式,而不只是实现代换盒所需的逻辑门数量。

布尔函数也可用于生成纠错码。里德–穆勒码 RM(r,n)\mathrm{RM}(r,n) 由所有代数次数不超过 rr 的 nn 元函数的真值表组成。当 0≤r≤n0\leq r\leq n 时,其码长为 2n2^n,维数为

∑j=0r(nj),\sum_{j=0}^{r}\binom nj,

最小距离为 2n−r2^{n-r}。一阶里德–穆勒码恰好包含所有仿射函数,因此,函数在密码学意义上的非线性度就是它到该码的距离。这在抵抗仿射逼近的能力与一类经典码的几何结构之间建立了精确的数学联系。

学习、集体决策与系统可靠性

在机器学习中,布尔函数可以用作二分类规则:输入编码各项属性,输出则指定两个类别中的一个。学习通常并不意味着重建任意真值表,因为在不加限制的情况下,所需的观测次数可能呈指数增长。相反,算法会利用某个假设类,例如合取式、小型决策树、稀疏多项式表示或阈值函数。在概率近似正确学习中,成功是指以关于训练数据抽样的高概率,得到一个在相关输入分布下误差较小的假设。

学习的难度既取决于表示方式,也取决于获取信息的方式。样例预言机提供带标签的输入,而成员查询预言机允许学习器查询自行选定的输入所对应的函数值。傅里叶系数能够揭示相关性,为均匀分布下的学习提供指引;仅依赖少数相关坐标的函数则为降维提供了机会。这类函数通常称为 junta 函数。不过,一个函数类具有简洁的表示,并不自动意味着存在高效的学习算法:仅仅是从观测中识别出这种表示,本身就可能在计算上十分困难。

投票提供了另一种解释。布尔聚合规则将个体的二元投票映射为一个集体结果。多数决、全体一致决和独裁规则都是基本例子。单调性表示,将某个个体的投票改为支持某一结果,不会使该结果落败;对称性则表示对所有投票者一视同仁。影响力是在给定投票模型下,某位投票者起决定性作用的概率。在各票相互独立且均匀随机的情况下,这就是未经归一化的概率班扎夫度量;采用其他分布和归一化方式,则会得到不同的投票权力指数。

在可靠性理论中,输入位可以表示某个部件是否正常工作,输出则表示整个系统是否正常工作。单调结构函数描述的是这样一种系统:修复一个部件不会导致系统失效。串联系统用合取表示,并联系统用析取表示。如果各部件以概率 p1,…,pnp_1,\ldots,p_n 相互独立地正常工作,则系统可靠性为

R(p1,…,pn)=∑x∈{0,1}nf(x)∏i=1npixi(1−pi)1−xi.R(p_1,\ldots,p_n) =\sum_{x\in\{0,1\}^n} f(x)\prod_{i=1}^{n}p_i^{x_i}(1-p_i)^{1-x_i}.

该表达式关于各部件的可靠性是多重线性的。对于串联系统,它化简为 ∏ipi\prod_i p_i;对于并联系统,则化简为 1−∏i(1−pi)1-\prod_i(1-p_i)。如果部件失效之间存在依赖关系,就需要用适当的联合分布替代乘积模型。

对于输入相互独立且成功概率均为 pp 的单调函数,马尔古利斯–鲁索公式将可靠性的变化与起决定性作用的事件联系起来:

ddpEp[f]=∑i=1nPr⁡p ⁣[f(x−i,1)≠f(x−i,0)].\frac{d}{dp}\mathbb E_p[f] =\sum_{i=1}^{n} \Pr_p\!\left[ f(x_{-i},1)\ne f(x_{-i},0) \right].

这里,右侧的概率是针对其余 n−1n-1 个坐标而言的。该公式解释了布尔系统如何随部件可靠性或事件密度的变化而发生急剧转变。同样的机制也出现在随机图性质和渗流中:当许多局部坐标起决定性作用的概率加总后达到相当大的程度时,一个全局的是非事件就会迅速转变。