第二章 布尔运算
计算机使用二进制来存储信息，$1$ 个比特位可以表示 $2$ 种情况， $n$ 个比特位可以表示 $2^n$ 种情况。我们可以直接按全 $0$ 到全 $1$ 的顺序来排列，另外在计算机中采用了二进制的补码来表示数字，也就是说十进制的 $（-x）$ 用二进制的 $（2^n - x）$ 来表示，关于这个表示方法有很多的好处，可以从理论上面给出证明，这个在很多地方可以搜索到。在本章中我们主要关注布尔函数的构造，关键的是利用真值表，比如异或门的真值表
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
观察到 $out$ 列中的 $1$ 我们可以得到一个布尔函数 $out = \overline{a}b + a\overline{b}$ ，根据这个布尔函数就可以构造出相关的电路。
同理，可以来看一个半加法器的真值表，表中的 $sum$ 表示和，$carry$ 表示进位。这样以来就很明显的可以看出可以用一个异或门和一个与门来实现一个半加法器。
| a | b | sum | carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
我们继续看全加法器的真值表
| a | b | c | sum | carry |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
我们可以先用一个半加法器把b和c的结果sum1和carry1给计算出来，在用一个半加法器把a和sum1的结果sum2和carry2给计算出来。然后可以知道sum2，carry1或着carry2就是就是全加法器的结果sum和carry。