Логические схемы
| English | Русский |
|---|---|
| logic circuit/ˈlɒdʒɪk ˈsɜːkɪt/ | логическая схема |
| Boolean expression/ˈbuːlɪən ekˈspreʃn/ | булево выражение |
| problem statement/ˈprɒbləm ˈsteɪtmənt/ | формулировка задачи |
| truth table/truːθ ˈteɪbl/ | таблица истинности |
| sum of products/sʌm ɒv ˈprɒdʌkts/ | сумма произведений |
| half adder/hɑːf ˈædə/ | полуаддитор |
Три датчика, два вентиля, одно решение
- Микроволновая печь нагревает только тогда, когда дверь закрыта и нажата кнопка запуска и таймер не достиг нуля.
- Три датчика дают три сигнала 0/1. Два вентиля AND объединяют их в один сигнал, который включает магнетрон. Откройте дверь, и выход мгновенно упадёт до 0.
- Каждая система безопасности, каждая сигнализация и каждая инструкция процессора — это такое решение, собранное из шести вентилей предыдущего урока.
- Этот урок посвящён сборке и чтению таких схем, а также переходу между четырьмя способами записи одного решения.
Четыре вида одной функции
- Логическая схема — это сеть вентилей, выполняющая булево выражение.
- Одну и ту же функцию можно записать как формулировку задачи на английском языке, как выражение, как схему электрической цепи или как таблицу истинности. Экзамен требует уметь переходить в любом направлении между ними.
- В экзаменационном листе выражения записываются словами,
X = (A AND NOT B) OR (B AND C), и принимаются в алгебраической форме $X = A\overline{B} + BC$, где точка или отсутствие знака обозначают AND, плюс — OR, а черта сверху — NOT. Используйте ту форму, которую требует вопрос.
Вентили, соединённые вместе для выполнения одного булева выражения
От выражения к схеме
- Нарисуйте один вентиль на каждый оператор, начиная с самых внутренних скобок.
- Для
X = (A AND B) OR (NOT C): вентиль AND на A и B, вентиль NOT на проводе C и вентиль OR, объединяющий два результата. - Входы слева, единственный выход справа, каждая линия заканчивается на входе вентиля или на выходе, а выход помечен X.
Один вентиль для каждого оператора в выражении
Логические схемы
вентили объединяются в схемы
У каждого вентиля есть фиксированное правило; последовательное соединение (цепочка) позволяет построить любую схему — начните с одного вентиля.
Для $X = (A \cdot B) + \overline{C}$ и $A=1, B=1, C=1$, чему равно $X$?
$A \cdot B = 1$, и $\overline{C} = 0$. $X = 1 + 0 = 1$.
Разобранный пример: от схемы к выражению
- Идите от входов вперед и помечайте каждый промежуточный выход.
- В схеме ниже B проходит через вентиль NOT. A и NOT B подаются на вентиль AND: назовём его выход P, так что
P = A AND NOT B. B и C подаются на второй вентиль AND:Q = B AND C. - P и Q подаются на вентиль OR, так что
X = P OR Q = (A AND NOT B) OR (B AND C). - Пометка P и Q — это не просто украшение. Это именно то, что позволяет заполнять таблицу истинности по одному вентиль за раз.
Помечайте каждый промежуточный выход перед тем, как писать выражение
В разобранной схеме выход второго вентиля И равен Q = B И ____.
B и C поступают на нижний вентиль И. Подписав этот выход Q, можно заполнить таблицу истинности, обрабатывая по одному вентилю за раз.
От схемы к таблице истинности
- Для $n$ входов существует $2^{n}$ строк: два входа дают 4, три дают 8, четыре дают 16. Перечислите их в порядке двоичного счета.
- Добавьте в таблицу столбец для каждого промежуточного выхода, а не только для финального, чтобы каждую строку можно было проверить по одному вентилю.
- Заполняйте столбцы слева направо: сначала NOT, затем каждый AND, затем OR.
Сколько строк имеет таблица истинности для схемы с 3 входами?
$2^n$ строк; для 3 входов, $2^3 = 8$.
Сколько строк для 4 входов?
$2^4 = 16$ строк.
Разобранный пример: восемь строк
- Схема из предыдущего разобранного примера со столбцами для NOT B, P, Q и X:
| A | B | C | NOT B | P | Q | X |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
- X равен 1 в четырёх из восьми строк. Проверьте любую строку по выражению: строка 1 0 0 имеет A = 1 и NOT B = 1, поэтому P = 1, следовательно X = 1.
Для X = (A AND NOT B) OR (B AND C), какие строки входов дают X = 1? Отметьте все подходящие варианты.
Строка 011 дает Q = 1; строка 100 дает P = 1. В строке 110 B = 1 обнуляет P, а C = 0 обнуляет Q; в строке 001 оба члена равны 0.
Таблица истинности к выражению: сумма произведений
- Сумма произведений: для каждой строки, где выход равен 1, запишите AND входных сигналов, ставя NOT на тех входах, которые равны 0 в этой строке. Затем объедините эти слагаемые через OR.
- Таблица, которая равна 1 только при (A = 0, B = 1) и (A = 1, B = 0), даёт
(NOT A AND B) OR (A AND NOT B), что в точности равно A XOR B. - Упрощайте только если об этом просят; неупрощённая сумма произведений даёт баллы.
В методе «сумма произведений» для каждой строки, где выход равен 1, вы записываете:
Каждая строка с 1 становится членом И (без 0-входов); затем все эти члены соединяются дизъюнкцией (ИЛИ).
В методе «сумма произведений» вы соединяете дизъюнкцией (ИЛИ) член И для каждой строки, где выход равен 1.
Каждая строка с выходом 1 становится членом И (с отрицанием 0-входов); объединение этих членов через ИЛИ дает выражение, которое равно 1 ровно на тех строках.
Полусумматор
- Сложение двух битов даёт бит суммы и бит переноса: 1 + 1 = 10 в двоичной системе.
- Столбец суммы содержит 0, 1, 1, 0, что соответствует XOR. Столбец переноса содержит 0, 0, 0, 1, что соответствует AND. Два вентиль образуют полусумматор.
- Это стандартный пример считывания вентилей прямо с таблицы истинности и первый элемент арифметического устройства каждого процессора.
Каждая пара входов проходит через вентили: XOR даёт сумму, AND даёт перенос, так что 1 + 1 = 10
Полусумматор
Подключите XOR и И к одним и тем же двум входам: XOR даст бит суммы, И — перенос. Нажмите A и B.
В полусумматоре какой вентиль производит бит переноса?
Перенос равен 1 только когда оба бита равны 1, что соответствует И. Сумма равна 1, когда биты различаются, что соответствует ИСКЛЮЧАЮЩЕМУ ИЛИ.
Из формулировки задачи
- Переводите английский текст в булевые выражения по одному предложению, прежде чем рисовать схемы.
- "A и B" — это
A AND B. "A или B, или оба" — этоA OR B. "ровно один из A и B" — этоA XOR B. - "ни A, ни B" — это
A NOR B. "не оба" — этоA NAND B. "если не" обычно означает AND NOT.
Соотнесите каждую английскую фразу с единственным вентилем, который её реализует.
both = И, differ = ИСКЛЮЧАЮЩЕЕ ИЛИ, neither = ИЛИ-НЕ, not-both = И-НЕ.
Разобранный пример: сигнал тревоги машины
- Тревога X срабатывает, когда страж открыт (A = 1) и либо двигатель работает (B = 1), либо температура высока (C = 1).
- "Либо B, либо C" — это
B OR C. "A и это" — этоX = A AND (B OR C). Скобки вокруг OR обязательны. - X = 1 требует A = 1 и хотя бы одного из B, C равного 1: строки (1, 0, 1), (1, 1, 0) и (1, 1, 1). Три строки из восьми, и A = 0 никогда не может вызвать тревогу.
- Схема представляет собой один вентиль OR на входах B и C, подающий сигнал на вентиль AND вместе с A.
Для сигнала тревоги X = A AND (B OR C), тревога может прозвучать при A = 0, при условии, что B и C равны 1.
AND с A означает, что A = 1 необходимо в каждой строке, где X = 1. При A = 0 выходной сигнал равен 0, независимо от значений B и C.
Потерянные баллы
A AND B OR Cбез скобок неоднозначен, и экзаменатор считает это ошибкой в понимании вами задачи. Ставьте скобки у OR перед тем, как делать с ним AND.- Провод, идущий никуда, или выход без подписи, лишит вас баллов даже при правильных вентилях.
- НЕ на входе обозначается как отдельный вентиль на схеме, а не черта над буквой.
- Три входа означают восемь строк. Таблица с меньшим числом строк не может быть засчитана как полная.
Вы поняли
- выражение → схема: один вентиль на оператор, внутренние скобки первыми, входы слева, помеченный выход справа
- схема → выражение: подпишите каждый промежуточный выход (P, Q) и объедините их; схема → таблица истинности: $2^{n}$ строк со столбцом на каждый вентиль
- таблица истинности → выражение: сумма произведений, один AND-член на каждую строку с выходом 1, объединённых через OR; XOR + AND образуют полусумматор
- задача → булева логика: ровно один = XOR, ни один = NOR, не оба = NAND; ставьте скобки у OR внутри AND