Построение схем логических элементов

В предыдущей лекции мы изучили четыре основных логических элемента. В этой лекции мы соединим их вместе, чтобы построить схемы, решающие реальные задачи.

Один логический элемент подобен винту — его функция ограничена сама по себе. Но соедините их, и вы сможете построить сколь угодно сложные функции.


Бытовая аналогия: строительство замка из кубиков Lego

Представьте, что перед вами четыре цвета кирпичиков LEGO:

  • Зелёный блок = элемент И: Ток течёт только тогда, когда оба конца соединены
  • Оранжевый блок = элемент ИЛИ: Ток течёт, когда подключён хотя бы один конец
  • Красный блок = элемент НЕ: Включённое становится выключенным, выключенное становится включённым
  • Фиолетовый блок = элемент исключающее ИЛИ: Ток течёт, когда два конца находятся в разных состояниях

Что можно построить из этих кирпичиков?

устройство для голосованияТри человека голосуют, и решает большинство. Это типичная комбинационная логическая схема — просто соедините элементы И/ИЛИ, чтобы реализовать её.

кодовый замокПравильные клавиши должны быть нажаты одновременно, чтобы разблокировать. По сути, это каскад элементов И — каждая клавиша соответствует входу, и только когда все входы равны 1, выход становится равным 1.

сигнализацияЕсли срабатывает любой датчик, звучит сигнал тревоги. По сути, это применение элементов ИЛИ — пока хотя бы один датчик выдаёт 1, сигнализация звучит.


Комбинационная логика против последовательностной логики

Прежде чем мы углубимся в построение схем, давайте разграничим два важных понятия:

TypeОсобенностиВыход зависит отЕсть ли у неё память?Примеры
Комбинационная логикаВыход определяется только текущим входомзначение текущего входанетСумматор, мажоритарный элемент, дешифратор
Последовательностная логикаВыход определяется текущими входами + историческим состояниемТекущий вход + ранее сохранённые значенияДаСчётчик, регистр, конечный автомат

Эта лекция посвящена комбинационной логике.Последовательностная логика будет подробно рассмотрена в лекции 9.

Простой способ их различать: комбинационная логика — это «что подашь на вход, то и получишь на выходе» (как математическая функция); последовательностная логика — это «я всё ещё помню, что ты подавал раньше» (как человеческая память).


Методология построения схемы: трёхшаговый метод

Существует универсальный трёхшаговый процесс построения любой комбинационной логической схемы с помощью логических элементов:

  1. Составьте таблицу истинностиШаг 1: Перечислите все комбинации входов и запишите ожидаемый выход для каждого случая.
  2. Запишите логическое выражениеШаг 2: Для каждой строки, где выход равен 1, запишите соответствующий «член-произведение» (комбинацию входов через AND), затем соедините все члены-произведения операцией OR. Это называется формой «сумма произведений».
  3. Нарисуйте схему / Напишите кодШаг 3: Преобразуйте логическое выражение в соединение логических элементов.

Давайте отработаем этот метод на трёх примерах, от простого к сложному.


Случай 1: Кодовый замок с двумя входами

ТребованияСлучай 1: Спроектируйте простую схему проверки пароля. Есть два входа A и B. Только когда A=1 и B=1, выход становится 1 (разблокировка); в противном случае выход равен 0 (заблокировано).

Это требование на самом деле представляет собой просто элемент AND. Но мы можем использовать его, чтобы продемонстрировать трёхшаговый метод:

Шаг 1: Таблица истинности

ABОжидаемый выход Y
000 (заблокировано)
010 (заблокировано)
100 (заблокировано)
111 (разблокировано)

Шаг 2: Логическое выражение

Только последняя строка имеет выход 1. Соответствующий член произведения: A И B.

Итак: Y = A И B

Шаг 3: Реализация схемы

Вам нужен только один элемент И, с входами A и B и выходом Y.

Слишком просто? Давайте рассмотрим более практичный пример.


Случай 2: Мажоритарный элемент (основной случай)

