Boolean algebra and Karnaugh maps
Введено| 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/ | код Грея |
Магистерская диссертация, построившая цифровую эпоху
- В 1937 году 21-летний студент по имени Клод Шеннон заметил, что телефонные реле, которые он изучал, выполняли то же самое, что и алгебра, придуманная Джорджем Булем восемьдесят лет назад для рассуждений о истине и лжи.
- Если переключатель — это булева переменная, то схема — это выражение, а упрощение выражения удаляет вентили из схемы. Меньше вентилей — дешевле, быстрее и меньше энергопотребление.
- Его диссертацию называют самой важной за столетие. Всё, что приведено на этой странице, — это одно это применение одной идеи.
- Этот урок посвящён булевой алгебре, законам де Моргана и карте Карно, которая выполняет ту же работу визуально.
Обозначения и законы
+означает ИЛИ,·означает И (и часто опускается), а черта сверху означает НЕ. Таблица истинности описывает то же самое исчерпывающим образом.- Идентичность: $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$.
- Поглощение: $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.
Законы де Моргана
- Законы де Моргана — это два закона, которые экзамен требует применять по названию:
- Алгоритм словами: инвертировать всё, поменять местами И и ИЛИ, инвертировать каждый операнд.
- Они важны практически, так как позволяют переписать любое выражение, используя только вентили 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$.
- Исходная схема требует двух вентилей И, одного НЕ и одного ИЛИ: четыре вентиля. Упрощённое выражение не требует ничего, кроме входа $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, взятых из таблицы истинности.
- Строки и столбцы обозначены в порядке кода Грея,
00, 01, 11, 10, чтобы соседние ячейки отличались ровно в одной переменной. Это весь секрет: он делает алгебру видимой через смежность. - 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.

Чем больше прямоугольник, тем проще терм
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$ содержит 1 в ячейках $\overline{A}B$ и $AB$. Упростите.
- Два 1 соседние: они находятся в одном столбце $B = 1$, поэтому группируются как прямоугольник из 2.
- Внутри этой группы $B$ остаётся равным 1 на протяжении всего процесса, тогда как $A$ меняется от 0 к 1. Переменная, которая меняется, исчезает.
- Таким образом, всё выражение просто равно $Z = B$. Сравните это с неупрощённой суммой произведений, $\overline{A}B + AB$, которое требует одного НЕ, двух И и одного ИЛИ.
Какой метод использовать
- Булева алгебра точна и работает для любого количества переменных, но вы должны распознать, какой закон применяется.
- Карта Карно механистична и её трудно ошибиться для двух–четырёх переменных, что и требуется на экзамене, и она напрямую показывает максимально возможное объединение.
- Оба метода дают одинаковый ответ. Преимущество карты Карно в том, что упрощение становится просмотром, а не поиском закона.
Потерянные баллы
- Де Морган — это инвертировать всё, поменять оператор, инвертировать каждую часть. Изменение только оператора — классическая половинчатая ошибка.
- Строки карты Карно должны быть в порядке кода Грея,
00, 01, 11, 10. В порядке двоичного счета смежность нарушена, и объединение не работает. - Размеры групп — степени двойки и могут заворачиваться за края. Группа из трёх элементов не является допустимой группой.
- Укажите, зачем нужно упрощение: меньше вентилей, значит, дешевле, быстрее, ниже энергопотребление.
Вы поняли
- Булева алгебра переписывает выражение в меньшее количество членов, поэтому схеме нужны меньше вентилей
- Законы де Моргана: $\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 как можно меньшим числом, как можно больших групп