跳到主要内容

卡诺图与三值逻辑 — 把复杂规则压简,以及第三个值从哪来

这一章讲三件事: 一堆缠在一起的条件怎么压成一句人话; 为什么真假两个值在真实的程序里不够用; 以及 && 为什么不能随手交换左右两边。

它在全书链条里的位置: 第 02 到 04 章教的是「怎么把条件说准」。 这一章教的是反方向:说准之后,怎么把它说短。 这也是原书逻辑那一章的收尾,再往后就换工具了(第 06 章开始讲余数)。 需要的基础: 第 03 章的真值表、第 04 章的德摩根定律。

1. 先看现象:三条规则,眼睛跟不上​

原书设了一个小游戏。屏幕上有一绿一黄两个灯泡,不停地闪。 符合下面三种情况之一,就要马上按按钮1:

  【二灯游戏的规则】
  ⓐ 绿灯灭,黄灯亮
  ⓑ 绿灯、黄灯都灭
  ⓒ 绿灯、黄灯都亮

  图说:全章的主走查就是其中一种灯况 —— 绿灯灭、黄灯亮(命中 ⓐ)。
       我们要看着它,从「三条规则」一路走到「一句人话」。

你试着照这三条打一局看看。 眼睛要先看绿灯、再看黄灯, 在脑子里对三条规则各查一遍——手一定跟不上。

但这三条规则其实可以压成一句话,而且短到不用想。 这一节到第 4 节就是把它压出来的过程。

2. 第一步:先翻成式子(翻完反而更长了)​

这一节回答:整理规则该从哪儿下手。

原书给的第一条动作是:不要光在脑子里想,先写成式子2。设两个命题:

  • A = 绿灯亮
  • B = 黄灯亮

于是三条规则各自变成:

规则写成式子念出来
ⓐ(¬A) ∧ B绿灯不亮,并且黄灯亮
ⓑ(¬A) ∧ (¬B)绿灯不亮,并且黄灯不亮
ⓒA ∧ B绿灯亮,并且黄灯亮

三条满足任意一条就按,所以把它们用「或者」串起来3:

  ((¬A) ∧ B) ∨ ((¬A) ∧ (¬B)) ∨ (A ∧ B)
      ⓐ            ⓑ              ⓒ

走查第一步:绿灯灭、黄灯亮——A 为假、B 为真。代进去: ⓐ 是「真 ∧ 真」= 真,于是整个式子为真,该按。

但原书紧接着自己吐槽了一句:这完全没有简化4。 一边盯着灯闪、一边判断这么长一串的真假,根本做不到。 式子写出来了,可它比原来的三条规则还难用。

3. 第二步:把所有组合摆成一张二维表,该按的打钩​

这一节回答:压简这件事,有没有不靠灵感的办法。

有,而且是画图。把所有真假组合摆成一张二维表,这张图叫卡诺图5。

两个命题、四种组合,所以是 2 × 2 的四格。照三条规则,在该按按钮的格子里打钩6:

                    B(黄灯亮)
                 假        真
              ┌───────┬───────┐
         假   │  ✓ ⓑ  │  ✓ ⓐ  │   ← A 为假(绿灯灭)这一整行都打钩
  A(绿灯亮)  ├───────┼───────┤
         真   │       │  ✓ ⓒ  │
              └───────┴───────┘

  图说:四个格子就是全部四种灯况,一个不多一个不少。
       ✓ 表示这种灯况要按按钮。三条规则正好占了三格,
       右上角那一格(绿灯灭、黄灯亮)就是我们的主走查。

走查第二步: 我们那种灯况(绿灯灭 = A 假、黄灯亮 = B 真)落在右上角那一格, 格子里有钩——该按,和第 2 节算出来的结果一致。

这张表和第 03 章的真值表是同一批信息,只是摆法不同: 真值表把四种组合竖着排成四行,卡诺图把它们摆成田字格。 摆成田字格是为了下一步——相邻的格子能被圈起来。

4. 第三步:圈框,每个框对应一个短式子​

