卡诺图 (K-Map) 求解器

卡诺图（K-Map）求解器可以简化 2 到 5 个变量的任何布尔逻辑函数，并以带有颜色编码分组的经典卡诺图形式展示简化过程。输入您的最小项、最大项，或使用交互式真值表 —— 该求解器在后台运行 Quine-McCluskey 算法，寻找每个质蕴涵项，标记必要项，并生成带有逐步解释的最小积之和（SOP）或和之积（POS）表达式。点击任何质蕴涵项标签可使它在卡诺图上覆盖的单元格脉冲闪烁，观察分组如何简化逻辑。

什么是卡诺图？

卡诺图（由 Maurice Karnaugh 于 1953 年发明）是真值表的图形化表示，其布局使得仅相差一个输入变量的单元格在物理上也是相邻的。其中的关键技巧是对行和列进行格雷码排序：连续的标签如 00, 01, 11, 10 之间恰好只相差一位。这种相邻性让您可以直观地发现可以合并为单个简化项的 1 组（或 0 组）。

对于 n 个输入变量，卡诺图有 2^n 个单元格。4 变量卡诺图是包含 16 个单元格的 4×4 网格；5 变量图则绘制为两个相邻的 4×4 网格。

SOP vs POS：选择哪种形式

积之和 (Sum of Products, SOP)

SOP 对 1 单元格进行分组。每个分组变成一个文字的乘积（AND），所有分组再进行“或”（OR）运算。例如：AB'C + BD。SOP 通常是默认选择，因为它直接对应于“与-或”门电路网络。

和之积 (Product of Sums, POS)

POS 对 0 单元格进行分组。每个分组变成补全文字的和（OR），所有和项再进行“与”（AND）运算。例如：(A + B')(C + D')。当函数中的 1 多于 0 时，POS 通常会更简洁。

本工具会独立计算这两种形式 —— 您可以切换输出模式来比较文字数量，并选择最适合您实现的那一种。

卡诺图的分组规则

• 仅限 2 的幂次分组：分组必须包含 1, 2, 4, 8 或 16 个单元格。不允许 3 或 5 个单元格的分组。
• 矩形形状：分组中的单元格必须形成矩形（水平、垂直或跨边界折叠）。
• 折叠相邻性：顶行与底行相邻；最左列与最右列相邻。这就是格雷码排序重要的原因。
• 优先选择最大分组：更大的分组可以消除更多变量，从而产生更短的乘积项。8 单元格的分组消除 3 个变量；4 单元格消除 2 个；2 单元格消除 1 个。
• 每个 1 都必须被覆盖：每个 1 单元格（对于 SOP）或 0 单元格（对于 POS）必须至少被一个分组覆盖。
• 允许重叠：同一个 1 可以被多个分组覆盖，如果这样能形成更大的分组。
• 随意项是灵活的：如果包含随意项能产生更大的分组，则可以将它们分组，但它们不必被覆盖。

质蕴涵项和必要质蕴涵项

质蕴涵项（Prime Implicant）是无法再进一步扩大的分组 —— 扩大它会包含 0 单元格（对于 SOP）。求解器会列出它找到的每一个质蕴涵项。然后它会选择一个最小覆盖：即覆盖每个所需最小项的最少质蕴涵项集合。

必要质蕴涵项（Essential Prime Implicant）被标记为 必要项，因为它是在覆盖某个特定最小项时的唯一质蕴涵项。每个最小表达式都必须包含所有必要质蕴涵项。在选定它们之后，剩余未覆盖的最小项将由性价比最高的额外质蕴涵项来覆盖。

