定义#

又称 “循环BCD码” 或 “Gray码”。

定义：$G = B \oplus (B \gg 1)$。表现为：相邻的编码只有一位不同。

来源#

常规的二进制在不断加一的过程中，可能会出现多位同时翻转的情况，例如从 3 加到 4 的过程中，最低的三位全都变了（011 -> 100）。而 格雷码希望“每次只变一位”。

格雷码在编码器、计数器、位置检测等场景中更稳定，不容易因为多位同时翻转而出错。

为了得到 格雷码，我们需要先观察二进制进位时发生的现象。从 3 到 4 时，最后两位从 11 变成了 00, 第三位则从 0 变成了 1。
这个过程中，没有变的是 “最后两位相同”。而利用异或，恰好可以抹去这种 “11” 到 “00” 的变化。

换句话说，格雷码记录的实际上是：二进制的相邻两位之间有没有发生变化。
这使得当二进制数加 1 时，虽然底层可能有多个位翻转，但这些翻转在“相邻位关系”里最终只会体现为一个位置的变化，于是 格雷码就只变 1 位。

例如数字 3，计算：$011 \oplus (011 \gg 1) = 010$；数字 4，计算：$100 \oplus (100 \gg 1) = 110$。两者只差了一位

逆变换#

$b_n$ 为二进制数，$g_n$ 为格雷码

$b_n = g_n$
$b_i = b_{i+1} \oplus g_i$

也就是：最高位不变，后续位分别与左侧的结果进行异或。

分配率公式#

$A(B + C) = AB + AC$

$A + BC = (A + B)(A + C)$

注释

上述公式的推导为：
$(A + B)(A + C) = A + AB + AC + BC = A(1 + B + C) + BC = A + BC$

反演率 (德摩根定律)#

这是 “与” 和 “或” 互换的基石。

提示

与的非等于非的或，或的非等于非的与

$(AB)' = A' + B'$ - 对应：A 与 B 中至少有一个为假

$(A + B)' = A'B'$ - 对应：A 与 B 都为假

反演定律#

两条基本公式：

$\overline{A \cdot B} = \overline{A} + \overline{B}$ - 对应：A 和 B 不同时为真

$\overline{A + B} = \overline{A} \cdot \overline{B}$ - 对应：A 和 B 都不为真

多余项定律#

$AB + A'C + (BC...) = AB + A'C$

对偶定理#

若两逻辑表达式相等，则它们的“对偶式”也相等。

对偶式的书写规则：与 ↔ 或； 0 ↔ 1； 变量和反变量不变

通法#

观察所有 Y = 1 的部分，假设某一个时刻：
$Y = 1, A = 1, B = 0, C = 1$
则有：$Y = AB'C + ...$
以此类推，按顺序写完所有情况。也就是每组输入变量取值的组合对应一个乘积项。

最小项#

在上面的通法中，$AB'C$ 就是一个最小项。使其值为 1 的变量取值就是它的编号（在某一类输入下为 1），此处为 $(101)_B = 5$，即 $m_4$

全体最小项之和为 1；任意两个最小值之积为 0；两个逻辑相邻的最小项之和可以合并，消去一对因子。

最大项#

例如 $A + B + C'$。使其值为 0 的变量取值就是它的编号（在某一类输入下为 0），此处为 $(001)_B = 1$，即 $M_1$

全体最大项之积为 0；任何两个最大项之和为 1；

最小项与最大项的关系#

最小项是从单个输入开始，不断寻找更多的输入来作为限制条件
最大项是从所有输入开始，不断排除无关的输入

单个最大项与最小项存在联系，$M_1' = \overline{A + B + \overline{C}} = A'B'C = m_1$，最大项与最小项相反的编号原则恰好凑上了反演定律。

而在 n = 3 时，$2^3 - 1 = 5$，所以：$M_1' = m_1 = m_5'$，即 $M_1 = m_5$，两者的下表集合是互补的。

卡诺图的绘制#

卡诺图，本质是用格雷码列出最小项矩阵，将逻辑上的相邻表现为几何图形的相邻。

理想的卡诺图应该是一个 n 维的立方体，我们只能尽量将它投影到纸面上。
使用格雷码而非二进制数，是因为格雷码能保证逻辑上相邻

例如三个变量时：

四个变量时（表中的数字为最小项编号）：

卡诺图中的相邻

卡诺图更接近与一个闭合的图形，由于格雷码的特性，两个轴对称的方块也是相邻的（注意不是中心对称），有：

• 左右边界相邻
• 上下边界相邻
• 四个角可以组成一组

注意：下文中的“相邻”指的都是逻辑上的相邻

函数式转卡诺图#

例如 $AB + AC$，遵循以下步骤：

• AB：在同时满足 A = 1 与 B = 1 的方格内填 1
• AC：在同时满足 A = 1 与 C = 1 的方格内填 1
• 其余表格填 0

注释

这里本质上是用了 $AB = AB(C + C')$ 的公式

对于更复杂的 $Y = A'BC'D + B'C'D' + A'C$，则有：（空白格子为 0）

卡诺图转最简式#

在卡诺图上，“相邻”的两个方格对应一个可以消去的因子，“相邻”的 2*2 共4个方格对应两个可以消去的因子，$2^n$ 个格子对应 $n$ 个可以消去的因子……
不断寻找这种“相邻”关系，并将它们圈起来作为标记，就可以据此写出对应的最简式。
同时，圈的个数越少越好，单个圈越大越好。这样才能保证最简。

需要注意的是，每个方格都是可以重复利用的，逻辑上的并集并不影响正确性。
例如：上图中右上四个可以合并，最左侧的两个可以合并，第二排的中间两个也可以合并。

提示

卡诺图中六个相邻的方格不可能一次性化简完毕，至少分为两组

嵌套逻辑函数的化简#

对于较为复杂的嵌套型逻辑函数，例如：
$Y = (A'D' + C'D + CD') \oplus (AC'D' + ABC + A'D + CD)$
针对左右两个与或式，可以记为 Y1 与 Y2, 分别画出卡诺图，然后对两张卡诺图相同位置的方块做异或，结果就是 Y 的卡诺图。

注释

此处如果不使用卡诺图来计算，将非常复杂

与非-与非形式#

将 与或式 取两次反，也就是利用反演率:
$Y = AB + AC = \overline{\overline{AB + AC}} = \overline{\overline{AB} \cdot \overline{AC} }$

与或非形式#

针对 $Y'$ 的卡诺图进行化简，写出 与或式 后取反： $Y = AB + AC = (A' + B'C')'$

或与形式#

对 与或非式 应用反演率：
$Y = (A' + B'C')' = (A'')((B'C')') = A(B + C)$

提示

也可以直接由卡诺图得到

或非-或非形式#

对 与或非式 中的“与”应用反演率，例：
$Y = (A' + B'C')' = (A' + (B'C')'')' = (A' + (B + C)')'$

重要

上述形式即使化到最简，也不一定是唯一的