这一节是压简真正发生的地方。

规则只有一条:把相邻的打钩格,用尽可能大的框圈起来7。 框的大小只能是 1×1、1×2、2×2、1×4 这种规整的块,而且几个框可以重叠8。

                    B(黄灯亮)
                 假        真
              ┌───────┬───────┐
         假   │┌ ✓ ── │ ─ ✓ ┐ │  ← 横框:整行都在 A 为假的地盘 → ¬A
  A(绿灯亮)  ├└──────┼───│───┤
         真   │       │ │ ✓ │ │  ← 竖框:整列都在 B 为真的地盘 → B
              └───────┴─└───┘─┘

  图说:两个框,一横一竖,重叠在右上角那一格。
       横框对应「绿灯灭」,竖框对应「黄灯亮」。

读框的办法很机械:看这个框整个落在谁的地盘里9:

  • 横着那个框:两格都在 A 为假的一行 → 它就是 ¬A(绿灯灭);
  • 竖着那个框:两格都在 B 为真的一列 → 它就是 B(黄灯亮)。

所有打钩的格子被这两个框盖满了,所以整条规则就是这两个框的「或者」:

  ((¬A) ∧ B) ∨ ((¬A) ∧ (¬B)) ∨ (A ∧ B)   ==   (¬A) ∨ B
  ────────────────────────────────────         ─────────
      压之前:A 出现 3 次、B 出现 3 次         压之后:各 1 次

这个「3 次变 1 次」你可以自己数一遍——左边三个括号里各有一个 A 和一个 B, 右边一共只剩一个 A、一个 B。

走查第三步: 把绿灯灭、黄灯亮代进右边——¬A 为真,整句为真,该按。 三步下来,答案一次都没变,但规则从三条变成了一句话: 「绿灯灭,或者黄灯亮,就按」10。

这就是这一章前半部分的全部内容。 原书的评价是:通过画卡诺图, 我们得知那条长式子和 (¬A) ∨ B 是相等的——卡诺图把逻辑表达式简化了11。

5. 加一个灯:8 个格子,而且分界要错位​

这一节回答:两个灯是特例吗。

不是,三个灯照样能压。 规则换成四条12:

  【三灯游戏的规则】
  ⓐ 绿、黄、红都灭      ⓑ 黄灯灭,红灯亮
  ⓒ 绿灯灭,黄灯亮      ⓓ 绿、黄、红都亮

三个命题(A 绿、B 黄、C 红)一共 2 × 2 × 2 = 8 种组合,所以是 8 个格子13。

这里有一个不画一遍就想不到的细节:B 和 C 的分界必须错开。 原书特意提醒了这一点——正是这个「错位」,才让 8 个格子装得下所有情况, 并且让相邻的格子真的只差一个灯14。

圈完框之后,结果是 (¬A) ∨ C:绿灯灭,或者红灯亮,就按15。

最值得看的是它少了什么:式子里根本没有 B。 也就是说,玩三灯游戏时黄灯压根不用看16。 四条规则里明明每一条都提到黄灯,压完之后它消失了—— 这种「某个条件其实无关」的发现,靠瞪眼看规则是看不出来的。

原书说,卡诺图通常就用在简化逻辑表达式和设计逻辑电路上17。

6. 换个场子:程序里还有第三个值​

这一节回答:前面所有讨论都建立在「非真即假」上,而真实的程序不是这样。

逻辑里只有真和假两个值,命题非真即假18。但程序不是。 原书列了一串:程序会因为出错而退出、会崩溃、会陷入死循环、会抛出异常—— 这些时候,你既拿不到真,也拿不到假19。

所以在真和假之外,又加了第三个值,叫 undefined(未定义)20:

值意思
true真
false假
undefined未定义——这里根本没算出结果

三个值的逻辑,就叫三值逻辑。

先看 &&(带条件的逻辑与)。 三个值就是 3 × 3 = 9 行表, 但结论只有三条,而且非常好记21:

  • A 为真时,A && B 的结果就是 B 的结果;
  • A 为假时,A && B 恒为假;
  • A 为 undefined 时,A && B 恒为 undefined。

