布尔代数 — 把逻辑变成可以化简的代数¶

这一章讲什么: 给你一套处理「真/假」的数学——三个运算符、十几条法则、两种标准写法;然后给你两个化简工具(代数演算、卡诺图)。为什么值得学: 计算机的各种操作都可以由布尔函数指定,而表达式越短,硬件越便宜。本章的主线例子贯穿始终:加法器的进位函数,从一句英语化简到三对门。

1. 顶层全景:从逻辑到电路的五级台阶¶

  ① 三个运算符:AND(∧, 像乘)、OR(∨, 像加)、NOT(¬, 取反)
        ↓ 配上真值表(枚举所有输入组合的结果)
  ② 一套代数法则:结合/交换/分配/幂等/补值…… + 德摩根定律
        ↓ 把「想要的功能」写成函数
  ③ 两种规范形式:最小项之和 ∑、最大项之积 ∏(完整、唯一、但啰嗦)
        ↓ 化简(= 省硬件)
  ④ 两条化简路:代数演算 和 卡诺图(图形化,同一套法则的肉眼版)
        ↓
  ⑤ 每个 ∧ 变与门、每个 ∨ 变或门、每个 ¬ 变非门 → 电路

  图说:五级台阶,①②是语言,③是标准写法,④是优化,⑤是落地。

原书给本章的定位写得直白:「计算机的功能基于布尔逻辑,这意味着计算机的各种操作都可以由布尔函数指定」⁶⁷。这句话是后面一切的许可证——加法器(第 6 章)、存储单元(第 7 章)、乃至整条指令流水线(第 9 章),都是「布尔函数 → 电路」这一个动作的大规模重复。所以本章的目标不是「学会一门代数」,而是拿到那张把逻辑翻译成硬件的执照:读完你会相信,任何能被真值表穷举的功能, 都注定能变成一堆开关——这只是工程,不再是科学。

这一章在全书链条里的位置:第 3 章的算术暴露了需求(进位怎么算), 第 5、6 章提供电路实现。布尔代数是中间的翻译层——把「要什么功能」翻译成「什么式子」,再把「什么式子」化简成「最省的门」。

历史坐标先摆好:布尔代数由英国数学家 George Boole 在 19 世纪建立, 他想「利用数学的严密性来解决逻辑问题」;1930 年代中期, 研究生 Claude Shannon 证明了电子开关能够实现所有的布尔代数表达式—— 「Shannon 的发现打开了一个全新的世界,布尔代数成为了计算机的数学基础」¹。也就是说:这套数学在计算机存在之前一百年就备好了,等的是开关。

2. 三个基本运算符:AND 像乘,OR 像加,NOT 像负¶

三种运算符,原书各给了符号约定、文字定义和真值表²:

运算符	符号(本书)	定义(一句话)	像初等代数里的
AND(与)	x ∧ y	两个操作数都为 1 时结果才为 1	乘法(x·y)
OR(或)	x ∨ y	至少一个为 1 时结果为 1	加法(x+y)
NOT(非)	¬x	0 变 1,1 变 0(单目)	算术非(但有显著不同)

「AND 是相乘,OR 是相加,这绝非偶然」:Boole 造这套代数时, 就在寻找用加法和乘法处理逻辑语句的方法³。真值表(列出所有输入组合的结果) 是本章的基本证据形式——两个位就有 4 种组合,三个位 8 种,全部列出来逐个验证, 后面的每一条法则都靠它背书。三个运算符的真值表,本章之后要反复回来查:

  x y | x∧y    x y | x∨y    x | ¬x
  ----+----    ----+----    ---+----
  0 0 |  0     0 0 |  0     0 |  1
  0 1 |  0     0 1 |  1     1 |  0
  1 0 |  0     1 0 |  1
  1 1 |  1     1 1 |  1

  图说:AND 只有最后一行是 1(两个都真);OR 只有第一行是 0(两个都假);
  NOT 只有两行——它是单目运算符,没有组合可言。

AND 的真值表形状像乘法表(只有 1×1=1),OR 的形状像「钳制的加法」 (1+1 还是 1,不是 2)——这也预告了幂等性:x∨x = x 这种初等代数里不存在的事,从真值表第二、四行就能直接读出。

一个已经见过的例子:第 3 章表 4-1 里两个位的加法—— 进位 = x ∧ y,和 = x ⊕ y(XOR,异或)。位加法本身就是布尔函数, 这是「算术 = 逻辑的物理表现」的第一个实证⁴。

3. 布尔表达式与法则:一半似曾相识,一半截然不同¶

3.1 词汇表¶

字面量(literal):表达式里某个变量或其补的一次出现。 x ∧ y ∨ ¬x ∧ z 里有 3 个变量、4 个字面量(¬x 是单独一个字面量)⁵;
项(term):被运算符组合起来的字面量组,如 (x ∨ y);
优先级:NOT > AND > OR,括号最优先⁶。记法:¬x ∧ y 读作 (¬x) ∧ y—— NOT 永远贴着它右边那一个变量,除非括号扩大它的管辖范围; 写表达式时拿不准就加括号,布尔世界里多一对括号没有任何代价。

3.2 与初等代数相同的法则⁷¶

法则	式子	一句话
结合律	x∧(y∧z) = (x∧y)∧z;∨ 同理	同种运算换顺序,值不变
自等值	x∧1 = x;x∨0 = x	乘 1 加 0,原样归还
交换律	x∧y = y∧x;∨ 同理	操作数换位置,值不变
AND 对 OR 分配	x∧(y∨z) = (x∧y)∨(x∧z)	乘对加分配,和老代数一样
AND 的零一值	x∧0 = 0	乘 0 得 0
NOT 对合	¬(¬x) = x	否定的否定,回到原值

原书对结合律给了完整的 8 行真值表验证,其他法则留作练习—— 「列出所有组合、算等式两边、逐行相等则得证」是这个领域证明的全部套路⁸。把 AND 结合律的那张表走一遍,体会「证明」在这个世界里有多朴素:

  要证:x ∧ (y ∧ z) = (x ∧ y) ∧ z
  三个变量 = 8 种组合,全部列出,等式两边各算一列:

  x y z | (y∧z) | (x∧y) | x∧(y∧z) | (x∧y)∧z
  ------+-------+-------+----------+----------
  0 0 0 |   0   |   0   |    0     |    0     ← 相等
  0 0 1 |   0   |   0   |    0     |    0     ← 相等
  0 1 0 |   0   |   0   |    0     |    0     ← 相等
  0 1 1 |   1   |   0   |    0     |    0     ← 相等
  1 0 0 |   0   |   0   |    0     |    0     ← 相等
  1 0 1 |   0   |   0   |    0     |    0     ← 相等
  1 1 0 |   0   |   1   |    0     |    0     ← 相等
  1 1 1 |   1   |   1   |    1     |    1     ← 相等

  8 行全相等,证毕。没有归纳法、没有引理——穷举就是这个宇宙的完备性。

这个「笨办法」有个隐藏优点:变量只有 0/1 两个取值,所以穷举的规模是 2ⁿ, 有天花板;初等代数里没法对「所有实数」列一张表,布尔代数可以。这也是计算机恰好能实现这套代数的深层原因——开关天然就是布尔世界的「所有取值」。

3.3 与初等代数不同的法则——本章真正的考点¶

法则	式子	为什么不一样
OR 对 AND 分配	x∨(y∧z) = (x∨y)∧(x∨z)	初等代数里加法不对乘法分配:1+(2·3)=7 ≠ (1+2)·(1+3)=12⁹
OR 的零一值	x∨1 = 1	加法没有「加什么都得某个固定值」的零一值
补值	x∧¬x = 0;x∨¬x = 1	初等代数里 x+(−x)=0 但 x·(−x)=−x²,不对称
幂等性	x∧x = x;x∨x = x	老代数里 x·x=x²、x+x=2x,都会变大

幂等性值得单独停一秒:x∨x = x 意味着「把一个项复制一份再合并」是合法操作。 这个看似无聊的法则,是 4.5.2 节代数化简的第一个动作(复制最小项), 也是卡诺图里「一个单元格可以进多个组」的合法性来源³⁰。记住它,后面要用。

3.4 德摩根定律:NOT 的分配方式,全章用得最多的一条¹⁰¶

  ¬(x ∧ y) = ¬x ∨ ¬y      「与的非 = 非的或」
  ¬(x ∨ y) = ¬x ∧ ¬y      「或的非 = 非的与」

直观读法:「不是(又 A 又 B)」=「不 A 或不 B」;「不是(A 或 B)」=「既不 A 也不 B」。这两行是第 5 章门电路变换、第 6 章电路优化的主力工具——它告诉你: 任何 AND 都能换成 NOT+OR,任何 OR 都能换成 NOT+AND, 门的选择因此有了自由度。

