企业官网建设流程全解析

布尔函数求值 - 短路求值与决策树的计算艺术

📰 5W1H 发明者故事

Who（何人）- 发明者是谁？

奠基者：Claude Shannon（香农，布尔电路理论）；George Boole（布尔代数）；高德纳（TAOCP 卷4A §7.1.1 系统整理）
背景：

• 香农（1916-2001）：1938 年硕士论文将布尔代数与继电器电路对应，为布尔函数求值奠定基础
• Knuth 在卷4A §7.1.1 中全面分析了布尔函数的表示与高效求值，包括决策树、OBDD 等多种方法
• 现代编译器（GCC、Clang）的短路求值（short-circuit evaluation）直接源自此理论

当时的处境：1930-40 年代，逻辑电路设计完全依赖工程师的直觉。复杂布尔表达式的化简极为繁琐，需要更系统的计算方法。

When（何时）- 什么时候发明的？

时间：布尔代数 1854 年（Boole）→ 电路对应 1938 年（Shannon）→ 算法系统化 1960-2000 年代
里程碑：

• 1938：Shannon 证明布尔代数等价于两端开关电路
• 1956：Quine-McCluskey 算法（最小化布尔函数）
• 1986：Bryant 提出 OBDD（有序二元决策图），布尔函数紧凑表示的突破
• 2006+：Knuth 在 TAOCP 7.1 中整理了求值的完整算法体系

Where（何地）- 在哪里发明的？

地点：MIT（Shannon）、加州大学伯克利（Bryant 的 BDD）、Stanford（Knuth 整理）
环境：集成电路设计自动化（EDA）的工程需求，驱动了布尔函数求值算法的快速发展

What（何事）- 发明了什么？

算法体系：布尔函数的高效求值（Boolean Function Evaluation）
核心方法：

1. 真值表求值：穷举所有 2^n 个输入组合，直接存储结果 —— 简单但指数级空间
2. 递归化简（Shannon 展开）：f(x₁,…,xₙ) = (¬x₁ ∧ f|{x₁=0}) ∨ (x₁ ∧ f|{x₁=1})
3. 短路求值（Short-circuit）：AND: 若左边为 FALSE 直接返回 FALSE，不求右边；OR: 若左边为 TRUE 直接返回 TRUE
4. 决策树求值：将布尔函数表示为二叉决策树，按变量顺序从根到叶求值，最多 n 次变量测试
5. OBDD 求值（参见 taocp4_bdd_story.md）：共享子树的有向无环图表示

TAOCP 核心算法（§7.1.1）：

• 算法 E（Evaluation via truth table）：直接查表
• 算法 S（Shannon expansion evaluation）：分治递归
• 位并行求值（Bit-parallel）：用机器字的每一位同时存储一个输入组合的结果，一次运算处理 64 个求值

Why（何因）- 为什么发明？

要解决的问题：

1. 电路验证：两个电路是否计算同一个布尔函数？等价性检查
2. 最小化：能否用更少的门（AND/OR/NOT）实现同一函数？降低硬件成本
3. 可满足性（SAT）：是否存在一组输入使函数值为 TRUE？（参见 taocp4_dpll_sat_story.md）
4. 编译器优化：条件表达式if (A && B)的短路求值减少不必要的运算

核心洞察：

• n 个变量的布尔函数共有 2⁽²n) 个，真值表需要 2^n 位存储
• 大多数实际函数有结构，可以用远小于 2^n 的资源表示和求值
• 变量顺序对决策树/BDD 大小有决定性影响（同一函数换变量顺序，BDD 可从线性变为指数级）

How（何果）- 如何实现？有什么影响？

bit-parallel 求值示意：

设有 4 个变量 x1,x2,x3,x4，用 4 位掩码表示 16 种输入组合： x1 的真值向量：0000 1111 (低8个组合 x1=0，高8个 x1=1) x2 的真值向量：0011 0011 x3 的真值向量：0101 0101 x4 的真值向量：... 求 f = (x1 AND x2) OR (NOT x3)： tmp = x1 & x2 → 与运算 result = tmp | (~x3) → 或运算 result 的每一位就是对应输入组合的函数值！ 64 位机器一次处理 64 种输入组合。

历史影响：

• 硬件综合工具（Synopsys Design Compiler）的核心是布尔函数求值与最小化
• 形式验证（Model Checking）用 BDD 表示布尔函数，验证电路等价性
• 现代 SAT 求解器（MiniSat、Glucose）在 DPLL 算法中大量做布尔求值
• C/C++/Java 的&&和||运算符的短路求值语义正是此理论的直接应用

