第 3 讲：逻辑函数化简与 Karnaugh 图

化简的目标取决于实现形式。对两级与或电路，通常先让乘积项数量最少，再让每项文字数最少；若实际只能用 NAND 或 NOR，还要考虑门型转换后的总成本。

代数化简

常用动作：

• 合并：$AB+A\bar B=A$；
• 吸收：$A+AB=A$；
• 消去：$A+\bar AB=A+B$；
• 添加冗余：$AB+\bar AC+BC=AB+\bar AC$，其中 $BC$ 是共识项；
• 提取异或：$\bar AB+A\bar B=A\oplus B$。

代数法快但依赖观察，不容易证明已最简。Karnaugh 图把相邻性画出来，更系统。

Karnaugh 图为什么按 Gray 码排

相邻格对应只改变一个变量的两个最小项，因此可以合并消去该变量。行列顺序为

$$00,01,11,10,$$

而不是普通二进制顺序。最左和最右相邻，最上和最下也相邻；四角彼此相邻。

画圈规则

对最简与或式，圈输出为 1 的格：

1. 每组格数必须是 $1,2,4,8,\dots$；
2. 每组必须为矩形，可跨边界；
3. 组尽可能大；
4. 所有 1 至少覆盖一次；
5. 可以重叠，若重叠能减少项数或文字数；
6. 不允许把确定的 0 圈进来。

图中四角被同一组覆盖，正好说明 Karnaugh 图的上下、左右边界是首尾相接的；不同圈也可以重叠，只要能用更少的乘积项覆盖全部的 1。

一组中保持不变的变量写入乘积项：恒为 1 写原变量，恒为 0 写反变量，发生变化的变量消去。

对最简或与式则圈 0：每个 0 组产生一个和项，恒为 0 的变量写原变量，恒为 1 写反变量。

主蕴含项与必需项

不能再扩大的组对应主蕴含项。若某个 1 只被一个主蕴含项覆盖，该项是必需主蕴含项，必须选入。先选所有必需项，再用尽量少的其他主蕴含项覆盖剩余 1。

仅凭“圈最大”不一定得到最少组数，重叠和覆盖组合仍要比较。

无关项

用 X 或 $d$ 标出的组合在实际不会出现，化简时可当 0 或 1。原则是：只有在能扩大分组、减少电路时才使用；不需要覆盖所有无关项。

若设计必须在非法状态下也有确定安全行为，就不能随意把这些状态当无关项，需按系统要求指定。

五、六变量图

五变量图可看成两张四变量图；两张图同一位置的格子也相邻，因为只差第五个变量。六变量则是四张图，按 Gray 关系判断图间相邻。

实际题中容易漏掉跨图合并。每组仍要求总体格数为 2 的幂。

门型实现

最简与或式可直接变成两级 AND–OR，也可双重取反变成 NAND–NAND：

$$F=P_1+P_2 =\overline{\overline{P_1}\cdot\overline{P_2}}.$$

最简或与式适合 NOR–NOR。若输入只提供原变量而无反变量，还要把额外反相器计入成本。

与冒险的关系

对两级与或电路，若相邻的两个 1 没有被同一乘积项覆盖，输入在两格之间变化时可能出现静态 1 冒险。增加覆盖这对相邻格的冗余组，能提供过渡期间始终为 1 的路径。

因此“绝对最简”和“无冒险”可能有冲突：工程实现会有意保留一个冗余共识项。

检查

• 行列顺序是 Gray 码；
• 跨边界邻接没有漏；
• 每组格数为 2 的幂；
• 无关项没有被误当必须输出；
• 最终式随机代几组真值；
• 若指定 NAND/NOR，实现形式和有效电平一致。