它的证明照例只要一张 4 行真值表(原书留作练习,我们替它走一遍)⁶¹:

  证 ¬(x ∧ y) = ¬x ∨ ¬y:
  x y | x∧y | ¬(x∧y) | ¬x | ¬y | ¬x∨¬y
  ----+-----+--------+----+----+-------
  0 0 |  0  |   1    | 1  | 1  |   1    ← 相等
  0 1 |  0  |   1    | 1  | 0  |   1    ← 相等
  1 0 |  0  |   1    | 0  | 1  |   1    ← 相等
  1 1 |  1  |   0    | 0  | 0  |   0    ← 相等
  四行全等,证毕。另一条 ¬(x∨y) = ¬x∧¬y 同理(或按对偶原理直接得出)。

留意最后一行——这又是一个对偶原理的用例:证了一条,另一条不必再证。德摩根定律把对偶从「观察」升级成了「工具」。

3.4 德摩根定律的工程读法¶

书里给的符号形式是 ¬(x ∧ y) = ¬x ∨ ¬y,但工程师记忆和使用的版本往往是 「长横线变短横线,或变与」:一个盖在整体上的 NOT(长横线),拆开时要分给每个变量(短横线),同时把 ∧ 换成 ∨:

  ¬(a ∧ b ∧ c)  =  ¬a ∨ ¬b ∨ ¬c     ← 一化三
  ¬(a ∨ b ∨ c)  =  ¬a ∧ ¬b ∧ ¬c

反过来也常用:想把几个短横线合并成一个长横线,就把 ∨ 换回 ∧。第 5 章会看到具体场景:用某一种晶体管(比如 NMOS)天然擅长做「¬(a∨b)」形的电路,德摩根定律就是把它改写成手头有的形状的扳手。

德摩根定律还是对偶原理的范例:把式子里的 0↔1、AND↔OR 全部互换, 等式仍然成立¹¹。回看 3.2/3.3 两表:除了对合,每条法则的对偶还是一条法则 (结合律的对偶是结合律,分配的两条互为对偶,零一值/补值/幂等性两两对偶)。 布尔代数的世界里,每张面孔都有镜像。

判断(我们的,不是书里的): 对偶原理是这一章最容易被「背完就忘」的内容, 但它的工程含义很实际:为一个电路写的化简技巧,对偶地搬过去就是另一个电路的技巧—— 你只需学一半。读数字设计文献时,看到「by duality」就能认出这是免费得来的另一半。 如果错,会错在: 对偶不是等价——对偶式相等靠的是 0/1 互换后的对称性, 不是在同一取值下逐点相等;把对偶当成等价来代入,会得出错误结论。

4. 布尔函数:计算机的全部功能都是函数¶

4.1 布尔函数和初等代数函数的思维差异¶

布尔函数形如 F(x, y) = x ∧ ¬y,值域只有 {0, 1}。原书给了一个极好的心智转换指引:初等代数函数是「代入求值」——给 x、y 任何数,算出 F; 布尔函数是「列出条件」——它告诉你「哪些变量组合让 F = 1」¹²。比如 F(x, y) = x ∧ ¬y 只有 4 种可能,它的全部信息是: 仅当 x = 1 且 y = 0 时 F = 1,其余 3 种组合都是 0。

这和第 3 章「位模式无语义、解释在程序」一脉相承:布尔函数不「计算」, 它甄别——把输入空间切成「结果为 1」和「结果为 0」两半。

4.2 本章主线例子登场:进位函数¶

第 3 章说过,两个位相加的进位为 1 有四种情况(有/无来自低位的进位 cin 各两种)。用英语写完,原书立刻把它翻译成布尔函数¹³:

  Cout(cin, x, y) = (¬cin ∧ x ∧ y) ∨ (cin ∧ ¬x ∧ y) ∨ (cin ∧ x ∧ ¬y) ∨ (cin ∧ x ∧ y)

三个变量、8 种输入组合、其中 4 种让 Cout = 1。这个式子就是本章主线例子, 后面每一节都要回到它:写规范形式(§5)、代数化简(§6)、卡诺图化简(§7)、最后合成电路(第 5、6 章接手)。

把它的真值表摊开(原书表 4-6),顺便看清「最小项各就各位」的样子⁵⁷:

  组合   cin x y | ¬cin∧x∧y | cin∧¬x∧y | cin∧x∧¬y | cin∧x∧y | Cout
  ------+---------+----------+----------+----------+--------+------
   m0     0 0 0  |    0     |    0     |    0     |    0   |  0
   m1     0 0 1  |    0     |    0     |    0     |    0   |  0
   m2     0 1 0  |    0     |    0     |    0     |    0   |  0
   m3     0 1 1  |    1     |    0     |    0     |    0   |  1   ← 第一种情况
   m4     1 0 0  |    0     |    0     |    0     |    0   |  0
   m5     1 0 1  |    0     |    1     |    0     |    0   |  1   ← 第二种情况
   m6     1 1 0  |    0     |    0     |    1     |    0   |  1   ← 第三种情况
   m7     1 1 1  |    0     |    0     |    0     |    1   |  1   ← 第四种情况

  图说:每一行恰好点亮一个最小项(它「自己的」那个),Cout 列是四个最小项的 OR。
  这就是为什么规范和保证不漏:每行有且仅有一个最小项在值班。

注意 m0~m7 的编号来自「把 cin、x、y 的值按顺序拼成二进制」——m6 = 110₂ = 6。编号本身只是速记,但它让「∑(3,5,6,7)」这种写法成为可能:函数从三行式子压缩成一行编号清单,既短又不丢信息⁵⁸。这也是记号设计的示范:压缩的前提, 是双方都查得到同一张编号表。

5. 两种规范形式:完整但啰嗦的标准写法¶

规范形式(canonical form)的用途:保证你考虑到了所有可能组合,不留死角; 代价是啰嗦。两种互为对偶:

5.1 最小项之和(规范和):盯住结果为 1 的组合¹⁴¶

乘积项(product term):只有 AND 的项,如 (x ∧ y);
最小项(minterm):包含所有变量(各自补或不补)的乘积项。 n 个变量有 2ⁿ 个最小项,每个最小项只被一组输入点亮;
把函数所有值为 1 的最小项 OR 起来,就是最小项之和, 也叫规范和、析取范式(disjunctive normal form)。

简写记号:把变量取值按顺序拼成二进制数,其十进制值作下标—— cin=1, x=1, y=0 → 110₂ = 6 → m₆。于是:

  Cout(cin, x, y) = m3 ∨ m5 ∨ m6 ∨ m7 = ∑(3, 5, 6, 7)

「最小」的名字由来:它让函数为 1 的输入组合数最少(每组输入只点亮一个最小项); 对比 (cin ∧ x) 这种缺变量的项,两组输入都能点亮它¹⁵。

5.2 最大项之积(规范积):盯住结果为 0 的组合¹⁶¶

对进位式两边取补,用德摩根定律展开:

  ¬Cout(cin, x, y) = (cin ∨ ¬x ∨ ¬y) ∧ (¬cin ∨ x ∨ ¬y) ∧ (¬cin ∨ ¬x ∨ y) ∧ (¬cin ∨ ¬x ∨ ¬y)

这一步值得停一下,因为它是一次全尺寸的德摩根操作:长横线拆成四个短横线, 每个变量取补,AND 与 OR 全部互换⁶⁴。展开后读结构:

求和项(sum term):只有 OR 的项;
最大项(maxterm):包含所有变量的求和项,只被一组输入压灭(使之为 0); 名字由来:它让函数为 0 的组合数最少,为 1 的最多;
把函数所有值为 0 的最大项 AND 起来,就是最大项之积, 也叫规范积、合取范式。简写:¬Cout = ∏(3, 5, 6, 7)。

用最大项重写时的思维也要跟着换向:规范积回答的问题不是「什么时候进位为 1」, 而是「什么时候进位的补为 0」——从反面描述同一个函数。原书特意给了 ¬Cout 的真值表(表 4-7):看 0 落在哪几行(m3、m5、m6、m7), 就把对应的四个最大项 AND 起来⁶⁵。

「用最小项或最大项是等价的」——选择取决于实现函数的可用硬件组件和个人偏好⁶⁶。这句轻描淡写的等价,背后是德摩根定律撑着的整个对偶结构:你手头的门擅长做 AND 就从最小项出发,擅长做 OR 就从最大项出发,反正两条路殊途同归。

注意两个括号的编号重合(都是 3、5、6、7)不是巧合而是必然: 使 Cout = 1 的输入组合,恰好是使 ¬Cout = 0 的输入组合。最小项 mi 和最大项 Mi 是同一组输入的两种说法——对照全表就能看出,两者靠「逐变量取补 + 互换 AND/OR」互变,正是对偶原理¹⁷。

把 3 变量的全表摊开看(这是原书表 4-8 的内容),对偶就摆在明面上⁴⁴:

  编号 | 取值 xyz | 最小项 mi(=1 的那组) | 最大项 Mi(=0 的那组)
  -----+----------+----------------------+----------------------
   m0  |   000    |  ¬x ∧ ¬y ∧ ¬z        |  M0: x ∨ y ∨ z
   m1  |   001    |  ¬x ∧ ¬y ∧ z         |  M1: x ∨ y ∨ ¬z
   m2  |   010    |  ¬x ∧ y ∧ ¬z         |  M2: x ∨ ¬y ∨ z
   m3  |   011    |  ¬x ∧ y ∧ z          |  M3: x ∨ ¬y ∧ ¬z
   m4  |   100    |  x ∧ ¬y ∧ ¬z         |  M4: ¬x ∨ y ∨ z
   m5  |   101    |  x ∧ ¬y ∧ z          |  M5: ¬x ∨ y ∨ ¬z
   m6  |   110    |  x ∧ y ∧ ¬z          |  M6: ¬x ∨ ¬y ∨ z
   m7  |   111    |  x ∧ y ∧ z           |  M7: ¬x ∨ ¬y ∨ ¬z

  图说:同一行,最小项逐变量取补、AND 换 OR,就是最大项——德摩根定律逐行成立。