📝 自然语言需求定义

需求名称：实现布尔函数求值器，支持真值表法、递归 Shannon 展开和位并行求值三种方式

功能需求（用精确的中文描述）

1. 解析布尔表达式（parse_expr）：将字符串表达式解析为抽象语法树（AST）

   • 支持运算符：&（AND）、|（OR）、!（NOT）、^（XOR）及括号
   • 支持变量：单字母 a-z
   • 输入：表达式字符串，如"(a & b) | !c"
   • 输出：AST 根节点指针

2. 真值表求值（eval_truthtable）：对 n 个变量的函数生成完整真值表

   • 输入：AST 根节点，变量列表，变量个数 n（n ≤ 20）
   • 操作：枚举所有 2^n 种赋值，对每种调用递归求值
   • 输出：打印格式化真值表

3. 单次求值（eval_once）：给定变量赋值，对 AST 求值一次

   • 输入：AST 根节点，变量名到布尔值的映射
   • 操作：递归计算，遇到变量节点查表，遇到运算符节点递归子树
   • 输出：0 或 1

4. 短路求值（eval_short_circuit）：与 eval_once 相同语义但利用短路优化

   • AND 节点：若左子树为 0 则立即返回 0，不求右子树
   • OR 节点：若左子树为 1 则立即返回 1，不求右子树
   • 输出：0 或 1，同时统计实际访问的节点数

5. 位并行求值（eval_bitparallel）：对最多 6 个变量的函数，用 64 位整数一次求全部 64 种（或 2^n 种）输入组合的值

   • 输入：AST，变量列表，变量数 n（n ≤ 6）
   • 操作：为每个变量 xᵢ 构造真值向量（第 k 位 = 输入组合 k 中 xᵢ 的值），然后用位运算模拟逻辑运算符
   • 输出：64 位结果向量

6. 可满足性检查（is_satisfiable）：判断函数是否存在使其为真的输入

   • 输入：AST，变量数 n
   • 操作：利用位并行结果，若结果向量非零则可满足
   • 输出：YES（及第一个满足的赋值）或 NO（重言式/矛盾式报告）

约束条件

• 解析器：递归下降，支持正确的运算符优先级（! > & > ^ > |）
• AST 节点：{ int type; char var; Node *left, *right; }
• 变量数限制：真值表模式 n ≤ 20，位并行模式 n ≤ 6
• 不使用第三方库，纯 C99 标准

验收标准（必须可验证）

AI 生成提示

基于以上需求，用标准C99实现布尔函数求值器。 要求： 1. 递归下降解析器，支持 !、&、|、^、括号，正确优先级 2. AST 节点：NodeType { VAR, NOT, AND, OR, XOR } 3. 实现四个求值器：eval_once、eval_short_circuit、eval_truthtable、eval_bitparallel 4. 短路求值记录访问节点数，与完整求值对比 5. 位并行：xᵢ 的真值向量 = 64 位整数，第 k 位 = ((k >> (n-1-i)) & 1) 6. main() 实现全部 8 个验收测试 7. 测试通过输出 "✓ 测试X通过"，失败输出 "✗ 测试X失败" 核心函数： - parse_expr(str) → Node* - eval_once(node, vars[]) → int - eval_short_circuit(node, vars[], *count) → int - eval_truthtable(node, var_names, n) → void（打印） - eval_bitparallel(node, var_names, n) → uint64_t - is_satisfiable(node, n) → int（打印第一个满足赋值）

💻 C语言实现文件

对应文件:taocp4_boolean_evaluation.c

编译运行:

gcc-Wall-std=c99-obool_eval taocp4_boolean_evaluation.c ./bool_eval# 详细输出模式gcc-Wall-std=c99-DVERBOSE-obool_eval_v taocp4_boolean_evaluation.c ./bool_eval_v

核心函数:

• parse_expr(str)- 递归下降解析布尔表达式为 AST
• eval_once(node, vars)- 给定赋值，递归计算函数值
• eval_short_circuit(node, vars, count)- 短路优化求值，统计节点访问数
• eval_truthtable(node, names, n)- 打印完整真值表
• eval_bitparallel(node, names, n)- 64 位并行求全部组合
• is_satisfiable(node, n)- 可满足性检查