布尔代数化简器

变量用 A、B、C...。运算符:& (AND),| (OR),! (NOT),^ (XOR),( )

给定一个布尔表达式 — A·B + A·¬B + ¬A·B,或带最小项的真值表 — 这个化简器会使用 Quine-McCluskey 算法返回最小的与或式(sum-of-products),并为最多六个变量提供 Karnaugh 图可视化。它会展示每一步(主蕴含项、必要主蕴含项、覆盖表),因此不仅适合作业,也适合审查综合工具内部的 minimiser 做出了什么选择。

布尔化简如何运行

  1. 1

    输入表达式或最小项

    使用运算符 ·(AND)、+(OR)、' 或 ¬(NOT)、⊕(XOR)。也可以粘贴类似 m(0,1,3,7) 的最小项索引。

  2. 2

    生成真值表

    计算每一种变量赋值,并把函数输出制成表格。

  3. 3

    Quine-McCluskey 查找主蕴含项

    最小项会被分组并迭代合并。相邻组(只相差一个变量)会继续合并,直到无法进一步约简。

  4. 4

    必要蕴含项覆盖函数

    Petrick 方法的覆盖表会选择最小的主蕴含项集合。结果是化简后的 SOP。POS 形式由补函数推导得到。

支持的运算符记法

运算 接受的符号
AND ·, *, &, , 空格
OR +, |,
NOT \', ¬, !, ~, 上划线(带上划线的 A 会渲染为 A\'
XOR , ^
常量 0, 1

示例

输入:A·B + A·¬B + ¬A·B

真值表:

A B F
0 0 0
0 1 1
1 0 1
1 1 1

最小项:m(1, 2, 3)。最小 SOP 可化简为 A + B(两个变量的 OR)。化简器会逐步展示:

  1. 按 1 的数量对最小项分组
  2. 合并相邻配对:(1,3) → -B,(2,3) → A-
  3. 覆盖表显示两者都是必要项 — 最终形式:A + B

为什么要最小化

  • 更少逻辑门:每个 AND/OR 项都会消耗硅面积或 FPGA LUT。
  • 更短关键路径:更小的逻辑通常意味着更低的传播延迟。
  • 更低功耗:开关节点更少。

算法限制

  • 变量数量:Quine-McCluskey 在最坏情况下按 O(3^n / n) 扩展。本工具可舒适处理最多 8 个变量;再往上应使用 Espresso 风格的启发式 minimisers(不能保证绝对最小,但可行)。
  • 无关项(don't-care terms):使用 d(indices) 语法包含它们;当某些输入组合不可能出现时,可以得到更小结果。

常见问题

Sum-of-products 是 OR-of-ANDs(如 AB + CD);product-of-sums 是 AND-of-ORs(如 (A+B)(C+D))。函数相同,结构不同。化简器会返回两者 — 选择适合下游工具的形式即可。

可以。把它们和最小项一起输入为 d(index1, index2, ...)。minimiser 会把它们视为可自由分配的值,从而得到更小结果。

如果分组选得正确,两者都能给出最小成本结果,但 K-map 依赖人工发现尽可能大的分组。Quine-McCluskey 是确定性的,并且总能找到最优解。

XOR 会在最小化前展开为 AND/OR/NOT。你会得到等价的 SOP,但 XOR 结构会丢失。如果要保留 XOR 的优化,需要另一种算法(Reed-Muller)。

相关工具