这个表还解释了名字的直觉来源:「最小项」指定卡诺图中 1 的最小数量 (每组输入只点亮一个),「最大项」指定 1 的最大数量(每组输入只压灭一个, 其余全亮)⁴⁵。记不住的场合,回到这张表查一行即可。

5.3 规范形式的地位¶

规范形式完整且唯一——两个函数等价,当且仅当它们的最小项集合相同¹⁸。但「唯一」不等于「最简」:Cout 的规范式有 4 项 × 3 字面量,而它的最小化形式 (马上见到)只有 3 项 × 2 字面量。规范的用途是起点和判据: 从规范式出发化简,化简完用真值表或规范式核对没改语义。

配套的工作流(原书 4.5.1 的建议,先立在这里)⁵⁴:

  ① 用英语把问题说清楚(「什么条件下结果为 1?」)
  ② 建真值表,枚举变量的所有组合
  ③ 从真值表直接读出最小项(值为 1 的行)或最大项(值为 0 的行)
  ④ 写成规范式(∑ 或 ∏)
  ⑤ 化简(§6 代数法 或 §7 卡诺图)
  ⑥ 用真值表核对:化简式在所有行上的值,和规范式完全一致

  图说:②③保证不漏情况(规范),⑤⑥保证不乱来(等价);
  真值表一头一尾各出现一次,是整个过程的守门员。

这套流程有个值得注意的性质:第 ② 步是不可省的。化简技巧再熟, 跳过真值表直接从模糊的需求写式子,漏掉的往往是那些「我以为不会出现」的输入组合 ——无关单元格(§7.5)之所以存在,恰恰是因为第 ② 步先承认了「这些组合我来标记, 而不是假装它们不存在」。

6. 最小化之一:代数演算——复制,然后合并¶

6.1 为什么要化简:门就是钱¶

落地规则一句话:每个 ∧ 变成与门,每个 ∨ 变成或门,每个 ¬ 变成非门; 硬件复杂度主要看与门和或门的数量(非门简单到几乎免费)¹⁹。更少的门 = 更低的成本、更小的面积、更低的功耗——对手持和可穿戴设备, 后三者尤其要紧²⁰。化简 therefore 不是数学洁癖,是工程行为。

6.2 最小表达式:什么叫「最简」¶

从最小项出发化简,目标叫最小乘积和:乘积项数最少;项数相同时,字面量总数最少²¹。 (对偶地,从最大项出发叫最小和乘积。)一个问题可能有多个最小解, 硬件工程师要在候选里按成本、元件可得性挑²²——第 5 章末会看到, 「审慎地添加非门反而能降复杂度」这种反直觉解。

6.3 进位函数的代数化简:三步¶

原书对 Cout 的化简,是幂等性法则的一次教科书级演示²³:

  ① 幂等性,复制第 4 项两次(现在 6 项):
     (¬cin∧x∧y) ∨ (cin∧¬x∧y) ∨ (cin∧x∧¬y) ∨ (cin∧x∧y) ∨ (cin∧x∧y) ∨ (cin∧x∧y)

  ② 重排,让每个原始项都配一个 (cin∧x∧y) 做 OR,三组各自提取公因子:
     (x∧y∧(¬cin∨cin)) ∨ (cin∧x∧(¬y∨y)) ∨ (cin∧y∧(¬x∨x))

  ③ 补值法则(x∨¬x = 1)、自等值(x∧1 = x):
     Cout(cin, x, y) = (x∧y) ∨ (cin∧x) ∨ (cin∧y)

结果对照:规范式 4 个三输入与门 + 1 个四输入或门 → 最简式 3 个两输入与门 + 1 个三输入或门。门少了一个,每个门的输入也少了。

更重要的是语义回来了:规范式的英语是啰嗦的「四种情况分别如何如何」, 化简后的英语只有一句——「cin、x、y 中至少有两个为 1,则进位为 1」²⁴。这一句正是全加器进位的人类标准说法。化简 = 找回人话。

6.4 对偶路线:从最大项化简 ¬Cout¶

同法炮制,只是把每一步换成对偶版本。先把规范积的末项用幂等性复制两次, 再加括号分组⁵⁵:

  ¬Cout = (cin∨¬x∨¬y) ∧ (¬cin∨x∨¬y) ∧ (¬cin∨¬x∨y) ∧ (¬cin∨¬x∨¬y)
          ∧ (¬cin∨¬x∨¬y) ∧ (¬cin∨¬x∨¬y)

  分组(每组配一个 (¬cin∨¬x∨¬y)):
   ① (cin∨¬x∨¬y) ∧ (¬cin∨¬x∨¬y)
   ② (¬cin∨x∨¬y)  ∧ (¬cin∨¬x∨¬y)
   ③ (¬cin∨¬x∨y)  ∧ (¬cin∨¬x∨¬y)

每组用 OR 对 AND 的分配律的一般形式 (X ∨ Y) ∧ (X ∨ Z) = X ∨ (Y ∧ Z)。第 ① 组:两个求和项共享 X = (¬x ∨ ¬y),配上 Y = cin、Z = ¬cin:

  (cin ∨ ¬x ∨ ¬y) ∧ (¬cin ∨ ¬x ∨ ¬y)
  = (¬x ∨ ¬y) ∨ (cin ∧ ¬cin)      ← 分配律逆用
  = (¬x ∨ ¬y) ∨ 0                  ← 补值法则
  = (¬x ∨ ¬y)                      ← 自等值

②③两组如法炮制,最终:

  ¬Cout(cin, x, y) = (¬x ∨ ¬y) ∧ (¬cin ∨ ¬x) ∧ (¬cin ∨ ¬y)

电路图和 6.3 的互为德摩根镜像:或门变成了以补值为输入的 AND²⁵。看起来 6.3 的版本更优(这个版本要在 6 个输入端加非门)—— 但原书提醒:解决问题的方法不止一种,硬件工程师要按元件特性权衡; 第 5 章会看到,由于门电路的电子特性,实际情况未必如图纸所示²⁶。

把两条路线的成果并排,本章的对偶主题就闭环了⁵⁶:

  最小项路线:Cout        = (x∧y) ∨ (cin∧x) ∨ (cin∧y)
  最大项路线:¬Cout       = (¬x∨¬y) ∧ (¬cin∨¬x) ∧ (¬cin∨¬y)
              │对偶──────────────│
  逐变量取补 + AND/OR 互换,两行精确地互为镜像——德摩根定律的全尺寸演示。

  图说:这不是巧合,是对偶原理的必然;学一条路线等于学了另一条。

7. 最小化之二:卡诺图——同一套法则的肉眼版¶

7.1 卡诺图是什么¶

代数演算「并不总是那么明显」;卡诺图(Karnaugh map, K 图) 把同样的化简变成看图说话。1953 年贝尔实验室的 Maurice Karnaugh 发明了它²⁷。结构:n 个变量的函数画 2ⁿ 个格子的矩形,每个最小项占一格(书里的叫法是「单元」), 值为 1 的格子填 1。

规则只有两条²⁸:

邻接规则(adjacency rule):共享一条边的两个格子,只有一个变量不同 (其余都相同,只是某个变量一格取补、一格不取);
分组消元:把相邻的 1 圈成一组(大小必须是 2 的幂),组内不同的那个变量被消掉, 不同的格子数每翻倍,消掉的变量多一个。组可以重叠、可以跨边缘回绕。

为什么邻接规则要求那么高?因为消元的合法性来自补值 + 分配: (¬x∧y) ∨ (x∧y) = (¬x∨x)∧y = y——两个最小项的差异变量 x 被吸干了²⁹。

7.2 两变量热身:F(x, y) = (x∧¬y) ∨ (¬x∧y) ∨ (x∧y)¶

这是卡诺图的完整示范,值得一步一步走完(原书图 4-7 到图 4-10)⁴⁶。

第 1 步:画图填格。 2×2 的卡诺图,纵轴 x(0 在上、1 在下),横轴 y。函数有三个最小项:m1(¬x∧y)、m2(x∧¬y)、m3(x∧y),在对应格子里填 1:

        y=0   y=1
  x=0 |  0  |  1  |      ← 右侧两个格子:m1 = (¬x∧y),m3 = (x∧y)
  x=1 |  1  |  1  |

  图说:值只在格子上有意义,「1 的分布」就是函数的全部信息。