ТребованияТри человека (A, B, C) голосуют по предложению (1 означает одобрение, 0 — отклонение). Предложение принимается, когда как минимум два человека одобряют (выход 1).

Это классический мажоритарный элемент с тремя входами и обязательный для изучения случай в учебниках по цифровым схемам.

Шаг 1: Составьте таблицу истинности

Три входа дают в сумме 23= 8 комбинаций:

ABCЧисло голосов заПройдено/не пройдено: YОписание
00000Никто не одобряет
00110Только C одобряет
01010Только B одобряет
01121B и C одобряют
10010Только A одобряет
10121A и C одобряют
11021A и B одобряют
11131Принято единогласно

Шаг 2: Запишите логическое выражение

Найдите строки, в которых выход равен 1 (строки 4, 6, 7, 8), и запишите по одному члену произведения для каждой строки:

  • Строка 4: NOT(A) AND B AND C
  • Строка 6: A AND NOT(B) AND C
  • Строка 7: A AND B AND NOT(C)
  • Строка 8: A AND B AND C

используйте OR-соединение:Y = (NOT(A) AND B AND C) OR (A AND NOT(B) AND C) OR (A AND B AND NOT(C)) OR (A AND B AND C)

Это выражение может показаться немного длинным, но логически оно очень ясно:Y равно 1 тогда и только тогда, когда любые два или три входа равны 1。

Шаг 3: Нарисуйте схему цепи с помощью SVG

three input linesA B C AND gate 1: A AND B ANDConnect to AND1 AND gate 2: B AND C AND AND gate 3: A AND C AND OR gate (combining the outputs of three AND gates) OR Output line YTagsFigure: Three-input majority voter circuit structure

Три элемента AND проверяют, является ли каждая из трёх пар "AB", "BC" и "AC" равной 11, затем элемент OR объединяет результаты.


Интерактивная демонстрация: реализация мажоритарного элемента на Python

Пример

# Мажоритарный элемент с тремя входами (пример демонстрации)
# Требование: голосуют три человека; решение проходит (выход 1), только когда как минимум два одобряют (1).

# ----- Повторное использование базовых логических элементов из лекции 6 -----
def AND(a, b):
    return 1 if a == 1 and b == 1 else 0

def OR(a, b):
    return 1 if a == 1 or b == 1 else 0

def NOT(a):
    return 1 if a == 0 else 0


# ----- Метод 1: стандартная форма суммы произведений (SOP) -----
def majority_voter_sop(a, b, c):
    """
Реализация мажоритарного элемента через сумму произведений.
Непосредственно выведите из таблицы истинности: найдите все строки, в которых выход равен 1,
Запишите по одному терму AND на строку, затем соедините их с помощью OR.
    """

    term1 = AND(AND(NOT(a), b), c)       # ~A·B·C
    term2 = AND(AND(a, NOT(b)), c)       # A·~B·C
    term3 = AND(AND(a, b), NOT(c))       # A·B·~C
    term4 = AND(AND(a, b), c)            # A·B·C
    return OR(OR(term1, term2), OR(term, term4))


# ----- Метод 2: оптимизированная упрощённая форма -----
def majority_voter_optimized(a, b, c):
    """
Оптимизированная реализация мажоритарного элемента: Y = AB + BC + AC.
Эта форма требует меньше вентилей, но логически эквивалентна первому методу.

Почему это эквивалентно?
После раскрытия SOP-формы метода 1 её можно упростить, используя закон поглощения булевой алгебры:
    ~A·B·C + A·~B·C + A·B·~C + A·B·C
    = (~A·B·C + A·B·C) + (A·~B·C + A·B·C) + (A·B·~C + A·B·C)
    = B·C·(~A+A) + A·C·(~B+B) + A·B·(~C+C)
    = B·C + A·C + A·B
    """

    return OR(OR(AND(a, b), AND(b, c)), AND(a, c))


