Булева алгебра и карты Карно
| English | Русский |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | Булева алгебра |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | законы де Моргана |
| Karnaugh map/ˈkɑːnɔː mæp/ | карта Карно |
| truth table/truːθ ˈteɪbl/ | таблица истинности |
| absorption/əbˈsɔːpʃn/ | поглощение |
| Gray code/ɡreɪ kəʊd/ | код Грея |
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.
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$.
Сопоставьте каждый закон булевой алгебры с его содержанием.
Эти законы позволяют упрощать булевы выражения алгебраически перед сборкой схемы.
По закону поглощения A + A·B упрощается до ____.
Если 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
Булева алгебра
A·B, A+B, Ā …
Булева алгебра — это просто эти логические элементы, записанные как выражения — сравните таблицы истинности.
По закону де Моргана $\overline{A \cdot B}$ равно:
Отрицать всё, поменять местами AND→OR, отрицать каждый операнд: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Какие шаги необходимо выполнить при применении закона де Моргана к выражению? Выберите все подходящие варианты.
Отрицать всё, поменять оператор, отрицать каждую часть. Порядок не важен, так как 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.
Упростите $A\cdot B + A\cdot\overline{B}$.
Вынести A за скобки: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B требует двух вентилей AND, одного NOT и одного OR. Сколько вентилей требуется для его упрощенной формы?
Оно упрощается до 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 (в порядке кода Грея) в прямоугольники размерами степени двойки; каждая группа становится упрощенным членом выражения.
Почему строки и столбцы карты Карно обозначены как 00, 01, 11, 10, а не 00, 01, 10, 11?
Порядок кода Грея делает алгебраическую смежность физической смежностью. В порядке счета правило группировки просто не работало бы.
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.
В карте Карно большая группа смежных 1 устраняет больше переменных, давая более простое выражение (группа из 2 убирает одну переменную, группа из 4 — две).
Объединяйте смежные 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.
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.
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