布尔函数

形式陈述 ​

对象与记号 ​

一个 $n$ 元布尔函数是函数理路函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。

输入 $x=(x_1,\dots ,x_n)$ 是 $n$ 个 bit 组成的向量，输出是一个 bit。由于定义域是有限集理路有限集Finite set与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。，函数可以由包含 $2^n$ 行的真值表完全指定；公式、程序、多项式和电路则是同一个输入—输出对象的不同表示。

也常把真假编码为 $\{-1,+1\}$，特别是在 Fourier 分析和多项式逼近中。两个编码之间可由 $b\mapsto (-1{)}^b$ 或 $b\mapsto 2b-1$ 转换，但 AND、XOR 与乘法的对应会随约定改变。推导开始前必须声明编码，不能在公式中途把 $0/1$ 与 $\pm 1$ 记法混用。

复杂度通常研究函数族 $\{f_n{\}}_{n\ge 1}$，其中每个 $f_n$ 只处理固定长度输入。单个 $f_n$ 是有限对象；“随 $n$ 增长需要多少资源”属于整个函数族。把一个固定 $n$ 的巨大真值表硬编码为常数，不会推翻关于函数族的渐近下界。

偏函数与关系 ​

偏布尔函数只在 promise 集合 $S\subseteq \{0,1{\}}^n$ 上定义：

算法只需在 $S$ 中的合法输入上满足正确性保证；对 promise 外是否仍须终止、是否仍受资源上限约束，则由具体计算模型规定。例如有限深度决策树在整个立方体上都会停机，只是不要求 promise 外的输出正确。promise 往往让查询或通信问题显著容易；因此 total function 的定理不能仅凭符号相同就套到 partial function，反方向也不能把 promise 外行为私自补全后仍声称复杂度不变。

关系问题 $R\subseteq S\times Z$ 又是不同对象。它允许同一输入对应多个合法输出，算法只需选择其中一个；这不是“输出不确定的布尔函数”。若输出集合仍是 $\{0,1\}$ 且两个值都可接受，关系在该输入上没有区分要求，而普通函数必须唯一指定一个值。

在两方通信中，还会研究 $f:X\times Y\to \{0,1\}$；那是输入按两位参与者分割的布尔值函数。它与本页的 Boolean cube 函数可以互相编码，却不共享相同的访问模型。通信模型理路两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。按交换消息计费，查询模型理路查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。按读取输入坐标计费，函数本身不替模型决定成本。

支持变量与限制操作 ​

坐标 $i$ 属于 $f$ 的支持，当且仅当存在两个只在第 $i$ 位不同的输入 $x,x^{\oplus i}$，使

对全函数，不在支持中的变量可以删除：沿着该坐标的每条边，函数值都不变。函数真正依赖多少坐标是语义性质，不能通过数公式里出现了多少变量名来判断。

对偏函数，若仍用相邻输入定义敏感性，必须同时要求 $x,x^{\oplus i}\in S$；但不能据此把“没有敏感边”解释为“不需要任何输入信息”。promise 可能切断立方体上的路径。更稳妥的依赖表述是：坐标集合 $J$ 足以决定输出，当且仅当任意 $x,y\in S$ 满足 $x_J=y_J$ 时都有 $f(x)=f(y)$。偏函数可能存在多个互不包含的最小决定集合，而全函数有唯一的支持。

把部分坐标固定为常量会得到限制。若 $I\subseteq [n]$，赋值 $\rho \in \{0,1{\}}^I$，则 $f{\upharpoonright }_{\rho }$ 是在其余坐标上代入 $x_i={\rho }_i$ 后得到的函数。限制可逐步暴露局部结构，也是决策树沿一条查询路径后所剩子问题的精确表达。

限制不同于删除一个输入样本。它固定若干坐标并保留与赋值一致的整个子立方体；偏函数的 promise 则可以是任意子集，不必具有子立方体形状。混淆两者会让关于递归和维数的论证失去适用条件。