| English | 释义 | 拼音 |
|---|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | 布尔代数 | bù ěr dài shù |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | 德摩根定律 | dé mó gēn dìng lǜ |
| Karnaugh map/ˈkɑːnɔː mæp/ | 卡诺图 | kǎ nuò tú |
| truth table/truːθ ˈteɪbl/ | 真值表 | zhēn zhí biǎo |
| absorption/əbˈsɔːpʃn/ | 吸收律 | xī shōu lǜ |
| Gray code/ɡreɪ kəʊd/ | 格雷码 | gé léi mǎ |
建起数字时代的那篇硕士论文
- 1937 年,一位 21 岁的学生 Claude Shannon 注意到,他研究的电话继电器所做的事,和八十年前 George Boole 为推理真假而发明的一种代数是同一回事。
- 如果一个开关是一个布尔变量,那么一个电路就是一个表达式,而化简表达式就是从电路里去掉门。门更少意味着更便宜、更快、更省电。
- 他的论文被称为那个世纪最重要的论文。这一页上的一切,都是把那一个想法当作工具来用。
- 这一课讲布尔代数(Boolean algebra)、德摩根定律,以及用眼睛做同样工作的卡诺图(Karnaugh map)。
记号与定律
+表示 OR,·表示 AND 且常常省略,上划线表示 NOT。真值表(truth table)把同样的东西穷尽地列出来。- 同一律:$A + 0 = A$,$A \cdot 1 = A$。零律:$A + 1 = 1$,$A \cdot 0 = 0$。
- 幂等律:$A + A = A$。互补律:$A + \overline{A} = 1$,$A \cdot \overline{A} = 0$。
- 吸收律(absorption):$A + A\cdot B = A$,因为若 $A$ 为真,不论 $B$ 如何整个表达式都为真。
Match each Boolean law to what it says.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
These laws let you simplify Boolean expressions algebraically before building the circuit.
By the absorption law, A + A·B simplifies to ____.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
If A is true the whole expression is true whatever B is, and if A is false both terms are false. B cannot affect the result.
德摩根定律
- 德摩根定律(De Morgan's laws)是考试要求你点名使用的那两条:
- 用话说的口诀:整体取反、AND 与 OR 互换、每一项各自取反。
- 它们在实践中重要,是因为它们让任何表达式都能只用 NAND 门或只用 NOR 门重写,而由一种重复的门造出的芯片制造成本更低。

两个表达式,一张真值表
Boolean algebra
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables.
By De Morgan's law, $\overline{A \cdot B}$ equals:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select 所有 that apply.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative.
例题:化简,并数一数门
- 化简 $Z = A\cdot B + A\cdot\overline{B}$ 并说明它省下了什么。
- 提出 $A$:$Z = A\cdot(B + \overline{B})$。由互补律 $B + \overline{B} = 1$,所以 $Z = A \cdot 1 = A$。
- 原式需要两个 AND 门、一个 NOT 和一个 OR:四个门。化简后的表达式一个都不需要,只要输入 $A$。
- 结尾一定要说化简换来了什么:门更少,所以电路更便宜、更快、更省电。
Simplify $A\cdot B + A\cdot\overline{B}$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B needs two ANDs, one NOT and one OR. How many gates does its simplified form need?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved.
卡诺图
- 卡诺图通过把真值表里相邻的 1 分组来化简表达式。
- 行和列按格雷码(Gray code)顺序
00, 01, 11, 10标注,使得相邻单元恰好只有一个变量不同。这就是全部诀窍:它把代数变成看得见的相邻关系。 - 在输出为 1 的每个单元里填 1,然后找出边长为 2 的幂(1、2、4、8)的矩形 1 组。组可以跨边界绕回。

矩形越大,项越简单
A Karnaugh map simplifies a Boolean expression by:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work.
读一个组
- 在一个组内部,保持不变的变量留在项里;发生变化的变量消失。
- 所以 2 的组去掉一个变量,4 的组去掉两个,8 的组去掉三个。组越大,项越简单。
- 用尽可能少、尽可能大的组覆盖每一个 1,再把各组的项 OR 起来。组可以重叠,而重叠往往正是能凑出更大组的原因。
In a Karnaugh map, a larger group of adjacent 1s eliminates more variables, giving a simpler term (a group of 2 drops one variable, a group of 4 drops two).
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes.
Put the steps of simplifying with a Karnaugh map in order.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1.
例题:读一张双变量卡诺图
- 一张关于 $A$ 和 $B$ 的卡诺图在 $\overline{A}B$ 和 $AB$ 两个单元里有 1。化简它。
- 这两个 1 是相邻的:它们同在 $B = 1$ 这一列,所以可以组成一个 2 的矩形。
- 在这个组里 $B$ 始终是 1,而 $A$ 从 0 变到 1。变化的那个变量消失。
- 所以整个表达式就是 $Z = B$。把它和未化简的积之和 $\overline{A}B + AB$ 比一比:后者需要一个 NOT、两个 AND 和一个 OR。
用哪种方法
- 布尔代数精确,对任意多个变量都适用,但你必须看出该用哪条定律。
- 卡诺图是机械的,在两到四个变量时很难出错——而考试考的正是这个范围——而且它直接把最大的分组显示给你。
- 两者给出同样的答案。卡诺图的好处是化简变成了看,而不是去搜寻一条定律。
容易丢掉的分
- 德摩根是整体取反、运算符互换、每一项各自取反。只换运算符是典型的半个答案。
- 卡诺图的行必须按格雷码顺序
00, 01, 11, 10。按二进制计数顺序排,相邻关系就错了,分组也就失败。 - 组的大小是2 的幂,并且可以跨边界绕回。三个一组不成组。
- 要说出化简是为了什么:门更少,所以更便宜、更快、更省电。
你掌握了
- 布尔代数把表达式改写成更少的项,于是电路需要更少的门
- 德摩根:$\overline{A + B} = \overline{A} \cdot \overline{B}$,$\overline{A \cdot B} = \overline{A} + \overline{B}$;吸收律:$A + AB = A$;$A\cdot B + A\cdot\overline{B} = A$
- 卡诺图把真值表中相邻的 1 分组,行列按格雷码顺序排列,使相邻者只差一个变量
- 组内变化的变量会消失,所以组越大项越简单:用尽可能少、尽可能大的组覆盖每一个 1