第 2 步:第一笔分组——右边一列。 m1 和 m3 共享一条边,差别只在 x (一格 ¬x、一格 x)。圈起来,消掉 x,剩下 y。用代数核对: (¬x∧y) ∨ (x∧y) = (¬x∨x)∧y = 1∧y = y——卡诺图的一笔,对应分配律加补值法则的一次联用⁴⁷。

第 3 步:第二笔分组——下面一行。 还剩 m2 没被圈。它的邻居有 m3 (右边,已圈过)。格子可以重复进组——把 m2、m3 再圈一组,消掉 y,剩下 x。这就是幂等性在图上的样子:(x∧¬y) ∨ (x∧y) = x∧(¬y∨y) = x, 而那个被两组共用的 m3 = (x∧y),就是代数法里被「复制两次」的那一项⁴⁸。

第 4 步:读图写答案。 两组各留一个变量:x 和 y。最终:

  F(x, y) = x ∨ y

三行规范式、三个乘积项、六个字面量,两笔消成一项两个变量。 卡诺图的全部技巧就在这四步:填格、找相邻、圈组(可重叠、可跨边)、每组消一个变量。

7.3 格雷码:让邻接规则在更多变量下成立¶

两变量时邻接自动满足;加到三、四变量,格子的排列顺序就不能用 00、01、10、11 了——7(0111)和 8(1000)只差 1,二进制却四位全变,共边的格子差了两个变量, 消元规则就断了。解法是 格雷码(Gray code):相邻两数只差一位, 1943 年由 Frank Gray 推出,最初为降低开关技术的出错率³¹。

构造方法是漂亮的镜像法:写出现有位模式,下面接一份上下镜像, 原模式前补 0、镜像前补 1:

  1 位:      0      1
  2 位:     00     01 | 11     10      ← 下两行是上两行的镜像,首位变 1
  3 位:    000    001 | 011    010 | 110    111 | 101    100

所以格雷码也叫反射二进制码(RBC)³²。4 位格雷码里 7→8 是 0100→1100, 只变一位;连回绕处(15→0:1000→0000)也只变一位³³。卡诺图的轴就用格雷码排序——3 变量图的顶部是 00、01、11、10,不是 00、01、10、11; 跨边缘(m2 到 m0、m6 到 m4)同样算相邻³⁴。

7.4 进位函数的卡诺图:三笔画出 6.3 节¶

把 Cout = ∑(3,5,6,7) 填进 3 变量卡诺图(纵轴 cin,横轴 xy 按格雷码), 圈三个组,每组消一个变量³⁵:

        xy
      00  01  11  10
cin 0 | 0 | 0 | 1 | 0 |        ← m3 孤立看,实际与下面相邻
    1 | 0 | 1 | 1 | 1 |        ← m5 m7 m6

  组①:m3 + m7(纵相邻)→ 消 cin      → (x ∧ y)
  组②:m5 + m7(横相邻)→ 消 x       → (cin ∧ y)
  组③:m6 + m7(横相邻)→ 消 y       → (cin ∧ x)

  Cout = (x∧y) ∨ (cin∧y) ∨ (cin∧x)     ← 与代数法一字不差

  图说:卡诺图就是 6.3 节三步代数操作的图形化;圈的每个组对应一次「复制 + 分配 + 补值」。

逐步对照一遍,把「图形化」坐实:

  ① 填格:m3 在(cin=0, xy=11),m5 在(cin=1, xy=01),
          m6 在(cin=1, xy=10),m7 在(cin=1, xy=11)。
  ② m3 和 m7 上下相邻,差一个变量 cin → 消掉,留下 x∧y。
     对应代数法里 (¬cin∧x∧y) ∨ (cin∧x∧y) = x∧y 那一组。
  ③ m5 和 m7 左右相邻(01 列与 11 列只差 x),差一个变量 x → 消掉,留下 cin∧y。
  ④ m6 和 m7 左右相邻(10 列与 11 列只差 y),差一个变量 y → 消掉,留下 cin∧x。
  ⑤ m7 被三个组共用(就是代数法里被复制两次的那一项)。
  ⑥ 三组的结果 OR 起来:Cout = (x∧y) ∨ (cin∧y) ∨ (cin∧x)。

  图说:m7 一格进三组 = 幂等性复制两次;格子的「共用」在图上是免费的,
  在代数上是要主动复制的——这就是卡诺图省心的地方。

注意横轴的排序 00、01、11、10:m5(xy=01)和 m7(xy=11)相邻、m6(xy=10)和 m7 相邻,都只差一位;若按二进制序 00、01、10、11 排,m6 会和 m7 隔一列、和 m5 隔两列,全乱。格雷码不是装饰,是卡诺图能工作的前提。³⁴

从最大项侧同样可行:填 0、圈 0、得到 ¬Cout 的最小和乘积, 与代数结果相同;两张图放在一起,就是德摩根定律的图形化展示 (0↔1、AND↔OR 互换)³⁶。原书还把最小项图和最大项图并排画了一回 (图 4-16):同一张图的 1 和 0 互换,AND 和 OR 互换,两个函数互为补—— 「最直观地展示」了最小项指定 1 的最小数量、最大项指定 1 的最大数量⁶⁰。

7.5 更大的组与无关单元格¶

大组消得多:判偶函数 Even(x,y,z) = ∑(0,2,4,6)(3 位数偶则 1), 四个格子一个大组,x、y 全消,只剩 Even = ¬z——「x 和 y 是多少不重要, 重要的是 z = 0」,卡诺图一句话说清³⁷。

为什么四个格子能圈一组?组分大小的规则是 2 的幂:2 格消 1 个变量,4 格消 2 个, 8 格消 3 个(整个函数恒 1)。判偶的四个格子 m0、m2、m4、m6 在图上排成「隔列相望」的位置——因为横轴是格雷码,相邻列共享的边比二进制序多, m0 与 m2、m4 与 m6 都相邻,跨边缘处 m0 还和 m4 相邻, 四格连成一个「可以从一边到另一边」的环带⁴⁹。这正是格雷码排序的回报: 按二进制序排,这些格子会散;按格雷码排,它们恰好围成一圈。

4 变量卡诺图:再加一个变量,格子翻倍到 16,画成 4×4—— 纵轴放 w、x(两个变量的格雷码:00、01、11、10),横轴放 y、z⁵⁰。规则不变:圈还是 2 的幂、还是可重叠可跨边,只是现在最多能消 4 个变量。变量再多(5、6 个)格子变成 32、64,人手已经圈不过来——这就是为什么卡诺图是教学工具和行业直觉的来源,而真正的设计交给算法(见§9 判断三)。