# ============================================
# Вывести полную таблицу истинности и сравнить два метода
# ============================================
print("=" * 60)
print(Таблица истинности мажоритарного голосования с тремя входами (ПРИМЕР демонстрации))
print("=" * 60)
print()
print("┌───┬───┬───┬────────┬──────────┬──────────┐")
print(│ A │ B │ C │ Пройдено? │ Метод SOP │ Метод оптимизации │)
print("├───┼───┼───┼────────┼──────────┼──────────┤")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            count = a + b + c
            passed = "Пройдено" if count >= 2 else "Не пройдено"
            sop = majority_voter_sop(a, b, c)
            opt = majority_voter_optimized(a, b, c)
            print(f"│ {a} │ {b} │ {c} │ {passed} │ {sop} │ {opt} │")
print("└───┴───┴───┴────────┴──────────┴──────────┘")

# ============================================
# Статистика использования логических элементов
# ============================================
print("\n" + "=" * 60)
print(" Сравнение количества логических элементов, используемых двумя методами")
print("=" * 60)
print()
print(Метод 1 (полная форма SOP):)
print(Элементы НЕ: 3 (~A, ~B, ~C))
print(Элементы И: 4 (четыре терма И, каждый требует 2 двухвходовых элемента И))
print(Элемент ИЛИ: 3 (объединение четырёх произведений))
print(Итого: примерно 14 вызовов базовых логических элементов)
print()
print("Метод 2 (оптимизированная форма Y = AB + BC + AC):")
print(Элементы И: 3 (AB, BC, AC))
print(Элемент ИЛИ: 2 (объединение трёх произведений))
print(" Итого: 5 вызовов базовых логических элементов")
print()
print(После оптимизации число вентилей сокращается примерно на 65%!)
print("В этом заключается инженерная ценность упрощения булевой алгебры.")

Обратите внимание на процесс преобразования таблицы истинности в логическое выражение. Это один из ключевых навыков в проектировании цифровых схем: увидев таблицу истинности, можно записать выражение; увидев выражение, можно нарисовать схему. Эти три представления взаимно однозначно соответствуют друг другу.


Пример 3: одноразрядный компаратор

ТребованияСравнить два 1-битных двоичных числа A и B. Вывести три сигнала: A>B, A=B, A<B

Это очень важная базовая схема — многобитные компараторы и условные проверки в процессорах развились отсюда.

Шаг 1: Таблица истинности

ABA > BA = BA < B
00010
01001
10100
11010

Шаг 2: Логическое выражение

Посмотрите на таблицу истинности:

  • A > B равно 1 тогда и только тогда, когда: A=1 AND B=0. Следовательно: Greater = A AND NOT(B)
  • A = B равно 1 тогда и только тогда, когда: A и B одинаковы. Поэтому: Equal = NOT(A XOR B), или, иначе говоря, Equal = (A AND B) OR (NOT(A) AND NOT(B))
  • A < B равно 1 тогда и только тогда, когда: A=0 AND B=1. Следовательно: Less = NOT(A) AND B

Обратите внимание, что определение A = B тесно связано с элементом XOR. Выход XOR, равный 1, означает "различны"; взятие NOT от него даёт "равны".

Шаг 3: реализация в коде

Пример

# 1-битный компаратор (демонстрационный пример)
# Сравнение двух 1-битных двоичных чисел A и B

def AND(a, b):
    return 1 if a == 1 and b == 1 else 0

def OR(a, b):
    return 1 if a == 1 or b == 1 else 0

def NOT(a):
    return 1 if a == 0 else 0


def one_bit_comparator(a, b):
    """
Однобитный компаратор: сравнивает A и B.
Возвращает кортеж (Greater, Equal, Less).
    """

    greater = AND(a, NOT(b))   # A > B: A=1 и B=0
    less = AND(NOT(a), b)      # A < B: A=0 и B=1
    # A = B: ни больше, ни меньше
    # Эквивалентно NOT(A XOR B), здесь используется другая реализация
    equal = AND(NOT(greater), NOT(less))
    return (greater, equal, less)


