怎样证明两个表达式等价？

为两个表达式在所有输入组合下各做一列真值表，再比较输出列。如果每一行都相同，它们就等价。只要有一行不同，就足以说明不等价，这一行就是你的反例。

需要检查多少种情形？

全部检查：2 的输入个数次方。两个输入有 4 种情形，三个输入有 8 种。检查的情形不够，只能证明它们不同，永远不能证明它们相同。

像德摩根定律这样的规则，记熟之后更快，但情形法永远有效，也不需要死记。在 IGCSE 阶段，清楚的情形表是展示推理的可靠方法。

当两个布尔表达式对每一种可能的输入都给出相同的输出，它们就是等价的（equivalent）。比较时，为每个表达式做一列，覆盖所有输入情形，再找出两列不同的那一行。

一次不吻合就是一个反例（counterexample）。它能立刻解决问题，所以可以停下来。

NOT (A AND B) 和 (NOT A) OR (NOT B) 等价吗？

A	B	A AND B	NOT (A AND B)	NOT A	NOT B	(NOT A) OR (NOT B)
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

两个结果列分别是 1、1、1、0 和 1、1、1、0。四行全部吻合，所以这两个表达式等价。

再比较 NOT (A OR B) 和 (NOT A) OR (NOT B)。取 A = 0、B = 1：NOT (0 OR 1) = NOT 1 = 0，但 (NOT 0) OR (NOT 1) = 1 OR 0 = 1。值不同，所以这两个表达式不等价。反例就是 A = 0、B = 1。

常见错误是只试一种情形，就断定两者相等。

错误推理：“A = 0、B = 0 时，NOT (A OR B) = 1，(NOT A) OR (NOT B) = 1。吻合，所以等价。”

一行吻合证明不了什么。同样这两个表达式在 A = 0、B = 1 时就不同。正确的做法是检查全部四种情形，或者一旦发现有不同的一行就立刻停止。

1. A AND (A OR B) 与 A 等价吗？

查看答案

若 A = 0：0 AND (0 OR B) = 0，与 A 相同。若 A = 1：1 AND (1 OR B) = 1 AND 1 = 1，与 A 相同。两种情形都吻合，所以它们等价。

2. NOT (A AND B) 与 (NOT A) AND (NOT B) 等价吗？如果不等价，请给出反例。

查看答案

不等价。取 A = 1、B = 0：NOT (1 AND 0) = NOT 0 = 1，但 (NOT 1) AND (NOT 0) = 0 AND 1 = 0。反例是 A = 1、B = 0。

3. A OR ((NOT A) AND B) 与 A OR B 等价吗？

查看答案

若 A = 1：左边是 1 OR (0 AND B) = 1，右边是 1 OR B = 1。若 A = 0：左边是 0 OR (1 AND B) = B，右边是 0 OR B = B。所有情形都吻合，所以它们等价。

下一步，看日常语句如何隐藏不止一种逻辑读法：区分逻辑 AND 与日常语言的歧义。然后试试布尔逻辑练习。布尔与数字表示实验室可以核对你的情形表。

如果你在课堂上会比较表达式，却不确定写多少步骤才能得分，我们的老师可以在一对一线上计算机科学补习中和你一起讨论。