
最小与或式不是风格偏好,而是关于你电路的物理事实。你留在表达式里的每一个乘积项,都是一个两输入与门,要买、要摆、要布线。Quine–McCluskey 算法配合精确最小覆盖,能把一张臃肿的真值表变成行为在所有输入上都一致的最少门数。本文是 Elysia Tools 上「布尔代数表达式化简器(Karnaugh Map)」工具的实战指南,它输出最小与或式(SOP)、格雷码卡诺图、规范的 Σm 形式,以及真值表验证结果。
一个什么也吸收不掉的例子
从一个最小、也最有教益的案例开始:AB + A'B。两个项、四个文字,读第二遍也读不出新东西。把 B 提出来得到 B(A + A'),而 A + A' = 1,整个表达式就塌缩成 B。化简器从另一个方向给出同样的结论。它把 ON 集读成两变量下的 Σm(1, 3),找出恰好一个素蕴涵项,报出最小与或式 F = B,一个项、一个文字。

这个结果对应的卡诺图值得盯一会儿。按格雷码排序,列依次是 0 和 1,B = 1 那一整列亮着,B = 0 那列是暗的。2 变量图里,一列两个相邻的 1 就是一个 2^n 大小的组,也就是一个不含任何变量的文字。亮着的那一列就是全部答案,图也让你看清为什么不存在更小的表达式。跑一遍验证,四种赋值全部与原式一致,而这一步恰是手工化简最常跳过的。
为什么必须先求素蕴涵项
你不能见大圈就圈,原因是一个大圈可以合法却仍然错误。Quine–McCluskey 用代数方式遍历组合,绕开了看图猜的路子:它先列出全部最小项,合并只差一个变量的成对项,再合并合并出来的结果,最后只留下无法继续扩展的项。留下来的这些就是素蕴涵项。

必要素蕴涵项指至少覆盖了一个其他素都不覆盖的最小项的那个素。只要某个最小项只被一个素覆盖,这个素就必须出现在最终答案里,没有别的选法。必要素先被锁定,之后算法才去看剩下还没覆盖的最小项,判断是需要再加一个素,还是两个更小的素合起来代价更低。最后这一步就是精确最小覆盖,真正的化简器与启发式化简器的分界也在这里。
同一个工具上的第二个算例里能看清这套必要素逻辑。三个变量、ON 集 Σm(0, 1, 2, 4, 5, 6) 时,Quine–McCluskey 找出两个素蕴涵项。B' 覆盖最小项 0、1、4、5,C' 覆盖 0、2、4、6。两个都是必要素:最小项 1 只有通过 B' 才能覆盖,最小项 2 只有通过 C' 才能覆盖。两个项、两个文字,不存在更便宜的覆盖。把这串最小项按「最小项模式」贴进 布尔代数表达式化简器(卡诺图辅助),可以一步步看到必要素是怎么被选出来的,不必凭空相信。
两种输入模式
工具接受两种形式的函数,选哪种,会改变验证这一步能证明什么。表达式模式下你直接写开关代数记号:+ 表示或,· 或相邻书写表示与,' 或 ! 表示非,^ 表示异或,括号用来分组,变量最多四个,A 到 D。工具先解析表达式,在整个赋值空间上求值,然后才化简,原式因此始终是基准。
最小项模式下你给出函数取值为 1 的那些下标,比如 0,1,2,4,5,6,再加上变量个数。这里 ON 集本身就是规格,没有可能被解析错的表达式,也没有需要规范化的东西。需求来自真值表、数据手册的时序表或者扫描链转储,而不是来自某位设计师写的等式时,就该用这个模式。上面那个 Σm 例子的 3 变量卡诺图按格雷码排成 00、01、11、10 四行,在跑任何算法之前,用眼睛读亮格就能复现 B' + C'。
异或有一点要提醒:异或不是 GF(2) 上开关代数的基本运算符。解析器接受 ^ 只是图方便,可含它的项并不是文字的乘积,不会出现在合法的与或式里。设计确实需要异或时,把它写成 (A'B + AB'),让化简器手里有文字可用。
卡诺图是一张覆盖图
卡诺图是把真值表折成网格,让相邻单元永远只差一个变量。图之所以管用,全靠这条相邻性质:2^n 个相邻的 1 塌缩成一个少 n 个文字的项,边缘的环绕也算相邻,格雷码排序正是为此存在。两个 1 并排得到一个项;四个连成方块,则得到两变量上的两个项。
图也是你复核算法结论的地方。工具给出最小与或式后,把每个项摊回图上,看成它覆盖的单元集合,确认这些集合的并集等于 ON 集,外面没有多余的格。覆盖到 0 格的项根本不算蕴涵项,出现这种情况的结果无论看着多漂亮都是错的。验证输出是另一道保险:它在真值表的每一个赋值上分别求简后函数和原函数的值,报告两者是否一致。
四个变量时图变成 4×4 网格,数圈才真有讲究:16 格的组覆盖全部最小项,8 格的组横跨一行或一列,4 格的组可以是 2×2 方块,也可以是 1×4 的长条。工具最多接受四个变量,并且直接渲染格雷码卡诺图,任何手工化简在写进 RTL 之前,都可以拿这张图交叉核对。
门数是怎么来的
最小与或式的实际收益在于它与硬件一一对应。一个含 n 个文字的乘积项变成一个 n 输入与门,项与项之间的加法变成一个或门。取反文字所需的反相器在现代标准单元库里通常不要钱,真正疼的是项的个数和每一项的扇入。