原书给了一把钥匙,一下就把这九行读通了:把 undefined 读成「计算机在这里什么都没做」22:

  • A 为真 → 还得看 B,B 是什么结果就是什么结果;
  • A 为假 → 不用看 B 了,直接是假;
  • A 为 undefined → 机器压根没往下走,当然也没看 B,结果还是 undefined。

注意中间那一条:A 为假的时候,B 根本不会被计算。 这就是为什么它叫「带条件的逻辑与」——看不看右边,取决于左边23。 它和下面这段嵌套的 if 是同一件事24:

if (A && B) { … }
        等价于
if (A) {
    if (B) { … }
}

于是有一条要记住的结论:A && B 不等于 B && A,交换律不成立25。 因为它俩执行的东西不一样——前者可能不跑 B,后者可能不跑 A。

||(带条件的逻辑或)是同一件事的镜像,三行就说完26: A 为真时不看右边,直接为真;A 为假时结果就是 B; A 为 undefined 时恒为 undefined。它等价的不是嵌套 if,而是一段 if-else27:

if (A || B) { … }
        等价于
if (A) { … } else { if (B) { … } }

7. 这条性质的实际用法:拿左边当闸门​

这一节回答:「看不看右边取决于左边」这件事,平时怎么用。

原书给了一行代码,它是这条性质最实际的用法28:

if (check() && execute()) {
    …
}

这里 check() 干的不是「凑一个条件」,是当闸门。 如果 check() 返回假,execute() 一次都不会跑29。

走查(另起一处): 假设 check() 检查磁盘还有没有空间,返回假; 那么 execute()(往磁盘写文件)根本不会被执行,整个条件直接为假。 把两个函数的顺序调过来写成 execute() && check(),文件已经写坏了,再检查也晚了。

这就是为什么第 6 节那句「交换律不成立」不是理论洁癖: && 的左右两边有时候是有先后的,换个位置就是另一个程序。

8. 多了一个值,第 04 章那条定律还成立吗​

这一节回答一个必须回答的问题:地基换了,上面的东西塌不塌。

第 04 章的德摩根定律是在真假两个值上验的——九行表里现在多了 undefined, 那条定律还成立吗?

成立。 原书把 (!A) || (!B) = !(A && B) 和 (!A) && (!B) = !(A || B) 两条式子在九行表上逐行核了一遍,结论是德摩根定律在三值逻辑里确实也成立30。

注意这里用的还是第 03 章那套办法:情况有限,就逐行核对。 两个值是 4 行,三个值是 9 行——列得完,就验得了。

但也别把三值逻辑想得太完整。 原书顺手交了个底: 如果要把涉及 true / false / undefined 的运算符全列出来,一共有 39 个; 这一章只讲了编程里最常用的三个(&&、||、!)31。

9. 作者的判断、我们的判断,以及这一章的边界​

说法书里给了什么
卡诺图能简化逻辑表达式给了完整走查:二灯从「A、B 各出现三次」压到「各出现一次」,三灯直接消掉一个条件
三值逻辑的三条结论给了九行表 + 一把钥匙(把 undefined 读成「什么都没做」)
&& 不满足交换律给了理由(是否计算右边取决于左边),并给了 check() && execute() 这个用法
德摩根定律在三值逻辑里成立给了逐行核对,不是断言
三值逻辑一共 39 个运算符只给了这个数,没有列出来,也没有说怎么数出来的

判断(我们的,不是书里的):卡诺图今天的用处,比原书写的时候小了一截。 它最初是给硬件设计用的(手工化简逻辑电路), 而今天写业务代码的人很少需要把一堆条件压到最短—— 可读性往往比短更重要,压完的 (¬A) ∨ B 有时反而丢掉了业务含义。 真正长期有用的是它带来的那两个发现: 「这几条规则其实是同一件事」和「这个条件根本无关」。 如果错,会错在: 如果一个人写的是硬件驱动、通信格式转换或者规则引擎那类代码, 条件组合密集,那么手工化简仍然很值钱。判据是: 他手上那段判断有没有超过三个互相独立的条件。

