2.4 布尔代数、逻辑门与电路

第 2.1 与 2.2 节使用了真与假两种取值。数字系统把同样的两种可能存成比特： $1$ 表示真， $0$ 表示假。布尔代数（Boolean algebra）提供计算这些值的规则，逻辑门则把规则实现为电路。

组合电路可以读成一张有方向的依赖图：输入信号送入逻辑门，导线再把计算结果送往下一级。第 11 章会把这类图正式描述为由顶点和边组成的图；在这里，箭头只表示“后一个信号必须等待前一个信号算出”。

布尔值与变量

布尔域为

\mathbb B=\{0,1\}.

布尔变量 $x$ 只能从 $\mathbb B$ 中取一个值。布尔函数

f:\mathbb B^n\to\mathbb B

接收 $n$ 个布尔输入，产生一个布尔输出。

例如，双输入函数共有四种输入赋值，因为

|\mathbb B^2|=2^2=4.

真值表列出每一种输入赋值及其输出。含 $n$ 个输入的真值表有 $2^n$ 行输入。

非、与、或

三种基本布尔运算对应第 2.1 与 2.2 节的逻辑联结词。

非（NOT）写作 $\neg x$ ，会反转一个值：

$x$	$\neg x$
$0$	$1$
$1$	$0$

与（AND）写作 $x\land y$ ，只有两个输入都是 $1$ 时才等于 $1$ 。

或（OR）写作 $x\lor y$ ，至少一个输入为 $1$ 时就等于 $1$ 。

$x$	$y$	$x\land y$	$x\lor y$
$0$	$0$	$0$	$0$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

电子逻辑门实现一种布尔运算。非门只有一个输入；与门和或门可以有两个或更多输入，本节若无特别说明，都使用双输入门。

逐步求表达式的值

考虑

f(x,y,z)=(x\land\neg y)\lor z.

括号指定依赖顺序。当 $(x,y,z)=(1,0,0)$ 时：

1. 先计算 $\neg y=\neg0=1$ ；

2. 再计算 $x\land\neg y=1\land1=1$ ；

3. 最后计算 $(x\land\neg y)\lor z=1\lor0=1$ 。

因此输出为 $f(1,0,0)=1$ 。

没有括号时，优先级为

\neg\quad\text{先于}\quad\land\quad\text{先于}\quad\lor.

所以 $\neg x\land y\lor z$ 表示 $((\neg x)\land y)\lor z$ 。

从表达式到电路

构造 $(x\land\neg y)\lor z$ 的电路，可以分三步：

1. 让 $y$ 经过非门；

2. 把 $x$ 与 $\neg y$ 送入与门；

3. 把与门输出和 $z$ 送入或门。

每根导线携带一个布尔信号。只有所有输入信号都已到达，逻辑门才能计算。这里的电路是组合电路，因此输出只取决于当前输入，与过去输入无关。

求值时，依赖箭头不能绕回尚未完成计算的逻辑门，否则当前输出会立即依赖自身。第 11 章会把没有这种回路的依赖图称为无环图；第 12 章则会加入存储状态，让受控反馈能够在时间维度上获得明确含义。

正在加载交互实验...

让三个实时输入信号通过两级可配置逻辑门。切换输入及其反相器、选择每一级逻辑门，并观察带标签的信号、逐级求值、输出与完整真值表如何立即同步更新。

正在加载概念检查...

正在加载本节练习...

布尔恒等式

若两个布尔表达式对每一种输入赋值都产生相同输出，就称它们等价，写作

F\equiv G.

真值表可以逐行比较两个输出列，从而证明等价。布尔恒等式则让我们通过代数变换完成相同证明。

对 $x,y,z\in\mathbb B$ ：

定律	布尔恒等式
恒等律	$x\land1\equiv x$ ， $\quad x\lor0\equiv x$
零一律	$x\land0\equiv0$ ， $\quad x\lor1\equiv1$
幂等律	$x\land x\equiv x$ ， $\quad x\lor x\equiv x$
互补律	$x\land\neg x\equiv0$ ， $\quad x\lor\neg x\equiv1$
双重否定律	$\neg(\neg x)\equiv x$
交换律	$x\land y\equiv y\land x$ ， $\quad x\lor y\equiv y\lor x$
结合律	$(x\land y)\land z\equiv x\land(y\land z)$ ，或运算同理
分配律	$x\land(y\lor z)\equiv(x\land y)\lor(x\land z)$
对偶分配律	$x\lor(y\land z)\equiv(x\lor y)\land(x\lor z)$
吸收律	$x\lor(x\land y)\equiv x$ ， $\quad x\land(x\lor y)\equiv x$

德摩根律会让否定穿过括号，同时交换与、或：

\neg(x\land y)\equiv\neg x\lor\neg y,