# Вывести таблицу истинности
print("=" * 50)
print(Таблица истинности одноразрядного компаратора (ПРИМЕР демонстрации))
print("=" * 50)
print()
print("┌───┬───┬────────┬────────┬────────┐")
print("│ A │ B │ A > B  │ A = B  │ A < B  │")
print("├───┼───┼────────┼────────┼────────┤")
for a in [0, 1]:
    for b in [0, 1]:
        gt, eq, lt = one_bit_comparator(a, b)
        print(f"│ {a} │ {b} │ {gt} │ {eq} │ {lt} │")
print("└───┴───┴────────┴────────┴────────┘")

# Проверка некоторых полезных сценариев
print("\nТестовый сценарий: ")
a_test, b_test = 1, 0
gt, eq, lt = one_bit_comparator(a_test, b_test)
print(f"A={a_test}, B={b_test}: A>B={gt}, A=B={eq}, A<B={lt}")
print(f"Интерпретация: A больше B" if gt else ("A равно B" if eq else "A меньше B"))

Случай 4: дешифратор 2-в-4

ТребованияПодайте на вход 2-битное двоичное число (00, 01, 10, 11) и сделайте так, чтобы ровно одна из соответствующих 4 выходных линий была равна 1, а остальные — 0.

Дешифратор — ключевой компонент в CPU — когда CPU хочет выбрать регистр, он по сути использует дешифратор.

Таблица истинности

A1A0Y0Y1Y2Y3
001000
010100
100010
110001

логическое выражение

  • Y0 = NOT(A1) AND NOT(A0)
  • Y1 = NOT(A1) AND A0
  • Y2 = A1 AND NOT(A0)
  • Y3 = A1 AND A0

Пример

# Дешифратор 2-4 (пример демонстрации)
# Вход: 2-битное двоичное число A1 A0
# Выход: ровно одна из 4 линий равна 1

def AND(a, b):
    return 1 if a == 1 and b == 1 else 0

def NOT(a):
    return 1 if a == 0 else 0


def decoder_2to4(a1, a0):
    """
Линейный дешифратор 2-в-4.
Верните список [Y0, Y1, Y2, Y3],
Ровно один из них равен 1, остальные равны 0.
    """

    Y0 = AND(NOT(a1), NOT(a0))  # 00 → Y0
    Y1 = AND(NOT(a1), a0)       # 01 → Y1
    Y2 = AND(a1, NOT(a0))       # 10 → Y2
    Y3 = AND(a1, a0)            # 11 → Y3
    return [Y0, Y1, Y2, Y3]


# Вывести таблицу истинности
print("=" * 50)
print(Таблица истинности дешифратора 2-4 (ПРИМЕР Демо))
print("=" * 50)
print()
print("┌────┬────┬────┬────┬────┬────┐")
print("│ A1 │ A0 │ Y0 │ Y1 │ Y2 │ Y3 │")
print("├────┼────┼────┼────┼────┼────┤")
for a1 in [0, 1]:
    for a0 in [0, 1]:
        Y = decoder_2to4(a1, a0)
        print(f"│ {a1}  │ {a0}  │ {Y[0]}  │ {Y[1]}  │ {Y[2]}  │ {Y[3]}  │")
print("└────┴────┴────┴────┴────┴────┘")