无关单元格(don't care):有时你知道某些输入组合永远不会出现 (例:两个事件不会同时发生,则 x=y=1 那格无关紧要)。卡诺图里这格标 X, 圈不圈随你——圈进去能变大组就多消一个变量,不圈也无妨³⁸。原书的小例子:F(恰好一个事件发生)= 0、1、1、X,把 X 圈进组,得到 F = x ∨ y, 一个或门完事³⁹。「设计并非凭空而来」——对输入的每一点领域知识, 都可能换成硬件里少几个门。

把无关单元格的例子走完整,因为它展示了「X 值多少钱」:

  问题:两个事件 x、y 不会同时发生;F = 「恰好一个事件发生」
  真值表:  x y | F
          -----+---
           0 0 | 0     (都没发生)
           0 1 | 1     (y 发生)
           1 0 | 1     (x 发生)
           1 1 | X     (不可能出现)

  卡诺图(2×2):
        y=0  y=1
  x=0 |  0 |  1 |
  x=1 |  1 |  X |    ← X 这一格:圈也行,不圈也行

  解法一(不圈 X):两个孤立格 → F = (¬x∧y) ∨ (x∧¬y)  ← 两个与门一个或门
  解法二(圈上 X):下面一行 + 右面一列 → F = x ∨ y     ← 一个或门!

  图说:X 的一格让两组从「两格组」升级成能跨格的大组,少用一个与门。
  这就是「知道 x、y 不会同来」这条领域知识换来的硬件。

原书特意说「你可能无须使用卡诺图也能猜到答案」——简单问题上直觉就够; 卡诺图的价值在变量一多、直觉失灵的时候⁵¹。另外注意一个细节: 无关项的用法在最大项侧同样成立(第 4.6 节动手实践里还有更「有趣」的用法预告)⁵²。

8. 4.6 用基本门拼出 XOR:组合运算的示范¶

把基本运算符组合成更常用的运算,本章收尾给一个示范:XOR(异或)—— 「两个操作数中有且仅有一个为 1 则结果为 1」⁴⁰。按最小项展开: 结果为 1 的组合是 (x=0, y=1) 和 (x=1, y=0),所以:

  x ⊕ y = (x ∧ ¬y) ∨ (¬x ∧ y) = m1 ∨ m2 = ∑(1, 2)

两个与门、两个非门、一个或门,电路图(图 4-21)就是把这行式子逐符号翻译⁴¹。 XOR 常见到有自己的门符号(图 4-20 的异或门,形状像或门多一条输入侧的横线)⁶²。

把 XOR 的真值表和已学的三个运算符并排,它的身份就清楚了:

  x y | x∧y | x∨y | x⊕y
  ----+-----+-----+-----
  0 0 |  0  |  0  |  0
  0 1 |  0  |  1  |  1
  1 0 |  0  |  1  |  1
  1 1 |  1  |  1  |  0    ← 只有这一行,XOR 和 OR 分家

  图说:XOR = OR 减去「两个都真」的情况;
  所以它也叫「不可兼或」(exclusive or)——排他的或。

XOR 还是第 6 章半加器的「和」(表 6-1 早已剧透:Sum = x ⊕ y), 第 16 章的逻辑指令(xor 指令)、第 3 章 OF 的定义(次末级进位 XOR 最终进位) 都会再用到它。可以说,从算术到电路到指令集,XOR 是布尔世界里出场率仅次于 AND/OR 的运算符。

一句小结收束 4.6 节:「当然,我们可以设计更多的布尔运算符。在接下来的几章中我们将继续研究,看看如何在硬件中实现这些运算符。一切都是通过简单的开关实现的」⁴²。

8.6 4.7 小结:一张工具清单¶

原书的小结把全章收成六件工具,对着查一遍自己带走没有⁵³:

#	工具	一句话
1	布尔运算符 AND/OR/NOT	逻辑版的乘、加、负;真值表定义一切
2	布尔代数法则	一套化简规则,一半像老代数、一半是布尔特产
3	简化布尔表达式	规范式 → 最小式;化简 = 省门
4	卡诺图	化简的图形版:邻接格圈组消元
5	格雷码	相邻差一位的编码,卡诺图排序的依据
6	组合基本运算符	XOR 由 AND/OR/NOT 拼出;更复杂的也可以

小结的最后一句话是预告:「第 5 章首先介绍基础电子学,这将为理解如何使用晶体管实现开关提供基础。接着,我们将学习如何使用晶体管开关来实现逻辑门。」⁶³ ——本章的式子,下一章就要变成真的开关。

8.5 给程序员的一节:布尔代数在代码里的影子¶

原书有一句放在 4.2 节、容易被滑过去的话:「知道如何简化布尔表达式对于硬件制造者和软件编写人员来说都是一件重要的工具」⁵⁹。把本章的工具映射到日常代码上:

本章的工具	代码里的对应物	化简的回报
结合律/交换律	`a && b && c` 的求值顺序可随意重排	可以「先算便宜的、能短路的那一侧」
幂等性 x∧x=x	`flag && flag` → `flag`	去重
补值 x∧¬x=0	`p && !p` → 恒假,死代码	直接被编译器消掉
分配律	`a && (b \|\| c)` ↔ `(a && b) \|\| (a && c)`	配合短路求值,选「最常触发的那侧」
德摩根定律	`!(a && b)` ↔ `!a \|\| !b`	把嵌套的否定摊平,否定算子越少越好读
无关单元格	前置条件保证的输入约束	`if (x >= 0) { ... sqrt(x) ... }` 里的检查可以省

最后一行值得展开:无关单元格的思想在软件里叫前置条件(precondition)—— 调用者保证某些组合不会出现,被调者就不必为它们写分支。卡诺图用 X 换门, 函数用契约换检查,是同一种经济(补充,不在书里,这是我们把书中思想向软件侧的映射, 「同构」二字是我们加的注解)。

还有一处直接对应:第 13 章会讲到,CPU 的条件跳转指令(jcc)查的正是第 3 章的 CF/OF/SF/ZF 这些标志——「if 语句最终变成一次对标志位的布尔判断」, 这本书从硬件到软件的链条在那里闭合。学了布尔代数,你读汇编里的 jge、jl、jz 就不再是背指令表,而是读一个布尔函数的值。

9. 作者的判断与证据¶

判断一:「化简对硬件制造者和软件编写人员都重要」。 证据是作者把话说到程序员脸上: 「即便你只对编程感兴趣,但你写的每一条编程语句最终都是通过完全由布尔代数系统描述的硬件来执行的」⁴³。化简是双向的:今天逻辑综合工具(把代码式描述自动转成门电路的软件)干的正是卡诺图干的事——你写 if (a && b) || (a && c), 综合器替你提取公因子(补充,不在书里,来自通用知识)。

判断二:两种规范形式都教,不偏心。 数字设计文献两种写法都在用, 教材只教最小项之和是常见缺陷;本书让进位函数两条路各走一遍, 还点破编号重合的必然性——这是把「对偶」教透了的写法。

判断三:卡诺图的手艺价值被如实交代。 书里没有假装代数法够用: 「代数操作可能并不总是那么明显」,图形化「可能更易于使用」²⁷; 也没有假装卡诺图万能——超过 4 个变量,格子翻倍到人眼不够用, 业界实际用程序化的化简算法(Quine-McCluskey 及启发式,补充,不在书里,来自通用知识)。

判断四(从 4.7 小结反推的):这一章的工具清单是刻意封闭的。 小结只列六件:布尔运算符(AND/OR/NOT)、代数法则、简化、卡诺图、格雷码、 XOR⁵³——没有引入任何额外工具(如 NAND 通用门、 espresso 算法)。这是「数学部分为硬件部分供弹药」的定位:够第 5、6 章用,就收笔。

判断五:「化简对软硬件都重要」的推广版。 4.2 节那句「每一条编程语句最终都是通过完全由布尔代数系统描述的硬件来执行的」, 其实是本章的题眼:它把布尔代数从「硬件工程师的工具」重新定义为「一切程序的最终执行介质」。这个定位解释了为什么一本「从程序员角度」的组成原理书肯花一整章讲卡诺图——作者认为你写的高级语言代码和门电路之间的翻译链, 是你作为程序员该知道的底牌。

10. 边界与局限¶

只化简到「门数与输入数」这一层。真正的电路优化还涉及时序(门有多快)、扇入扇出(一个门能带几个输入/几个门),第 5 章末和第 6 章会碰到边;
卡诺图止步于 4 变量(书内示例),实际数字设计靠算法化工具;
不教自动机/时序逻辑(那是第 7 章),本章全部函数都是「输出只取决于当前输入」的组合逻辑;
动手实践里的真值表证明(逐法则验证)是本章不可跳过的肌肉训练, 拆解给不了手感;
「最小」按的是字面量数,不是实际成本。 书里多次埋了伏笔(4.5.1 的「审慎地添加非门反而降低复杂性」、6.4 的「实际情况可能并非如此」): 真实硬件里,门的类型比门的数量更影响成本——有些门天生便宜 (第 5 章会看到 NAND/NOR 的晶体管实现比 AND/OR 省一半器件), 最小乘积和未必是最小成本解。本章的化简目标是教科书目标,不是工厂目标; 从式子到芯片之间还隔着「工艺映射」这一层(补充,不在书里,来自通用知识)。
学这一章最容易的弯路,是把布尔法则当「公式表」背。 每一条法则在真值表上都只是一行肉眼可见的事实(比如幂等性:x∨x 的两行输出跟 x 一模一样); 先看见事实,再记名字,顺序反过来就只剩死记了——这也是原书把所有证明都留成真值表练习的原因。

11. 可带走的¶

全章主线例子,一行走完: 进位条件先用英语列四种情况 → 写成规范和 ∑(3,5,6,7)(4 项×3 字面量)→ 幂等复制 + 分配 + 补值(或卡诺图三笔) → (x∧y)∨(cin∧x)∨(cin∧y)(3 项×2 字面量)→ 人话:「至少两个为 1 则进位」。 同一条式子走了四遍(英语、规范和、代数最简、卡诺图),每一步都等价, 每一步都更短——这就是「化简」二字的全部含义:语义不动,成本下降。

AND 像乘、OR 像加、NOT 像负——但布尔代数有自己的法则,别拿老代数硬套 (OR 对 AND 可分配、幂等 x∨x=x,都是老代数没有的);
真值表是这个领域的「实验」:任何等式,枚举所有组合逐行核对即证明;
德摩根定律:¬(x∧y) = ¬x∨¬y,¬(x∨y) = ¬x∧¬y——门电路变换的主力;
对偶原理:0↔1、AND↔OR 互换,等式仍成立;每条法则自带镜像;
布尔函数的思维是「哪些组合让结果为 1」,不是「代入求值」;
两种规范形式:最小项之和 ∑(盯住 1)、最大项之积 ∏(盯住 0);完整、唯一、啰嗦;
化简 = 省门 = 省钱省电;幂等性(复制一项再合并)是代数法的起手式;
卡诺图 = 同一套法则的图形化:邻接格只差一个变量,圈组消元,组可重叠可跨边;
格雷码(反射二进制码)让「相邻只差一位」在多变量下成立——卡诺图的排序依据;
无关单元格(X):永远不会出现的输入,圈不圈随你——领域知识能换门;
XOR = (x∧¬y)∨(¬x∧y),常见到有自己的门,半加器的「和」就是它;
每条法则都该亲手用真值表验过一遍——书里的动手实践不是作业,是把「真值表 = 这个领域的实验」从口号变成本能的唯一办法;
遇到卡诺图之外的现实问题(变量多、约束杂),记住本章教的「真值表 → 规范式 → 化简 → 核对」四步流程仍然成立,只是第 ③ 步交给计算机(补充,不在书里);
对偶原理省一半功夫:证了一条法则,它的对偶自动成立—— 看到「by duality」字样,就是有人替你省下了另一半证明;
学完之后回到自己的代码看一眼:你写过的每一个 if 和 &&, 都是本章某张真值表的人间形态。

12. 原文地图¶

本章地图覆盖第 4 章正文及 4.6、4.7 两个分节文件。

主题	原书章	原文位置
Boole 与 Shannon	第4 章布尔代数	`text/08-ch04.txt:8`(搜「George Boole」) · `text/08-ch04.txt:21`(搜「Shannon」)
位加法的真值表(进位/和)	第4 章布尔代数	`text/08-ch04.txt:40`(搜「真值表」)
三个运算符定义	第4 章布尔代数	`text/08-ch04.txt:53`(搜「AND 是一个双目运算符」) · `text/08-ch04.txt:61`(搜「OR 也是双目运算符」) · `text/08-ch04.txt:71`(搜「NOT 是一个单目运算符」)
字面量、项、优先级	第4 章布尔代数	`text/08-ch04.txt:89`(搜「字面量」) · `text/08-ch04.txt:99`(搜「优先级」)
每条语句都是布尔硬件执行	第4 章布尔代数	`text/08-ch04.txt:110`(搜「每一条编程语句」)
与初等代数相同的法则	第4 章布尔代数	`text/08-ch04.txt:122`(搜「结合律」) · `text/08-ch04.txt:163`(搜「x∧1=x」) · `text/08-ch04.txt:179`(搜「对合性」)
OR 对 AND 分配与 1+(2·3) 反例	第4 章布尔代数	`text/08-ch04.txt:194`(搜「x ∨ (y ∧ z)」) · `text/08-ch04.txt:199`(搜「1 + (2 · 3) = 7」)
补值、幂等性	第4 章布尔代数	`text/08-ch04.txt:230`(搜「x ∧ ¬x = 0」) · `text/08-ch04.txt:240`(搜「x∧x=x」)
德摩根定律与对偶原理	第4 章布尔代数	`text/08-ch04.txt:244`(搜「德摩根定律」) · `text/08-ch04.txt:250`(搜「对偶原理」)
进位函数登场	第4 章布尔代数	`text/08-ch04.txt:270`(搜「Cout」)
布尔函数「列出条件」思维	第4 章布尔代数	`text/08-ch04.txt:264`(搜「在内。导致进位为 1 的」)
最小项、规范和 ∑	第4 章布尔代数	`text/08-ch04.txt:317`(搜「最小项」) · `text/08-ch04.txt:338`(搜「∑ (3,5, 6, 7)」)
最大项、规范积 ∏	第4 章布尔代数	`text/08-ch04.txt:373`(搜「最大项」) · `text/08-ch04.txt:392`(搜「∏ (3,5, 6, 7)」)
规范形式完整唯一	第4 章布尔代数	`text/08-ch04.txt:416`(搜「完整且唯一」)
化简的硬件动机	第4 章布尔代数	`text/08-ch04.txt:420`(搜「每个 ∧ 运算符变成与门」) · `text/08-ch04.txt:288`(搜「成本和功耗」)
最小乘积和/最小和乘积定义	第4 章布尔代数	`text/08-ch04.txt:436`(搜「最小乘积和」) · `text/08-ch04.txt:450`(搜「最小和乘积」)
多解与硬件权衡	第4 章布尔代数	`text/08-ch04.txt:462`(搜「不止一个最小解」)
进位函数代数化简三步	第4 章布尔代数	`text/08-ch04.txt:478`(搜「复制两次」) · `text/08-ch04.txt:486`(搜「消去」) · `text/08-ch04.txt:501`(搜「至少有两个为 1」)
¬Cout 化简与门电路对比	第4 章布尔代数	`text/08-ch04.txt:522`(搜「如法炮制」) · `text/08-ch04.txt:531`(搜「不止一种」)
卡诺图历史与邻接规则	第4 章布尔代数	`text/08-ch04.txt:538`(搜「卡诺图」) · `text/08-ch04.txt:561`(搜「邻接规则」)
分组消元与可重叠	第4 章布尔代数	`text/08-ch04.txt:563`(搜「分组」) · `text/08-ch04.txt:588`(搜「多个组」)
格雷码构造与 7→8 只变一位	第4 章布尔代数	`text/08-ch04.txt:594`(搜「格雷码」) · `text/08-ch04.txt:641`(搜「7 和 8」)
3 变量卡诺图与进位三笔	第4 章布尔代数	`text/08-ch04.txt:652`(搜「00、01、11、10」) · `text/08-ch04.txt:667`(搜「3 个分组」)
最大项侧卡诺图、德摩根图形化	第4 章布尔代数	`text/08-ch04.txt:680`(搜「值为 0 的单元格」) · `text/08-ch04.txt:688`(搜「图形化展示」)
偶数函数大组 Even = ¬z	第4 章布尔代数	`text/08-ch04.txt:723`(搜「∑(0,2,4,6)」) · `text/08-ch04.txt:727`(搜「¬z」)
无关单元格	第4 章布尔代数	`text/08-ch04.txt:740`(搜「永远不会出现」) · `text/08-ch04.txt:753`(搜「无关单元格」)
XOR 定义与最小项实现	4.6 组合基本布尔运算符	`text/09-ch04-06-4-6.txt:11`(搜「有且仅有一个为 1」) · `text/09-ch04-06-4-6.txt:14`(搜「x ∧ ¬y」)
动手实践(逐法则真值表证明)	第4 章布尔代数	`text/08-ch04.txt:255`(搜「使用真值表证明」)
规范形式比较(表 4-8 全表)	第4 章布尔代数	`text/08-ch04.txt:400`(搜「所有最小项和最大项」)
m0~m7 对照表出自表 4-6	第4 章布尔代数	`text/08-ch04.txt:300`(搜「最小项」)
卡诺图由 Karnaugh 1953 年发明	第4 章布尔代数	`text/08-ch04.txt:540`(搜「1953」)
无关单元格圈组得 x ∨ y	第4 章布尔代数	`text/08-ch04.txt:759`(搜「F(x, y) = x ∨ y」)
「一切都是简单的开关」	4.6 组合基本布尔运算符	`text/09-ch04-06-4-6.txt:21`(搜「一切都是」)
最小项之和别名(析取范式)	第4 章布尔代数	`text/08-ch04.txt:313`(搜「析取范式」)
最大项之积别名(合取范式)	第4 章布尔代数	`text/08-ch04.txt:369`(搜「合取范式」)

出处:「第4 章布尔代数」第 8 段(text/08-ch04.txt:8,搜「George Boole」)与第 21 段(text/08-ch04.txt:21,搜「Shannon」)。原文:「布尔代数是由英国数学家 George Boole 在 19 世纪发展起来的」;「一位名叫 Claude Shannon 的研究生证明了电子开关能够实现所有的布尔代数表达式」「布尔代数成为了计算机的数学基础」。 ↩
出处:「第4 章布尔代数」第 53 段(text/08-ch04.txt:53,搜「AND 是一个双目运算符」)。原文:「当且仅当两个操作数均为 1 的时候,AND 的结果为 1;否则,结果为 0」;OR 见第 61 段(text/08-ch04.txt:61,搜「OR 也是双目运算符」):「至少有一个运算符为 1,OR 的结果才为 1」;NOT 见第 71 段(text/08-ch04.txt:71,搜「NOT 是一个单目运算符」)。 ↩
出处:「第4 章布尔代数」第 81 段(text/08-ch04.txt:81,搜「绝非偶然」)。原文:「AND 是相乘,而 OR 是相加,这绝非偶然。George Boole 在发展布尔代数时,一直在寻找一种方法,将数学严密性应用于逻辑并使用加法和乘法来处理逻辑语句。」 ↩
出处:「第4 章布尔代数」第 40 段(text/08-ch04.txt:40,搜「真值表」)。原书表 4-1 列出两个位加法的真值表(进位列与和列),第 4.1 节说明 AND/OR/NOT 用真值表定义。 ↩
出处:「第4 章布尔代数」第 89 段(text/08-ch04.txt:89,搜「字面量」)。原文:「字面量是表达式中的变量或变量之补(complement)的单个实例」;例中「共有 3 个变量(x、y、z)和 7 个字面量」。 ↩
出处:「第4 章布尔代数」第 96 段(text/08-ch04.txt:96,搜「优先级」)。原书表 4-2:NOT 高、AND 中、OR 低,「括号中的表达式首先被求值」。 ↩
出处:「第4 章布尔代数」第 122 段(text/08-ch04.txt:122,搜「结合律」)至第 185 段。自等值:「x∧1=x」「x∨0=x」;零一值:「x∧0=0」;对合性:「¬(¬x) = x」。 ↩
出处:「第4 章布尔代数」第 127 段(text/08-ch04.txt:127,搜「详尽的真值表」)。原文:「为了证明 AND 和 OR 的结合律,我们使用了一份详尽的真值表」;「这种方法适用于本节中介绍的所有法则,不过我只在这里展示结合律的真值表。」 ↩
出处:「第4 章布尔代数」第 199 段(text/08-ch04.txt:199,搜「1 + (2 · 3) = 7」)。原文:「在初等代数中,加法对乘法不满足分配律」,代入 x = 1、y = 2、z = 3:左边 1 + (2·3) = 7,右边 (1+2)·(1+3) = 12。 ↩
出处:「第4 章布尔代数」第 245 段(text/08-ch04.txt:245,搜「德摩根定律」)。原文:「¬(x ∧ y) = ¬x ∨ ¬y」「¬(x ∨ y) = ¬x ∧ ¬y」。 ↩
出处:「第4 章布尔代数」第 250 段(text/08-ch04.txt:250,搜「对偶原理」)。原文:「如果你用 1 代替每个 0,用 0 代替每个 1,用 OR 代替每个 AND,用 AND 代替每个 OR,等式仍然成立。」 ↩
出处:「第4 章布尔代数」第 264 段(text/08-ch04.txt:264,搜「在内。导致进位为 1 的」)。原文:「不妨将初等代数函数看作要求你代入变量值进行求值,而布尔函数是告诉你哪些变量值会导致函数结果为 1。」 ↩
出处:「第4 章布尔代数」第 270 段(text/08-ch04.txt:270,搜「Cout」)。原文:Cout(cin, x, y) = (¬cin ∧ x ∧ y) ∨ (cin ∧ ¬x ∧ y) ∨ (cin ∧ x ∧ ¬y) ∨ (cin ∧ x ∧ y)。 ↩
出处:「第4 章布尔代数」第 312 段(text/08-ch04.txt:312,搜「乘积之和」)。原文:「因为 OR 运算类似于加法,所以等式右边叫作乘积之和(sum of products),也称为析取范式(disjunctive normal form)。」 ↩
出处:「第4 章布尔代数」第 317 段(text/08-ch04.txt:317,搜「最小项」)与第 324 段(text/08-ch04.txt:324,搜「仅当」)。原文:「最小项(minterm)是只指定了其中一种排列组合的乘积项」;「对于每个最小项,只有一组变量值使其值为 1」。 ↩
出处:「第4 章布尔代数」第 368 段(text/08-ch04.txt:368,搜「和的乘积」)。原文:「因为 AND 运算类似于乘法,所以等式右边叫作和的乘积(product of sums),也称为合取范式(conjunctive normal form)。」 ↩
出处:「第4 章布尔代数」第 252 段(text/08-ch04.txt:252,搜「对偶性」)。原文:「如果比较相应的最小项和最大项,就会发现两者的对偶性:使用德摩根定律,通过对每个变量求补并互换 OR 和 AND 来相互生成。」 ↩
出处:「第4 章布尔代数」第 416 段(text/08-ch04.txt:416,搜「完整且唯一」)。原文:「规范形式给出了完整且唯一的函数声明,因为其考虑到了变量值的所有可能组合。」 ↩
出处:「第4 章布尔代数」第 420 段(text/08-ch04.txt:420,搜「每个 ∧ 运算符变成与门」)。原文:「用硬件实现布尔函数时,每个 ∧ 运算符变成与门,每个 ∨ 运算符变成或门,每个¬运算符变成非门。一般来说,硬件的复杂性与所使用的与门以及或门的数量有关(非门很简单,不会显著增加复杂性)。」 ↩
出处:「第4 章布尔代数」第 288 段(text/08-ch04.txt:288,搜「成本和功耗」)。原文:「越简单的硬件使用的组件越少,从而节省成本、空间以及功耗。对于手持和可穿戴设备,这 3 个因素尤为重要。」 ↩
出处:「第4 章布尔代数」第 436 段(text/08-ch04.txt:436,搜「最小乘积和」)。原文:「最小乘积和(minimal sum of products),这是一个乘积和表达式,其中所有其他数学等价的乘积和表达式具有至少同样多的乘积项,并且那些乘积项数量相同的表达式具有至少同样多的字面量。」 ↩
出处:「第4 章布尔代数」第 462 段(text/08-ch04.txt:462,搜「不止一个最小解」)。原文:「一个问题可能有不止一个最小解。优秀的硬件设计通常涉及找出若干最小解的解决方案,然后在可用的硬件环境中评估每种解决方案。」 ↩
出处:「第4 章布尔代数」第 478 段(text/08-ch04.txt:478,搜「复制两次」)至第 489 段(text/08-ch04.txt:489,搜「( x ∧ y ) ∨」)。原文:「使用幂等法则将第 4 项复制两次」,经分配律、补值法则、自等值化简得 = ( x ∧ y ) ∨ ( cin ∧ x ) ∨ ( cin ∧ y )。 ↩
出处:「第4 章布尔代数」第 501 段(text/08-ch04.txt:501,搜「至少有两个为 1」)。原文:「最小化形式的表述要简单得多:如果 cin、x 和 y 中至少有两个为 1,则进位为 1。」 ↩
出处:「第4 章布尔代数」第 528 段(text/08-ch04.txt:528,搜「德摩根定律」)。原文:「将图 4-6 与图 4-5 相比较,你可以从图上看出德摩根定律:OR 变成了以补值作为输入的 AND。」 ↩
出处:「第4 章布尔代数」第 531 段(text/08-ch04.txt:531,搜「不止一种」)。原文:「这里需要理解的重要一点是,解决问题的方法不止一种。硬件工程师的工作之一是根据成本、元件的可用性等因素来决定哪种解决方案是最好的。」 ↩
出处:「第4 章布尔代数」第 116 段(text/08-ch04.txt:116,搜「代数的一些法则并不陌生，」)与第 540 段(text/08-ch04.txt:540,搜「1953」)。原文:「用于最小化布尔函数的代数操作可能并不总是那么明显」;「1953 年,贝尔实验室的电信工程师 Maurice Karnaugh 发明了卡诺图」。 ↩↩
出处:「第4 章布尔代数」第 563 段(text/08-ch04.txt:563,搜「分组」)。原文:「需要使用卡诺图来进行简化,需要将图中相邻为 1 的两个单元格分组。然后消除二者之间不同的变量并合并两个乘积项。」「被分组的单元格数量必须是 2 的倍数,而且你只能划分相邻的单元格。」 ↩
出处:「第4 章布尔代数」第 557 段(text/08-ch04.txt:557,搜「( ¬x ∨ x ) ∧ y」)。原文演示:( ¬x ∧ y ) ∨ ( x ∧ y ) = ( ¬x ∨ x ) ∧ y = y。 ↩
出处:「第4 章布尔代数」第 588 段(text/08-ch04.txt:588,搜「多个组」)。原文:「你可以将一个单元格纳入多个组中,就像在代数操作中使用幂等性法则添加单元格副本一样。」 ↩
出处:「第4 章布尔代数」第 594 段(text/08-ch04.txt:594,搜「格雷码」)。原文:「1943 年,Frank Gray 推出了一种代码,即格雷码(Gray code),其中相邻两数之间只相差一位。」 ↩
出处:「第4 章布尔代数」第 604 段(text/08-ch04.txt:604,搜「镜像」)与第 618 段(text/08-ch04.txt:618,搜「反射二进制码」)。原文:「要添加一位,先书写现有位模式的镜像」;「这就是有时候将格雷码称为反射二进制码(Reflected Binary Code,RBC)的原因。」 ↩
出处:「第4 章布尔代数」第 641 段(text/08-ch04.txt:641,搜「7 和 8」)。原文:「7 和 8 对应的二进制码分别是 0111 和 1000;当十进制值仅递增 1 时,所有位都会发生变化。但是比较 7 和 8 对应的格雷码 0100 和 1100,只有 1 位有变化」;回绕处只变一位见第 644 段(text/08-ch04.txt:644,搜「回绕」)。 ↩
出处:「第4 章布尔代数」第 652 段(text/08-ch04.txt:652,搜「00、01、11、10」)。原文:「3 变量卡诺图顶部的位模式依次为 00、01、11、10,这是表 4-9 中的格雷码的顺序,并非 00、01、10、11。」 ↩↩
出处:「第4 章布尔代数」第 667 段(text/08-ch04.txt:667,搜「3 个分组」)与第 671 段(text/08-ch04.txt:671,搜「同样的等式」)。原文:「如前所述,组可以重叠,于是得到了图 4-13 所示的 3 个分组」「使用图 4-13 中的 3 个分组,我们得到了与代数方法同样的等式」。 ↩
出处:「第4 章布尔代数」第 688 段(text/08-ch04.txt:688,搜「图形化展示」)。原文:「如果你比较图 4-13 和图 4-15,可以看到德摩根定律的图形化展示……我们交换 0 和 1,交换 AND 和 OR,从一个卡诺图得到另一个卡诺图。」 ↩
出处:「第4 章布尔代数」第 723 段(text/08-ch04.txt:723,搜「∑(0,2,4,6)」)与第 727 段(text/08-ch04.txt:727,搜「¬z」)。原文:Even(x, y, z) = ∑(0,2,4,6);「卡诺图表明 x 和 y 的值是多少并不重要,重要的是 z = 0。」 ↩
出处:「第4 章布尔代数」第 740 段(text/08-ch04.txt:740,搜「永远不会出现」)与第 753 段(text/08-ch04.txt:753,搜「无关单元格」)。原文:「如果你清楚哪些值的组合永远不会出现,那么代表这些组合的最小项(或最大项)就无关紧要了」;「X 代表一个无关单元格——我们不关心这个单元格是否与其他单元格组合在一起。」 ↩
出处:「第4 章布尔代数」第 755 段(text/08-ch04.txt:755,搜「无关”单元格」)与第 759 段(text/08-ch04.txt:759,搜「x ∨ y」)。原文:「由于表示最小项(x ∧ y)的是一个“无关”单元格,我们可以将其包括或不包括在最小化分组中」;「由图 4-19 中的卡诺图得到解决方案:F(x, y) = x ∨ y」。 ↩
出处:「4.6 组合基本布尔运算符」第 11 段(text/09-ch04-06-4-6.txt:11,搜「有且仅有一个为 1」)。原文:「XOR 是一种双目运算符。如果两个操作数中有且仅有一个为 1,则结果为 1;否则,结果为 0。」 ↩
出处:「4.6 组合基本布尔运算符」第 14 段(text/09-ch04-06-4-6.txt:14,搜「x ∧ ¬y」)。原文:x∨_ y = (x ∧ ¬y) ∨ (¬x ∧ y),「XOR 运算符可以用两个与门、两个非门和一个或门来实现」。 ↩
出处:「4.6 组合基本布尔运算符」第 21 段(text/09-ch04-06-4-6.txt:21,搜「一切都是」)。原文:「当然,我们可以设计更多的布尔运算符。在接下来的几章中我们将继续研究,看看如何在硬件中实现这些运算符。一切都是通过简单的开关实现的。」 ↩
出处:「第4 章布尔代数」第 110 段(text/08-ch04.txt:110,搜「每一条编程语句」)。原文:「即便你只对编程感兴趣,但你写的每一条编程语句最终都是通过完全由布尔代数系统描述的硬件来执行的。编程语言倾向于通过抽象来隐藏大量底层细节,但是仍然使用布尔表达式来实现编程逻辑。」 ↩
出处:「第4 章布尔代数」第 404 段(text/08-ch04.txt:404,搜「规范项」)。原书表 4-8 展示 3 变量问题的所有最小项和最大项,「如果比较相应的最小项和最大项,就会发现两者的对偶性」。 ↩
出处:「第4 章布尔代数」第 703 段(text/08-ch04.txt:703,搜「最小数量」)。原文:「这种比较直观地展示了最小项如何指定卡诺图中 1 的最小数量,以及最大项如何指定 1 的最大数量。」 ↩
出处:「第4 章布尔代数」第 549 段(text/08-ch04.txt:549,搜「x ∧ ¬y」)。原书以 F(x, y) = (x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ y) 为例,从图 4-7 的格子映射讲到图 4-10 的分组,得到 F(x, y) = x ∨ y(第 586 段,text/08-ch04.txt:586,搜「x ∨ y」)。 ↩
出处:「第4 章布尔代数」第 557 段(text/08-ch04.txt:557,搜「( ¬x ∨ x ) ∧ y」)。原文:( ¬x ∧ y ) ∨ ( x ∧ y ) = ( ¬x ∨ x ) ∧ y = y,「运用分配律和补值法则」。 ↩
出处:「第4 章布尔代数」第 587 段(text/08-ch04.txt:587,搜「幂等性法则复制」)。原文:「包含在两个分组中的单元格(x ∧ y)是我们先前在代数解决方法中使用幂等性法则复制而来的项。」 ↩
出处:「第4 章布尔代数」第 725 段(text/08-ch04.txt:725,搜「相邻的边」)。原文:「图 4-17 显示了卡诺图上的这些最小项,4 项为一组。这 4 项能被分组在一起是因为它们都有相邻的边」;跨边缘分组规则见第 566 段(text/08-ch04.txt:566,搜「从一边到另一边」)。 ↩
出处:「第4 章布尔代数」第 731 段(text/08-ch04.txt:731,搜「4 变量卡诺图」)。原文:「图 4-18 展示了最小项的 4 变量卡诺图。变量 y 和 z 位于水平轴,w 和 x 位于垂直轴。」 ↩
出处:「第4 章布尔代数」第 761 段(text/08-ch04.txt:761,搜「猜到答案」)。原文:「你可能无须使用卡诺图也能猜到答案。」 ↩
出处:「第4 章布尔代数」第 1 段(text/08-ch04.txt:1,搜「42 布尔代数」)。原文:「由图 4-19 中的卡诺图得到解决方案:F(x, y) = x ∨ y。这是一个简单的或门。」并在动手实践预告无关单元格在第 7 章末尾的更多用法。 ↩
出处:「4.7 小结」第 9 段(text/10-ch04-07-4-7.txt:9,搜「布尔运算符」)。原书 4.7 小结列出的条目:布尔运算符、布尔代数法则、简化布尔代数表达式、卡诺图、格雷码、组合基本的布尔运算符(XOR)。 ↩↩
出处:「第4 章布尔代数」第 429 段(text/08-ch04.txt:429,搜「真值表」)。原文:「要将问题转化为规范形式,请创建一个真值表,列出问题中变量的所有可能组合。从真值表中,很容易列出定义函数的最小项或最大项。」 ↩
出处:「第4 章布尔代数」第 478 段(text/08-ch04.txt:478,搜「复制两次」)与第 513 段(text/08-ch04.txt:513,搜「一般形式」)。原文:「我们将采用与最小项之和相同的方法,先将最后一项复制两次」;「OR 对 AND 的分配律具有以下一般形式:(X ∨ Y) ∧ (X ∨ Z) = X ∨ (Y ∧ Z)」。 ↩
出处:「第4 章布尔代数」第 522 段(text/08-ch04.txt:522,搜「如法炮制」)。原文:「对另外两个分组如法炮制,我们可以得到:¬Cout(cin, x, y) = (¬x ∨ ¬y ) ∧ ( ¬cin ∨ ¬x ) ∧ ( ¬cin ∨ ¬y )」;「这个电路会生成进位的补。我们需要对输出¬Cout(cin, x, y)求补来得到进位值。」 ↩
出处:「第4 章布尔代数」第 298 段(text/08-ch04.txt:298,搜「使进位为 1 的条件」)。原书表 4-6 列出 8 个最小项(m0~m7)对应的四个乘积项取值与 Cout 值。 ↩
出处:「第4 章布尔代数」第 317 段(text/08-ch04.txt:317,搜「mi」)。原文:「逻辑设计人员通常不会写出函数中的所有字面量,而是使用符号 mi 来指定第 i 个最小项,如果将字面量的值按顺序排列并将其视为二进制数,i 代表的就是这个整数。」 ↩
出处:「第4 章布尔代数」第 109 段(text/08-ch04.txt:109,搜「重要的工具」)。原文:「知道如何简化布尔表达式对于硬件制造者和软件编写人员来说都是一件重要的工具。」 ↩
出处:「第4 章布尔代数」第 691 段(text/08-ch04.txt:691,搜「对偶性」)。原文:「为了进一步强调最小项和最大项的对偶性,比较图 4-16(a)和图 4-16(b)」;图 4-16(a)为 F(x, y, z) = ¬x ∧ ¬y ∧ ¬z,图 4-16(b)为 ¬F(x, y, z) = x ∨ y ∨ z。 ↩
出处:「第4 章布尔代数」第 253 段(text/08-ch04.txt:253,搜「证明德摩根定律」)。原书动手实践第 2 题:「证明德摩根定律。」(书中未附证明,真值表证明是我们按本节方法补走的示范。) ↩
出处:「4.6 组合基本布尔运算符」第 9 段(text/09-ch04-06-4-6.txt:9,搜「专门电路符号」)。原文:「因为该运算符十分常见,所以有专门电路符号。」 ↩
出处:「4.7 小结」第 17 段(text/10-ch04-07-4-7.txt:17,搜「第 5 章」)。原文:「第 5 章首先介绍基础电子学,这将为理解如何使用晶体管实现开关提供基础。接着,我们将学习如何使用晶体管开关来实现逻辑门。」 ↩
出处:「第4 章布尔代数」第 244 段(text/08-ch04.txt:244,搜「德摩根定律」)。原文:「让我们利用德摩根定律,对指定进位的等式两边求补」并给出 ¬Cout 的四项展开式。 ↩
出处:「第4 章布尔代数」第 353 段(text/08-ch04.txt:353,搜「使进位的补数为 0 的条件」)。原书表 4-7 列出使 ¬Cout 为 0 的最大项 M3、M5、M6、M7。 ↩
出处:「第4 章布尔代数」第 395 段(text/08-ch04.txt:395,搜「等价的」)。原文:「这表明使用最小项或最大项是等价的。具体使用哪一个取决于多种因素,如实现函数的可用硬件组件以及个人偏好。」 ↩
出处:「第4 章布尔代数」第 259 段(text/08-ch04.txt:259,搜「计算机的功能基于布尔逻辑」)。原文:「计算机的功能基于布尔逻辑,这意味着计算机的各种操作都可以由布尔函数指定。」 ↩