\neg(x\lor y)\equiv\neg x\land\neg y.

例如，

\begin{aligned} (x\land y)\lor(x\land\neg y) &\equiv x\land(y\lor\neg y)\\ &\equiv x\land1\\ &\equiv x. \end{aligned}

第一个表达式需要两个与门、一个非门和一个或门；化简后只需传递 $x$ 的导线。等价函数可能拥有完全不同的电路成本。

与非门和或非门具有完备性

与非门（NAND）计算

x\uparrow y=\neg(x\land y).

或非门（NOR）计算

x\downarrow y=\neg(x\lor y).

如果只使用某一种逻辑门就能实现任意布尔函数，就称这种门具有功能完备性。与非门单独就具有功能完备性，因为

\neg x=x\uparrow x,

x\land y=\neg(x\uparrow y)=(x\uparrow y)\uparrow(x\uparrow y),

再利用德摩根律即可构造或运算。或非门也有对偶构造。

从真值表构造函数

文字是变量或其否定，例如 $x$ 或 $\neg x$ 。最小项是若干文字的与，并且只在真值表的一行上等于 $1$ 。

对输入行 $(x,y,z)=(1,0,1)$ ，对应最小项为

x\land\neg y\land z.

每个文字都要求相应输入取指定值，因此该最小项只选中这一行。

从任意真值表构造布尔函数，可以这样做：

1. 为输出为 $1$ 的每一行写一个最小项；

2. 用或连接所有最小项。

所得形式称为析取范式（Disjunctive Normal Form，DNF），也称“积之和”形式。

假设 $f(x,y)$ 在 $01,10,11$ 三行上等于 $1$ ，则

f=(\neg x\land y)\lor(x\land\neg y)\lor(x\land y).

通过代数化简可得

f\equiv x\lor y.

析取范式保证构造正确，化简则负责降低成本。

异或与半加器

异或（XOR）写作 $x\oplus y$ ，只有两个输入不同时才等于 $1$ ：

x\oplus y=(\neg x\land y)\lor(x\land\neg y).

半加器把两个一位二进制数 $x,y$ 相加。它的两个输出是：

S=x\oplus y

表示和位，以及

C=x\land y

表示进位。

$x$	$y$	和位 $S$	进位 $C$	二进制结果
$0$	$0$	$0$	$0$	$00$
$0$	$1$	$1$	$0$	$01$
$1$	$0$	$1$	$0$	$01$
$1$	$1$	$0$	$1$	$10$

两个输出说明：同一组输入可以同时送入多个布尔函数。

正在加载交互实验...

选择一个双输入或三输入目标，涂出输出应为 $1$ 的全部真值表行。锻造台会把每个选中行变成最小项，实时组成规范 DNF 电路，统计文字数与不匹配行数，并在全部真值表行与目标一致时立即确认。

正在加载概念检查...

正在加载本节练习...

从当前信号走向记忆状态

布尔代数解释当前输入如何产生当前输出。组合电路没有记忆：相同输入一定产生相同输出。

交通灯、登录协议、自动售货机和通信控制器必须记住此前发生过什么。第 12 章会加入有限状态变量，使同一个当前输入能够在不同状态下触发不同动作。在此之前，第 3 章将建立证明方法，用来严格论证布尔恒等式以及课程后续出现的其他结论。

2.4 布尔代数、逻辑门与电路

布尔值与变量

布尔域为

\mathbb B=\{0,1\}.

布尔变量 $x$ 只能从 $\mathbb B$ 中取一个值。布尔函数

f:\mathbb B^n\to\mathbb B

接收 $n$ 个布尔输入，产生一个布尔输出。

例如，双输入函数共有四种输入赋值，因为

|\mathbb B^2|=2^2=4.

真值表列出每一种输入赋值及其输出。含 $n$ 个输入的真值表有 $2^n$ 行输入。

非、与、或

三种基本布尔运算对应第 2.1 与 2.2 节的逻辑联结词。

非（NOT）写作 $\neg x$ ，会反转一个值：

$x$	$\neg x$
$0$	$1$
$1$	$0$

与（AND）写作 $x\land y$ ，只有两个输入都是 $1$ 时才等于 $1$ 。

或（OR）写作 $x\lor y$ ，至少一个输入为 $1$ 时就等于 $1$ 。

$x$	$y$	$x\land y$	$x\lor y$
$0$	$0$	$0$	$0$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

电子逻辑门实现一种布尔运算。非门只有一个输入；与门和或门可以有两个或更多输入，本节若无特别说明，都使用双输入门。

逐步求表达式的值

考虑

f(x,y,z)=(x\land\neg y)\lor z.

括号指定依赖顺序。当 $(x,y,z)=(1,0,0)$ 时：

1. 先计算 $\neg y=\neg0=1$ ；