这一章的边界:

  • 卡诺图只演示到三个命题;四个以上原书没讲,而格子数是翻倍涨的(第 13 章讲这件事);
  • 「相邻」这个词原书没有严格定义——为什么错位排列之后相邻格只差一个条件,书里让你自己看图;
  • 三值逻辑的 39 个运算符没有列出来,也没说这 39 是怎么数的;
  • 没有讲现实语言里 null、NaN、空值传播这些真实的第三值, 原书的 undefined 是一个理想化的模型;
  • 原书这一章到此结束,后面换成余数(第 06 章)。

10. 可带走的​

  1. 整理复杂规则的第一步是写成式子——哪怕写完更长,也比在脑子里绕强;
  2. 卡诺图就是把所有真假组合摆成田字格,该成立的格子打钩;
  3. 压简的动作只有一个:把相邻的钩用尽量大的框圈起来,框可以重叠;
  4. 每个框对应一个短式子:整行落在 A 为假的地盘,它就是 ¬A;
  5. 三条规则可以塌成一句话:「绿灯灭,或者黄灯亮」——式子里 A、B 各出现三次,压完各只剩一次;
  6. 压简还能发现「某个条件根本无关」:三灯游戏压完之后,黄灯根本不用看;
  7. 程序会崩、会卡死,所以真假之外还有第三个值 undefined;
  8. && 看不看右边,取决于左边:A 为假就不看 B;它等价于一段嵌套的 if; || 是它的镜像(A 为真就不看 B),等价于一段 if-else;
  9. 所以 A && B 不等于 B && A——check() && execute() 是拿左边当闸门,顺序换了就出事;
  10. 德摩根定律在三值逻辑里照样成立,这是逐行核对出来的,不是想当然。

11. 原文地图​

主题原书章原文位置
二灯游戏的三条规则第2章　逻辑text/07-ch02.txt:856(搜「必须遵守以下规则迅速按下游戏机按钮」) · :861(搜「绿灯灭，黄灯亮」)
先翻成逻辑表达式第2章　逻辑text/07-ch02.txt:872(搜「更重要的法则是必须写出逻辑表达式帮助思考」) · :890(搜「这完全没有简化」)
卡诺图的定义与画法第2章　逻辑text/07-ch02.txt:895(搜「是将所有命题的真假组合以二维表的形式表示的图」) · :913(搜「用框将相邻的打钩格围起形成组合框」)
压简结果 (¬A) ∨ B第2章　逻辑text/07-ch02.txt:949(搜「横向的组合框」) · :956(搜「在玩二灯游戏时观察灯泡亮灭」) · :958(搜「我们利用卡诺图简化了逻辑表达式」)
三灯游戏与错位第2章　逻辑text/07-ch02.txt:967(搜「绿灯、黄灯、红灯都灭」) · :999(搜「注意一下 B 和 C 的 false/true 分界是错位的」) · :1027(搜「不需要看黄灯」)
第三个值 undefined第2章　逻辑text/07-ch02.txt:1034(搜「陷入无限循环、抛出异常」) · :1036(搜「叫 undefined 的值」)
&& 的三条结论与那把钥匙第2章　逻辑text/07-ch02.txt:1064(搜「不包含 undefined 的行」) · :1069(搜「这里计算机不进行任何处理」) · :1117(搜「所谓的交换法则不成立」)
check() && execute()第2章　逻辑text/07-ch02.txt:1120(搜「check() && execute()」) · :1124(搜「就不执行 execute() 了」)
|| 与 if-else第2章　逻辑text/07-ch02.txt:1158(搜「A 为 true 时」) · :1164(搜「和下面的程序是一样的」)
三值逻辑里的德摩根定律、39 个运算符第2章　逻辑text/07-ch02.txt:1226(搜「德摩根定律在三值逻辑中确实也成立」) · :1238(搜「数量将达到 39 个」)