随意项条件 (Don't-Care Conditions)

随意项（在卡诺图上显示为 X）是输出结果无关紧要的输入组合 —— 要么它在实际电路中永远不会出现，要么它的值对系统没有影响。算法可以自由地将每个 X 视为 0 或 1，选择能产生最简表达式的那种。在实践中，随意项通常能减少 30–60% 的文字数量。现实世界中的一个常见来源：十进制数字解码器仅使用 16 种四位输入组合中的 10 种，剩下的 10–15 组合即为随意项。

Quine-McCluskey 算法

卡诺图是一种可视化方法，但对于超过 4–5 个变量的情况，它会变得不切实际。Quine-McCluskey (QM) 算法是其表格形式的等效方法 —— 数学上严谨且可扩展。本求解器内部使用 QM 算法：

1. 以二进制列出最小项，并按 1 的位数进行分组。
2. 合并相邻组的配对（相差一位），将不同位替换为破折号。例如：0011 + 0111 → 0-11。
3. 重复此过程直到无法进一步合并。无法合并的项即为质蕴涵项。
4. 建立质蕴涵项表 —— 行为质蕴涵项，列为所需的最小项。识别必要质蕴涵项（只有单个勾选标记的列）。
5. Petrick 方法 / 穷举搜索：对于剩余未覆盖的最小项，找到覆盖它们的最简额外质蕴涵项集合。

如何使用此计算器

1. 选择变量数量：2, 3, 4 或 5 个。卡诺图网格会自动适配。
2. 选择输入方法：
   • 最小项：输入 F = 1 时的索引（例如 1, 3, 5, 7）以及任何随意项。
   • 最大项：输入 F = 0 时的索引。求解器会自动将剩余部分计算为 1。
   • 真值表：点击每一行在 0、1 和 X 之间循环切换。非常适合手动设计的逻辑。
3. 选择 SOP 或 POS 输出。通过切换来比较两种形式 —— 通常其中一种会更短。
4. 点击“求解”。卡诺图会出现，每个质蕴涵项都有独特的颜色。点击任何标签可使它覆盖的单元格脉冲闪烁。
5. 查看步骤：Quine-McCluskey 的分解过程展示了每个质蕴涵项是如何推导出来的，以及哪些是必要的。

示例：带随意项的 4 变量函数

考虑 F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5)。

如果没有随意项，最小 SOP 需要多个项。通过将 {0, 2} 视为 1，求解器可以构建 4 单元格分组 A'B'（覆盖 0, 1, 2, 3）。将 5 视为 1 让它可以扩展 CD 的覆盖范围。简化结果为：

仅用 4 个文字 —— 而如果不使用随意项技巧，则需要 10 个以上。您可以通过上方的“带随意项的 4变量”快速示例加载此示例。

为什么要简化布尔函数？

• 更少的门电路 = 更低的硬件成本、更小的芯片面积、更低的功耗。
• 更快的电路：关键路径上的门延迟更少。
• 更清晰的文档：简洁的表达式更易于验证和维护。
• 数字设计的基础：每个 FPGA 综合工具都在运行 Quine-McCluskey 的后代算法（如 Espresso-II 等）。

局限性及何时使用其他工具

• 5 个以上变量：卡诺图在视觉上会变得杂乱。本工具通过拆分为两个 4×4 图来支持最多 5 个变量。超出此范围，请依赖 Quine-McCluskey 步骤或使用 ABC / Espresso 等综合工具。
• 冒险与毛刺 (Hazards and Glitches)：最小覆盖可能包含静态冒险。对于无冒险设计，需要包含冗余的质蕴涵项 —— 本工具会标记它们，但不会自动添加冒险覆盖项。
• 多输出简化：如果多个函数共享变量，联合简化（共享门电路）会产生更小的硬件。本工具一次简化一个函数。

常见问题解答

什么是卡诺图？

卡诺图（K-map）是一种用于简化布尔表达式的可视化方法。单元格的排列方式使得相邻单元格仅相差一个变量（格雷码排序）。将 1 组合成大小为 1、2、4、8 或 16 的矩形，可以得出最小的积之和表达式。

SOP 和 POS 之间有什么区别？

SOP（积之和）对 1 单元格进行分组并将其乘积项进行“或”运算，例如 A'B + CD。POS（和之积）对 0 单元格进行分组并将其和项进行“与”运算，例如 (A + B')(C' + D)。两者描述的是同一个函数，但通常其中一种形式会更简洁。

什么是随意项，为什么要使用它们？

随意项（记为 X）是输出值无关紧要的输入组合 —— 它们永远不会出现，或者其值不重要。求解器可以将其视为 0 或 1，以产生更简单的表达式。随意项通常能显著减少文字数量。

什么是质蕴涵项？

质蕴涵项是无法进一步扩大的最大可能相邻 1 单元格组（大小为 2 的幂）。必要质蕴涵项是唯一覆盖至少一个最小项的项，必须包含在每个最小表达式中。

Quine-McCluskey 算法是如何工作的？

Quine-McCluskey 是卡诺图的表格等效方法，适用于多个变量。它以二进制形式列出所有最小项，按 1 的数量分组，并迭代合并恰好相差一位的对。无法进一步合并的项即为质蕴涵项。然后通过质蕴涵项表选择最小覆盖。

这个卡诺图求解器支持多少个变量？

该工具支持 2 到 5 个变量。5 变量卡诺图显示为两个相邻的 4×4 图（一个用于 A=0，一个用于 A=1）。超过 5 个变量后，卡诺图会变得不切设计；对于更大的函数，请使用 Quine-McCluskey 步骤。

延伸阅读

• 卡诺图 — 维基百科
• Quine-McCluskey 算法 — 维基百科
• Petrick 方法 — 维基百科