第 1 讲 · 从逻辑门到组合逻辑

现存手绘材料尝试用 AND、OR 和 NOT 组成“同或”和“异或”电路。它也刚好展示了电子设计的一个基本方法：不靠电路长得像不像，而是把每个节点翻译成表达式，再逐行验证。

三种基本门

门	表达式	何时输出 1
AND	$A\land B$	$A$ 和 $B$ 都为 1
OR	$A\lor B$	至少一个为 1
NOT	$\lnot A$	$A$ 为 0

一条连线每经过一个门，就给它命名一个中间变量。最后一层只需要对中间变量再运算。

同或：两输入相同时为 1

$$A\operatorname{XNOR}B =\lnot(A\lor B)\lor(A\land B) =\lnot(A\oplus B).$$

$A$	$B$	XNOR
0	0	1
0	1	0
1	0	0
1	1	1

手绘图中“OR 后取反”与“AND”的输出再 OR，正好得到上式，所以同或部分是成立的。

异或：两输入不同时为 1

$$A\oplus B =(A\lor B)\land\lnot(A\land B).$$

关键是最后必须是 AND，因为要同时满足“至少一个为 1”和“不是两个都为 1”。

现存手绘图的“异或”部分把这两路在最后接到了 OR，其表达式是

$$(A\lor B)\lor\lnot(A\land B).$$

对任意 $A,B$，它都等于 1：若至少一个输入为 1，前项已为 1；若两者都为 0，后项为 1。因此它不是异或电路，最后一个 OR 应改为 AND。

电路验证的固定流程

1. 给每个门输出命名；
2. 从输入向输出写布尔表达式；
3. 用德摩根律简化：$\lnot(A\lor B)=\lnot A\land\lnot B$；
4. 列出 $2^n$ 种输入的真值表；
5. 将实际输出与目标功能逐行比对。