Boolean algebra and Karnaugh maps · 布尔代数与卡诺图
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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ǎ |
The master's thesis that built the digital age
- In 1937 a 21-year-old student named Claude Shannon noticed that the telephone relays he was studying were doing the same thing as an algebra George Boole had invented eighty years earlier for reasoning about true and false.
- If a switch is a Boolean variable, then a circuit is an expression, and simplifying the expression removes gates from the circuit. Fewer gates is cheaper, faster and less power.
- His thesis has been called the most important of the century. Everything on this page is that one idea used as a tool.
- This lesson is Boolean algebra 布尔代数, De Morgan's laws, and the Karnaugh map 卡诺图 that does the same job by eye.
建起数字时代的那篇硕士论文
- 1937 年,一位 21 岁的学生 Claude Shannon 注意到,他研究的电话继电器所做的事,和八十年前 George Boole 为推理真假而发明的一种代数是同一回事。
- 如果一个开关是一个布尔变量,那么一个电路就是一个表达式,而化简表达式就是从电路里去掉门。门更少意味着更便宜、更快、更省电。
- 他的论文被称为那个世纪最重要的论文。这一页上的一切,都是把那一个想法当作工具来用。
- 这一课讲布尔代数(Boolean algebra)、德摩根定律,以及用眼睛做同样工作的卡诺图(Karnaugh map)。
The notation and the laws
+means OR,·means AND and is often left out, and an overbar means NOT. A truth table 真值表 describes the same thing exhaustively.- Identity: $A + 0 = A$ and $A \cdot 1 = A$. Null: $A + 1 = 1$ and $A \cdot 0 = 0$.
- Idempotent: $A + A = A$. Inverse: $A + \overline{A} = 1$ and $A \cdot \overline{A} = 0$.
- Absorption 吸收律: $A + A\cdot B = A$, because if $A$ is true the whole expression is true regardless of $B$.
记号与定律
+表示 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. · 把每个布尔定律与它说的内容配对。
These laws let you simplify Boolean expressions algebraically before building the circuit. · 这些定律让你在构建电路之前以代数方式简化布尔表达式。
By the absorption law, A + A·B simplifies to ____. · 根据吸收律,A + A·B 化简为 ____。
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. · 若 A 为真,不论 B 如何整个表达式都为真;若 A 为假,两项都为假。B 影响不了结果。
De Morgan's laws
- De Morgan's laws 德摩根定律 are the two the exam asks you to use by name:
- The recipe in words: negate the whole, swap AND and OR, negate each operand.
- They matter practically because they let any expression be rewritten using only NAND gates or only NOR gates, and a chip built from one repeated gate is cheaper to manufacture.
Two expressions, one truth table
德摩根定律
- 德摩根定律(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: · 由德摩根定律,$\overline{A \cdot B}$ 等于:
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$. · 取反整体,把 AND→OR 交换,取反每个操作数:$\overline{A \cdot B} = \overline{A} + \overline{B}$。
Applying De Morgan's law to an expression involves which steps? Select all · 所有 that apply. · 对一个表达式应用德摩根定律包含哪些步骤?选出所有适用的。
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative. · 整体取反、运算符互换、每一项各自取反。顺序无关,因为 AND 和 OR 满足交换律。
Worked example: simplify, and count the gates
- Simplify $Z = A\cdot B + A\cdot\overline{B}$ and say what it saves.
- Factor out $A$: $Z = A\cdot(B + \overline{B})$. By the inverse law $B + \overline{B} = 1$, so $Z = A \cdot 1 = A$.
- The original needs two AND gates, a NOT and an OR: four gates. The simplified expression needs none, just the input $A$.
- Always finish with what the simplification buys: fewer gates, so a cheaper, faster circuit that uses less power.
例题:化简,并数一数门
- 化简 $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}$. · 简化 $A\cdot B + A\cdot\overline{B}$。
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$. · 提出 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? · A·B + A·NOT B 需要两个 AND、一个 NOT 和一个 OR。它化简后的形式需要几个门?
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved. · 它化简为 A 本身,所以输出就是输入,一个门都不需要。省下四个门。
The Karnaugh map
- A Karnaugh map simplifies an expression by grouping adjacent 1s taken from the truth table.
- Rows and columns are labelled in Gray code 格雷码 order,
00, 01, 11, 10, so that adjacent cells differ in exactly one variable. That is the whole trick: it makes the algebra visible as adjacency. - Place a 1 in each cell where the output is 1, then find rectangular groups of 1s whose sides are powers of two: 1, 2, 4, 8. Groups may wrap around the edges.
The bigger the rectangle, the simpler the term
卡诺图
- 卡诺图通过把真值表里相邻的 1 分组来化简表达式。
- 行和列按格雷码(Gray code)顺序
00, 01, 11, 10标注,使得相邻单元恰好只有一个变量不同。这就是全部诀窍:它把代数变成看得见的相邻关系。 - 在输出为 1 的每个单元里填 1,然后找出边长为 2 的幂(1、2、4、8)的矩形 1 组。组可以跨边界绕回。
矩形越大,项越简单
A Karnaugh map simplifies a Boolean expression by: · 一个卡诺图这样简化一个布尔表达式:
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term. · 你把相邻的 1(以格雷码顺序)分组成 2 的幂的矩形;每组变成一个简化的项。
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11? · 卡诺图的行列为什么标成 00、01、11、10 而不是 00、01、10、11?
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work. · 格雷码顺序把代数上的相邻变成位置上的相邻。按计数顺序排,分组规则根本不成立。
Reading a group
- Inside a group, a variable that stays the same survives in the term; a variable that changes disappears.
- So a group of 2 drops one variable, a group of 4 drops two, and a group of 8 drops three. The larger the group, the simpler the term.
- Cover every 1 using as few and as large groups as possible, then OR the group terms together. Groups may overlap, and overlapping is often what allows a larger one.
读一个组
- 在一个组内部,保持不变的变量留在项里;发生变化的变量消失。
- 所以 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 的组消除更多变量,给出一个更简单的项(一个 2 的组去掉一个变量,一个 4 的组去掉两个)。
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes. · 你把相邻的 1 以格雷码顺序分组成 2 的幂的矩形;组越大,它变成的项越简单。
Put the steps of simplifying with a Karnaugh map in order. · 把用卡诺图化简的步骤按顺序排列。
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 1. · 格雷码、填 1、最大的组、去掉变化的、把项 OR 起来。用尽可能少、尽可能大的组覆盖每一个 1。
Worked example: read a two-variable map
- A Karnaugh map for $A$ and $B$ has 1s in the cells $\overline{A}B$ and $AB$. Simplify.
- The two 1s are adjacent: they share the $B = 1$ column, so they group as a rectangle of 2.
- Inside that group $B$ stays 1 throughout, while $A$ changes from 0 to 1. The variable that changes disappears.
- So the whole expression is simply $Z = B$. Compare that with the unsimplified sum of products, $\overline{A}B + AB$, which needs a NOT, two ANDs and an OR.
例题:读一张双变量卡诺图
- 一张关于 $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。
Which method to use
- Boolean algebra is exact and works for any number of variables, but you must spot which law applies.
- A Karnaugh map is mechanical and hard to get wrong for two to four variables, which is what the exam sets, and it shows you the largest grouping directly.
- Both give the same answer. The benefit of the K-map is that simplification becomes looking, not searching for a law.
用哪种方法
- 布尔代数精确,对任意多个变量都适用,但你必须看出该用哪条定律。
- 卡诺图是机械的,在两到四个变量时很难出错——而考试考的正是这个范围——而且它直接把最大的分组显示给你。
- 两者给出同样的答案。卡诺图的好处是化简变成了看,而不是去搜寻一条定律。
Marks that slip away
- De Morgan is negate the whole, swap the operator, negate each part. Changing only the operator is the classic half-answer.
- K-map rows must be in Gray code order,
00, 01, 11, 10. In binary counting order the adjacency is wrong and the grouping fails. - Group sizes are powers of two and may wrap the edges. A group of three is not a group.
- Say what simplifying is for: fewer gates, so cheaper, faster, lower power.
容易丢掉的分
- 德摩根是整体取反、运算符互换、每一项各自取反。只换运算符是典型的半个答案。
- 卡诺图的行必须按格雷码顺序
00, 01, 11, 10。按二进制计数顺序排,相邻关系就错了,分组也就失败。 - 组的大小是2 的幂,并且可以跨边界绕回。三个一组不成组。
- 要说出化简是为了什么:门更少,所以更便宜、更快、更省电。
You've got it
- Boolean algebra rewrites an expression into fewer terms, so the circuit needs fewer gates
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ and $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorption: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- a Karnaugh map groups adjacent 1s from the truth table, with rows and columns in Gray code order so neighbours differ in one variable
- a variable that changes within a group disappears, so bigger groups give simpler terms: cover every 1 with as few, as large, groups as possible
你掌握了
- 布尔代数把表达式改写成更少的项,于是电路需要更少的门
- 德摩根:$\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