Footnotes​

  1. 出处:「第2章　逻辑——真与假的二元世界」第 856 段(text/07-ch02.txt:856,搜「必须遵守以下规则迅速按下游戏机按钮」)与第 861 段(text/07-ch02.txt:861,搜「绿灯灭，黄灯亮」)。原书的原话是「下述规则较为复杂,你能将它整理得简单一些吗?」——这是一道留给读者的题,不是讲解。 ↩

  2. 出处:「第2章　逻辑——真与假的二元世界」第 872 段(text/07-ch02.txt:872,搜「更重要的法则是必须写出逻辑表达式帮助思考」)。 ↩

  3. 出处:「第2章　逻辑——真与假的二元世界」第 878 段(text/07-ch02.txt:878,搜「需要按下按钮的情况就是下述」)与第 887 段(text/07-ch02.txt:887,搜「((¬A) ∧ B)」)。 ↩

  4. 出处:「第2章　逻辑——真与假的二元世界」第 890 段(text/07-ch02.txt:890,搜「这完全没有简化」)。原文接着说:要一边观察灯的亮灭、一边判断这种逻辑表达式的真假,实在难以做到。 ↩

  5. 出处:「第2章　逻辑——真与假的二元世界」第 895 段(text/07-ch02.txt:895,搜「是将所有命题的真假组合以二维表的形式表示的图」)。原书给的英文是 Karnaugh map。 ↩

  6. 出处:「第2章　逻辑——真与假的二元世界」第 897 段(text/07-ch02.txt:897,搜「根据规则在应」)。原书的图 2-28 就是这张打了钩的四格图。 ↩

  7. 出处:「第2章　逻辑——真与假的二元世界」第 913 段(text/07-ch02.txt:913,搜「用框将相邻的打钩格围起形成组合框」)。原文列了允许的框形状:1×1、1×2、1×4 或 2×2、4×4。 ↩

  8. 出处:「第2章　逻辑——真与假的二元世界」第 920 段(text/07-ch02.txt:920,搜「组合框相互重叠也没关系」)。 ↩

  9. 出处:「第2章　逻辑——真与假的二元世界」第 949 段(text/07-ch02.txt:949,搜「横向的组合框」)。原文两条并列:横向的框是 A 为 false 的区域,用 ¬A 表示;纵向的框是 B 为 true 的区域,用 B 表示。 ↩

  10. 出处:「第2章　逻辑——真与假的二元世界」第 956 段(text/07-ch02.txt:956,搜「在玩二灯游戏时观察灯泡亮灭」)。原文的原话是:当「绿灯灭(¬A)」或者「黄灯亮(B)」的时候就可以按下按钮。 ↩

  11. 出处:「第2章　逻辑——真与假的二元世界」第 959 段(text/07-ch02.txt:959,搜「我们利用卡诺图简化了逻辑表达式」)。 ↩

  12. 出处:「第2章　逻辑——真与假的二元世界」第 967 段(text/07-ch02.txt:967,搜「绿灯、黄灯、红灯都灭」)。四条规则在原文里是连着的四行。 ↩

  13. 出处:「第2章　逻辑——真与假的二元世界」第 980 段(text/07-ch02.txt:980,搜「因此表的网格数变为」)。 ↩

  14. 出处:「第2章　逻辑——真与假的二元世界」第 999 段(text/07-ch02.txt:999,搜「注意一下 B 和 C 的 false/true 分界是错位的」)。原文的原话是:正是这个「错位」,使得用 8 个网格就能表示所有情况。为什么错位之后相邻格只差一个条件,书里没有展开。 ↩

  15. 出处:「第2章　逻辑——真与假的二元世界」第 1005 段(text/07-ch02.txt:1005,搜「正中间的组合框」)与第 1025 段(text/07-ch02.txt:1025,搜「最后得到的逻辑表达式为」)。 ↩

  16. 出处:「第2章　逻辑——真与假的二元世界」第 1027 段(text/07-ch02.txt:1027,搜「不需要看黄灯」)。原文的原话是:在这个逻辑表达式中没有出现 B,由此我们可知在判断是否按下按钮时,不需要看黄灯。 ↩

  17. 出处:「第2章　逻辑——真与假的二元世界」第 1028 段(text/07-ch02.txt:1028,搜「卡诺图通常用于简化逻辑表达式、设计逻辑电路等」)。 ↩

  18. 出处:「第2章　逻辑——真与假的二元世界」第 1031 段(text/07-ch02.txt:1031,搜「逻辑上只使用真」)。 ↩

  19. 出处:「第2章　逻辑——真与假的二元世界」第 1034 段(text/07-ch02.txt:1034,搜「陷入无限循环、抛出异常」)。原文说这些情况下「得不到 true 和 false 中的任何一个值」。 ↩

  20. 出处:「第2章　逻辑——真与假的二元世界」第 1036 段(text/07-ch02.txt:1036,搜「叫 undefined 的值」)。原文写明 undefined 意为「未定义」。 ↩

  21. 出处:「第2章　逻辑——真与假的二元世界」第 1064 段(text/07-ch02.txt:1064,搜「不包含 undefined 的行」)。原文一共列了四条结论,第一条是「不包含 undefined 的行,和逻辑与 A ∧ B 相等」——也就是说,老规矩在没有第三个值的行上原样保留。 ↩

  22. 出处:「第2章　逻辑——真与假的二元世界」第 1069 段(text/07-ch02.txt:1069,搜「这里计算机不进行任何处理」)。原文说,从左往右读每一行、把 undefined 这样解读,就能马上理解上面的结论。 ↩

  23. 出处:「第2章　逻辑——真与假的二元世界」第 1107 段(text/07-ch02.txt:1107,搜「在判」)与第 1108 段(text/07-ch02.txt:1108,搜「应根据条件 A 判断是否需要看 B」)。原文给的英文名是 conditional and / short-circuit logical and。 ↩

  24. 出处:「第2章　逻辑——真与假的二元世界」第 1109 段(text/07-ch02.txt:1109,搜「这其」)与第 1112 段(text/07-ch02.txt:1112,搜「if (A) {」)。原书还写明:这个 && 和 C、Java 中的 && 意思相同。 ↩

  25. 出处:「第2章　逻辑——真与假的二元世界」第 1117 段(text/07-ch02.txt:1117,搜「所谓的交换法则不成立」)。 ↩

  26. 出处:「第2章　逻辑——真与假的二元世界」第 1158 段(text/07-ch02.txt:1158,搜「A 为 true 时」)。原书的表(图 2-35)同样是九行,结论与 && 对称。 ↩

  27. 出处:「第2章　逻辑——真与假的二元世界」第 1164 段(text/07-ch02.txt:1164,搜「和下面的程序是一样的」)。原书把等价的 if-else 完整写了出来(第 1166 到 1172 段)。 ↩

  28. 出处:「第2章　逻辑——真与假的二元世界」第 1120 段(text/07-ch02.txt:1120,搜「check() && execute()」)。 ↩

  29. 出处:「第2章　逻辑——真与假的二元世界」第 1124 段(text/07-ch02.txt:1124,搜「就不执行 execute() 了」)。原文的原话是:这里的 check() 起到了检查可否执行 execute() 的作用。磁盘那个例子是我们编的,书里只说了机制。 ↩

  30. 出处:「第2章　逻辑——真与假的二元世界」第 1226 段(text/07-ch02.txt:1226,搜「德摩根定律在三值逻辑中确实也成立」)。原书图 2-37 是一张九行十列的大表,把两条等式的四个式子并排列出来逐行比对。 ↩

  31. 出处:「第2章　逻辑——真与假的二元世界」第 1238 段(text/07-ch02.txt:1238,搜「数量将达到 39 个」)。原文说因此不再赘述,本节介绍的是编程中常用的 &&、|| 以及 !。 ↩