直接比较两个例子。AB + A'B 化简成一个项、一个文字,整个函数就是一根导线。Σm(0,1,2,4,5,6) 化简成两个各含一个文字的项,也就一个 2 输入或门。两个例子都不需要一个与门。停在规范式上的粗糙化简,会为 Σm 那个例子给出三个各含三个文字的项,那就是 3 输入与门接 3 输入或门,真值表一模一样,硅片面积和延迟却实打实更多。
这类算术正是应该在评审之前、而不是之后跑一遍工具的场合。综合器丢给你一份网表、一串 Verilog assign、一棵多路选择器树或者一个译码后的状态机,而你想知道自己离地板还有多远时,就用 布尔代数表达式化简器(卡诺图辅助)。更广的工程工具箱见 工具目录。
验证本身就是交付物
一份化简只有在你能够证明它与原式等价时才值得交付,而真值表上的等价是有限的,因此可以核查。工具里验证这一步比它的代数更重要的原因就在这里。它会走遍变量允许的每一个赋值,两个变量四行,四个变量十六行,逐行把原式和最小与或式比对。
把这份输出当成契约,别当成走过场。显示一致,意味着两个函数在所有可能的输入上都相同,这是对一份数字设计能下的、仅次于形式化等价证明的最强断言。显示不一致,要么解析器把你的表达式读成了别的意思,要么覆盖过程中丢了项,两者都值得在采纳结果前追下去。Σm 那个例子报告全部八个赋值一致,AB + A'B 报告四个赋值全部一致。
有个便宜的办法可以早点抓住解析偏差:用两种本应一致的记法把函数写两遍,比如 AB + A'B 和 (A AND B) OR ((NOT A) AND B),都跑一次,确认工具返回同一个规范 Σm。两者不一致,毛病出在表达式的读取上,不在化简环节,你也就赶在它进原理图之前抓住了一个笔误。
评审要过两道关
在把任何最小与或式当成设计之前,把原式和化简结果并排放好,分开问两个问题。第一,它们等价吗?这个问题验证环节会穷尽地回答,你应该信它。第二,这个结果是你真正想要的,还是某个被你写错了的规格所能得到的最小表达式?两个问题并不相同,化简器分辨不出其中的差别。
输入列表里少写一个最小项,是第二类失败最典型的出场方式。你写 Σm(0, 1, 2, 4, 5, 6),心里想的是一个奇偶校验器,结果拿到一个干净的两项结果,而这个结果既不是奇偶函数,也不是它的补。算法完全照你说的做了。为了让图好看而扩到 4 个变量也是陷阱:没用到的变量会带来成行成列的重复格,还会把最小项下标整体抬高,因为下标是按位置排的,取决于变量个数。
第三个陷阱是时序。按文字数优化,和按级数深度优化不是一回事。两级与或式在结构上深度统一,这也是两级逻辑好推理的原因;可你需要的关键路径短于两级门延迟时,单纯化简已经帮不上忙,该做的是重构函数,或者改用多级技术。
什么时候干脆不用化简器
有些情况跑工具纯属白费力气,这不必遮掩。综合流程里已经有一个称职的化简器,答案就躺在网表里,你再跑一遍只多出一点安心。函数只有一两个变量时,手算比敲表达式快,AB + A'B → B 就是例子。输入是毫无结构的成堆最小项,你只需要一个能跑的表达式、而不需要可证明的最小解,那么规范的 Σm 展开本来就是对的。
工具的价值在中段那片拥挤地带:三四个变量的密集最小项集合、从译码树或多路选择器链拼出来的表达式,以及一切以生成式 RTL 形式到你手上的东西。最小与或式在这些场合都不显然,门数也会变成你必须交代的面积和延迟。合适的习惯是早点跑,先看卡诺图,再看答案,最后让验证输出结案。
在 布尔代数表达式化简器(卡诺图辅助) 上把 Σm(0, 1, 2, 4, 5, 6) 和 AB + A'B 两个例子各跑一次,能一遍看到必要素的选择和已验证的等价。更多数字逻辑算例在 Elysia Tools 算例库,那里的输入输出对可以直接抄进你自己的流程。
Pingback: Boolean Algebra Simplifier Field Guide: When Four Literals Collapse to One Gate and a Karnaugh Map Proves It - COSESAI