2. 再计算 $x\land\neg y=1\land1=1$ ；

3. 最后计算 $(x\land\neg y)\lor z=1\lor0=1$ 。

因此输出为 $f(1,0,0)=1$ 。

没有括号时，优先级为

\neg\quad\text{先于}\quad\land\quad\text{先于}\quad\lor.

所以 $\neg x\land y\lor z$ 表示 $((\neg x)\land y)\lor z$ 。

从表达式到电路

构造 $(x\land\neg y)\lor z$ 的电路，可以分三步：

1. 让 $y$ 经过非门；

2. 把 $x$ 与 $\neg y$ 送入与门；

3. 把与门输出和 $z$ 送入或门。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

布尔恒等式

若两个布尔表达式对每一种输入赋值都产生相同输出，就称它们等价，写作

F\equiv G.

真值表可以逐行比较两个输出列，从而证明等价。布尔恒等式则让我们通过代数变换完成相同证明。

对 $x,y,z\in\mathbb B$ ：

定律	布尔恒等式
恒等律	$x\land1\equiv x$ ， $\quad x\lor0\equiv x$
零一律	$x\land0\equiv0$ ， $\quad x\lor1\equiv1$
幂等律	$x\land x\equiv x$ ， $\quad x\lor x\equiv x$
互补律	$x\land\neg x\equiv0$ ， $\quad x\lor\neg x\equiv1$
双重否定律	$\neg(\neg x)\equiv x$
交换律	$x\land y\equiv y\land x$ ， $\quad x\lor y\equiv y\lor x$
结合律	$(x\land y)\land z\equiv x\land(y\land z)$ ，或运算同理
分配律	$x\land(y\lor z)\equiv(x\land y)\lor(x\land z)$
对偶分配律	$x\lor(y\land z)\equiv(x\lor y)\land(x\lor z)$
吸收律	$x\lor(x\land y)\equiv x$ ， $\quad x\land(x\lor y)\equiv x$

德摩根律会让否定穿过括号，同时交换与、或：

\neg(x\land y)\equiv\neg x\lor\neg y,

\neg(x\lor y)\equiv\neg x\land\neg y.

例如，

\begin{aligned} (x\land y)\lor(x\land\neg y) &\equiv x\land(y\lor\neg y)\\ &\equiv x\land1\\ &\equiv x. \end{aligned}

第一个表达式需要两个与门、一个非门和一个或门；化简后只需传递 $x$ 的导线。等价函数可能拥有完全不同的电路成本。

与非门和或非门具有完备性

与非门（NAND）计算

x\uparrow y=\neg(x\land y).

或非门（NOR）计算

x\downarrow y=\neg(x\lor y).

如果只使用某一种逻辑门就能实现任意布尔函数，就称这种门具有功能完备性。与非门单独就具有功能完备性，因为

\neg x=x\uparrow x,

x\land y=\neg(x\uparrow y)=(x\uparrow y)\uparrow(x\uparrow y),

再利用德摩根律即可构造或运算。或非门也有对偶构造。

从真值表构造函数

文字是变量或其否定，例如 $x$ 或 $\neg x$ 。最小项是若干文字的与，并且只在真值表的一行上等于 $1$ 。

对输入行 $(x,y,z)=(1,0,1)$ ，对应最小项为

x\land\neg y\land z.

每个文字都要求相应输入取指定值，因此该最小项只选中这一行。

从任意真值表构造布尔函数，可以这样做：

1. 为输出为 $1$ 的每一行写一个最小项；

2. 用或连接所有最小项。

所得形式称为析取范式（Disjunctive Normal Form，DNF），也称“积之和”形式。

假设 $f(x,y)$ 在 $01,10,11$ 三行上等于 $1$ ，则

f=(\neg x\land y)\lor(x\land\neg y)\lor(x\land y).

通过代数化简可得

f\equiv x\lor y.

析取范式保证构造正确，化简则负责降低成本。

异或与半加器

异或（XOR）写作 $x\oplus y$ ，只有两个输入不同时才等于 $1$ ：

x\oplus y=(\neg x\land y)\lor(x\land\neg y).

半加器把两个一位二进制数 $x,y$ 相加。它的两个输出是：

S=x\oplus y

表示和位，以及

C=x\land y

表示进位。

$x$	$y$	和位 $S$	进位 $C$	二进制结果
$0$	$0$	$0$	$0$	$00$
$0$	$1$	$1$	$0$	$01$
$1$	$0$	$1$	$0$	$01$
$1$	$1$	$0$	$1$	$10$

两个输出说明：同一组输入可以同时送入多个布尔函数。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

从当前信号走向记忆状态

布尔代数解释当前输入如何产生当前输出。组合电路没有记忆：相同输入一定产生相同输出。