真值表 — 把「不是、并且、或者」钉死成一张表
这一章讲三件事: 为什么「或者」这种日常词非得钉死不可; 钉死的工具长什么样(一张把所有情况列全的表); 以及同一句话在五种连接词下会得到哪五个不同的答案。
它在全书链条里的位置: 第 02 章说一条规则不能漏、不能重。 可规则一复杂,就得把好几个条件连起来说——而「连起来」的方式本身就有歧义。 这一章把连接词一个个钉死,第 04 章再用它们推出更绕的关系。 需要的基础: 第 02 章的「命题、真、假」。
1. 先看现象:同一个「或者」,两句话两个意思
原书开篇摆了两段对话,并排放在一起特别刺眼1:
第一段。 技术员说:按下紧急按钮或者水位高于危险水位时,警报器就报警。 有人问:那按钮按下、并且水位也超标的时候,报不报警?技术员说当然报。
第二段。 有人说:他现在在大阪或者东京。 有人问:那他有没有可能既在东京又在大阪?说话的人说这怎么可能。
同一个「或者」,一个包含「两件事都成立」,另一个排除它。 说话的人自己都没意识到用了两个意思——而需求文档就是用这种语言写的。
程序不接受这种含糊。 所以要给每个连接词配一张表,把所有可能的真假组合列全, 一行一行钉死。这张表叫真值表。
全章的主走查:一位 4 岁的乘客,在星期日乘车
────────────────────────────────────────────────
命题 A =「这位乘客的年龄在 6 岁以上」→ 假(他 4 岁)
命题 B =「乘车日是星期日」 → 真
────────────────────────────────────────────────
¬A 不是 A → 真
A ∧ B A 并且 B → 假
A ∨ B A 或者 B(至少一个) → 真
A ⊕ B A 或者 B(但不能都成立) → 真
A = B A 和 B 相等 → 假
────────────────────────────────────────────────
图说:同一个人、同一天,五种连法给出五个答案。
这一章每一节讲一行,五行走完这一章就完了。
2. 「不是」:两行就钉死了
这一节回答:最简单的连接词怎么钉。
从「乘车日是星期日」这个命题出发,可以造出「乘车日不是星期日」。
这种「不是……」的运算叫作非,英文写作 not,符号写成 ¬A2。
用文字解释容易含糊,所以原书直接上表3:
| A | ¬A |
|---|---|
| 真 | 假 |
| 假 | 真 |
两行,这就是「非」的全部定义。
为什么两行就够? 因为 A 是命题,它只能是真或假,不能是别的(第 02 章说过)。 两行正好把所有情况罗列完,不漏也不重——第 02 章那两条底线,在这里第一次被用上了4。
走查第一步: 我们那位 4 岁乘客,A =「年龄在 6 岁以上」为假, 所以 ¬A =「年龄不到 6 岁」为真。
3. 同一张表还能用来证明:「不是不是」等于「是」
这一节回答:这张表除了下定义,还能干什 么。
「乘车日不是不是星期日」和「乘车日是星期日」,说的是同一件事吗? 凭感觉是,但感觉不能当证据。
办法是把表再往右接一列5:
| A | ¬A | ¬¬A |
|---|---|---|
| 真 | 假 | 真 |
| 假 | 真 | 假 |
比较第一列和第三列:两行都一模一样。 由于这两行已经穷尽了所有情况, 所以 A 和 ¬¬A 是相等的,这就证完了。
这是真值表的第二种用法:不只是定义,还能证明6。 后面几章会反复用到它——只要能把所有情况列成有限的几行,就能靠「逐行核对」下结论。 (第 05 章会用同样的办法,在九行表上核对一条定律。)
4. 另一副面孔:文氏图
这一节回答:表格能列全,但看不出形状;有没有更直观的?
有。把「命题为真的那些情况」画成一块地——这种图叫文氏图7。
┌─────────────────────────┐ ┌─────────────────────────┐
│ 一星期的七天 │ │▓▓一星期的七天▓▓▓▓▓▓▓▓▓▓▓│
│ ╭───────╮ │ │▓▓▓▓▓╭───────╮▓▓▓▓▓▓▓▓▓▓│
│ │ 星期日│ ← A 为真 │ │▓▓▓▓▓│ 星期日│▓▓▓▓▓▓▓▓▓▓│
│ ╰───────╯ │ │▓▓▓▓▓╰───────╯▓▓▓▓▓▓▓▓▓▓│
│ 星期一…星期六 │ │▓▓星期一…星期六▓▓▓▓▓▓▓▓▓▓│
└─────────────────────────┘ └─────────────────────────┘
命题 A:乘车日是星期日 命题 ¬A:乘车日不是星期日
图说:外面那个方框是「所有可能的情况」,里面的圈是「A 为真的那些情况」。
▓ 表示这个式子为真的地盘。取反就是把阴影翻个面。
文氏图本来是画集合关系的:外面的方框表示全集(这里是一星期所有日子), 里面的椭圆表示「星期日的集合」,也就是「命题 A 为真的那些日子」8。
它比表格强的地方只有一处,但很要命:两个式子等不等,一眼就看得出来—— 阴影一样,就是同一件事。 第 04 章那条最难记的定律,靠这张图三秒钟就能确认。
5. 「并且」:四行,只有一行为真
这一节回答:两个命题连起来,表要列几行。
把「年龄在 6 岁以上」和「乘车日是星期日」连起来,得到
「年龄在 6 岁以上,并且乘车日是星期日」。
这种「A 并且 B」的运算叫作与,英文写作 and,符号写成 A ∧ B9。
它的定义只有一句:仅当 A 和 B 都为真时,A ∧ B 才为真10。列成表11:
| A | B | A ∧ B |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 假 | 假 |
| 假 | 真 | 假 |
| 假 | 假 | 假 |
为什么是四行? A 有真假两种,每一种对应 B 的真假两种, 所以一共 2 × 2 = 4 种12。四行覆盖了全部情况,不漏也不重。
走查第二步: 我们那位 4 岁乘客在星期日——A 假、B 真,落在第三行, 所以 A ∧ B 为假。他不满足「6 岁以上并且星期日」这个条件。
画成文氏图,A ∧ B 就是两个椭圆重叠的那一块—— 既在 A 里面,又在 B 里面13。
6. 「或者」:说反话更好懂
这一节回答:第 1 节那个歧义,数学这边选了哪个意思。
超市对「持有礼券 A,或者礼券 B」的顾客打折,两张都有也照样打折。
这种「A 或者 B」的运算叫作或,英文写作 or,符号写成 A ∨ B14。
定义是:A 和 B 里至少有一个为真,它就为真15。
| A | B | A ∨ B |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 假 | 真 |
| 假 | 真 | 真 |
| 假 | 假 | 假 |
这里原书教了一个很实用的小习惯:碰上「至少……」这种说法, 多半反过来说更清楚。「A 和 B 中至少有一个为真时为真」这句要在脑子里绕一下; 「仅当 A 和 B 都为假时才为假」——一句就懂了16。
于是真值表的第三种用处出来了:它还能帮你找到更简洁的说法17。 看着表格找哪一行最少,照那一行说话。
走查第三步: 4 岁乘客在星期日——A 假、B 真,落在第三行,A ∨ B 为真。
7. 另一种「或者」:两个都真,反而假
这一节回答:第 1 节那两段对话里,另一个「或者」怎么表示。
「他现在在东京,或者他现在在大阪」——他不可能同时在两地。
这种「A 或者 B,但不能都成立」的运算叫作异或,
英文写作 exclusive or,符号写成 A ⊕ B18。
| A | B | A ⊕ B |
|---|---|---|
| 真 | 真 | 假 ← 和「或」唯一不同的一行 |
| 真 | 假 | 真 |
| 假 | 真 | 真 |
| 假 | 假 | 假 |
它和「或」只差第一行。 一句话记法:仅当 A 和 B 不同时,A ⊕ B 才为真19。
原书还给了一个能动手做出来的版本:两个开关、一个灯泡、一节电池20。
真 真
╱ ╱
────● 开关 A ────● 开关 B ┌───────┐
╲ ╲ │ 灯泡 │
假 假 └───────┘
└──────── 电池 ────────────────────────────┘
图说:两个开关各自可以拨到「真」或「假」两个接线柱上。
只有当两个开关拨的位置不同时,电路才通、灯才亮 —— 这正是 A ⊕ B。
走查第四步: 4 岁乘客在星期日——A 假、B 真,两者不同,所以 A ⊕ B 为真。 (注意它和上一节的 A ∨ B 同为真;这两个「或者」的差别只在两者都真的那一行上。)
8. 「A 和 B 相等」也是一个命题
这一节回答:除了连接词,还有一种被忽略的运算。
「A 和 B 相等」这句话本身也能判对错,所以它也是一个命题,写成 A = B21。
| A | B | A = B |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 假 | 假 |
| 假 | 真 | 假 |
| 假 | 假 | 真 |
注意最后一行:两个都假,它们也算「相等」。 相等说的是真假一致,不是「都成立」。
走查第五步: 4 岁乘客在星期日——A 假、B 真,不一致,所以 A = B 为假。
把这张表和上一节的异或表并排看,你会发现它们处处相反。
所以 ¬(A ⊕ B) 和 A = B 是同一件事22。
这里还蹦出一个有用的说法: 「¬(A ⊕ B) 和 A = B 相等」这句话本身也是命题,
而且不管 A、B 是真是假,它永远为真——这种永远为真的命题叫作恒真命题23。
9. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 五个运算符的定义 | 给了表,每张表都罗列了全部情况,不漏不重 |
| 「不是不是」等于「是」 | 给了证明(第三列与第一列逐行相同) |
| 真值表能定义、能证明、还能找更简洁的说法 | 给了三处示范,第三处就是「或」的反说法 |
| 文氏图更直观 | 是作者的说法;书里承认表格「有时并不直观」,但没有解释为什么图更好懂 |
判断(我们的,不是书里的):这一章真正的收益不是五个符号,是「列全所有情况」这个动作。 五个符号里,程序员真正天天用的只有三个(与、或、非), 而「把所有组合列出来逐行核对」这个动作,在写复杂条件、写测试用例、 排查「为什么这个分支进不去」的时候都用得上。 两个条件是 4 行,三个条件是 8 行——能列完就能保证不漏。 如果错,会错在: 条件一多,行数会翻倍(这正是第 13 章讲的那件事), 到十几个条件就列不完了。判据是:你手上那段条件判断里有几个能各自变来变去的开关。
这一章的边界:
- 原书这一章还没讲完:蕴涵(若 A 则 B)与德摩根定律在第 04 章, 卡诺图与三值逻辑在第 05 章;
- 文氏图只用于两个命题——三个命题的图开始难画,原书到第 05 章改用另一种图;
- 「真值表能证明」有个前提没点破:它只对「情况有限」的命题成立。 情况无限多的断言证不了——那要等到第 08 章的数学归纳法;
- 没有讲这五个符号在具体语言里怎么写(
&&、||、!),那是第 05 章的事。
10. 可带走的
- 自然语言的「或者」至少有两个意思,一个包含「两者都成立」,一个排除它;
- 真值表就是把所有真假组合列全的表;两个命题正好 4 行,不漏不重;
- 非(
¬A):两行,真变假、假变真; - 与(
A ∧ B):四行只有一行真——两个都真才真; - 或(
A ∨ B):四行只有一行假——记成「仅当都假才假」,比「至少一个真」好懂; - 异或(
A ⊕ B):和「或」只差一行——两个都真时它是假;两个开关一个灯泡就是它; - 相等(
A = B):真假一致就为真,包括「两个都假」;它正好是异或的反面; - 真值表有三种用处:下定义、做证明、找更简洁的说法;
- 文氏图是真值表的另一副面孔:阴影一样,两个式子就相等——比逐行核对快得多。
11. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 两个「 或者」的对话 | 第2章 逻辑 | text/07-ch02.txt:6(搜「水位高于危险水位」) · :18(搜「他现在在大阪或者东京」) |
| 逻辑非与真值表 | 第2章 逻辑 | text/07-ch02.txt:279(搜「的命题的运算称作非」) · :286(搜「因此需要使用真值表」) · :301(搜「该真值表覆盖了所有情况」) |
| 双重否定 | 第2章 逻辑 | text/07-ch02.txt:309(搜「等于 A」) · :317(搜「也可以用于「证明」」) |
| 文氏图 | 第2章 逻辑 | text/07-ch02.txt:331(搜「就能很清晰地表示出命题的真假」) · :347(搜「文氏图原本是表示集合关系的图」) |
| 逻辑与 | 第2章 逻辑 | text/07-ch02.txt:360(搜「的命题运算称作逻辑与」) · :366(搜「仅当 A 和 B 都为 true 的时候」) · :386(搜「因此真值表的行数为４行」) |
| 逻辑或 | 第2章 逻辑 | text/07-ch02.txt:418(搜「礼券」) · :430(搜「仅当 A 和 B 都为 false 时才为 false」) · :431(搜「多数情况下考虑其否定意义能够更容易理解」) |
| 异或与电路图 | 第2章 逻辑 | text/07-ch02.txt:503(搜「的运算称作异或」) · :525(搜「仅当 A 和 B 不同时为 true」) · :540(搜「电路图来表示」) |
| 相等与恒真命题 | 第2章 逻辑 | text/07-ch02.txt:561(搜「相等」能成为一个命题) · :600(搜「答案是 A = B」) · :609(搜「恒真命题」) |