# Показать реальный сценарий использования
print("\nПрактический сценарий применения: использование дешифратора для выбора регистров)
registers = ["R0", "R1", "R2", "R3"]
for a1 in [0, 1]:
    for a0 in [0, 1]:
        Y = decoder_2to4(a1, a0)
        idx = Y.index(1)          # Найти, какая выходная линия равна 1
        print(fАдрес A1A0={a1}{a0} → выбирает регистр {registers[idx]})

Дешифратор — это классическая схема «один-ко-многим». Его аналог — мультиплексор (MUX), который работает по принципу «многие-к-одному». Оба очень часто используются при проектировании тракта данных CPU. Дешифратор используется для «выбора цели» (например, в какой регистр выполнять запись), а мультиплексор — для «выбора источника» (например, из какого регистра АЛУ считывает данные).


Универсальные логические элементы: чем особенны NAND и NOR

В реальном производстве микросхем элементы NAND и NOR более «низкоуровневые», чем элементы AND и OR.

Элемент NAND = AND + NOTТо есть сначала выполняется AND, затем инверсия. NAND и NOR называют «универсальными логическими элементами», потому что каждый из них по отдельности может реализовать все булевы функции.

Почему микросхемы предпочитают NAND/NOR? Потому что в КМОП-технологии:

  • Элемент NAND требует всего 4 транзистора, а элемент AND — 6 (AND = NAND + NOT).
  • У элементов NAND выше скорость переключения
  • Поэтому функция AND в реальных микросхемах реализуется на низком уровне с помощью NAND + NOT.

Далее проверим «универсальность» элемента NAND:

Пример

# Доказательство универсальности элемента NAND (демонстрационный пример)
# Один элемент NAND может реализовать три основные функции: NOT, AND, OR

def NAND(a, b):
    """Элемент NAND: результат AND инвертируется.
Y = 0 тогда и только тогда, когда a=1 и b=1"""

    return 0 if a == 1 and b == 1 else 1


Реализуйте NOT с помощью NAND: NOT(A) = NAND(A, A)
def NOT_from_NAND(a):
    return NAND(a, a)


# используйте NAND для реализации AND:AND(A,B) = NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B))
def AND_from_NAND(a, b):
    nand_ab = NAND(a, b)
    return NAND(nand_ab, nand_ab)


# Реализуйте OR с помощью NAND: OR(A,B) = NAND(NOT(A), NOT(B))
def OR_from_NAND(a, b):
    return NAND(NOT_from_NAND(a), NOT_from_NAND(b))


# ============================================
# Проверка
# ============================================
print("=" * 60)
print(Демонстрация универсальности вентилей NAND (пример демонстрации).)
print("=" * 60)

print("\n[Проверка: NOT реализовано с помощью NAND]")
for a in [0, 1]:
    expected = 1 if a == 0 else 0
    actual = NOT_from_NAND(a)
    print(f" A={a}: NOT_from_NAND = {actual}, ожидаемое = {expected}, {'Успех' if actual == expected else 'Провал'}")

print("\n[Проверка: AND реализовано с помощью NAND]")
for a in [0, 1]:
    for b in [0, 1]:
        expected = 1 if a == 1 and b == 1 else 0
        actual = AND_from_NAND(a, b)
        print(f" A={a}, B={b}: AND_from_NAND = {actual}, ожидаемое = {expected}, {'Успех' if actual == expected else 'Провал'}")

print("\n[Проверка: OR реализовано с помощью NAND])
for a in [0, 1]:
    for b in [0, 1]:
        expected = 1 if a == 1 or b == 1 else 0
        actual = OR_from_NAND(a, b)
        print(f" A={a}, B={b}: OR_from_NAND = {actual}, period望 = {expected}, {'Through' if actual == expected else 'failure'}")

print("\nВывод: для построения ЛЮБОЙ булевой функции нужны только вентили NAND.)
print(Вот почему в курсе nand2tetris можно построить целый компьютер, начиная с вентилей NAND.)

nand2tetris (From NAND to Tetris) — известный курс по информатике. Он предлагает вам шаг за шагом построить процессор, память и операционную систему, используя только вентили NAND, а затем запустить игру «Тетрис». Если вам интересны низкоуровневые детали компьютеров, очень рекомендую.


Интерактивная демонстрация: конструктор схемы мажоритарного голосования (пример демонстрации vis-network)

Используйте нижеvis-networkОна визуализирует схему мажоритарного голосования с тремя входами (Y = AB + BC + AC).Щёлкните входные узлы A, B, C, чтобы переключать 0/1, схема автоматически вычислит и обновит цвета всех проводов —Красныйозначает, что сигнал равен 1,серыйозначает, что сигнал равен 0.

Мажоритарный элемент с тремя входами (щёлкайте по узлам A/B/C, чтобы переключать)

A=0, B=0, C=0 → Не прошло (требуется как минимум 2 голоса «за»)
Входной узел A Входной узел B Входной узел C Вентиль AND Вентиль OR Выход Y
Другие расширения