Логические вентили: И, ИЛИ, НЕ

Урок о том, как абстрактные операции И, ИЛИ, НЕ становятся физическими деталями, из которых собран любой процессор.

Логический вентиль (gate) — это электронная схема, которая принимает на вход один или несколько логических сигналов (0 или 1) и выдаёт ровно один выходной сигнал по жёстко заданному правилу — фактически реализует одну строку таблицы истинности.

В предыдущих разделах мы записывали логику формулами: $A \land B$, $A \lor B$, $\neg A$. Это была чистая математика на бумаге. Но та же самая логика управляет миллиардами транзисторов в вашем телефоне. Связующее звено между формулой и кремнием — именно вентиль. Понять вентили — значит понять, как из закона алгебры логики получается работающее железо, и это прямо разбирается в задачах ЕГЭ про схемы и сумматоры.

Зачем это нужно

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

Базовые вентили: И, ИЛИ, НЕ

Три кита, из которых выводится остальное.

Вентиль НЕ (NOT, инвертор)

Один вход, один выход. Переворачивает сигнал: из 0 делает 1, из 1 делает 0. Формула: $\neg A$ (часто пишут $\bar{A}$). На схемах рисуется треугольником с кружком на выходе; именно кружок означает «инверсию».

Вентиль И (AND)

Выход равен 1 только тогда, когда все входы равны 1. Достаточно одного нуля на входе — на выходе ноль. Формула: $A \land B$. По смыслу это умножение: $1 \cdot 1 = 1$, а $1 \cdot 0 = 0$.

Вентиль ИЛИ (OR)

Выход равен 1, если хотя бы один вход равен 1. Ноль на выходе бывает в единственном случае — когда все входы нули. Формула: $A \lor B$.

Исключающее ИЛИ (XOR) и его роль

Очень важный вентиль, особенно для арифметики. XOR (исключающее ИЛИ) выдаёт 1, когда входы различны, и 0, когда они одинаковы. Формула: $A \oplus B$.

XOR удобно представлять как «детектор различия» или как сложение по модулю 2: $A \oplus B = (A + B) \bmod 2$. Через базовые операции его можно выразить так:

$$ A \oplus B = (A \land \neg B) \lor (\neg A \land B) $$

Именно поэтому XOR лежит в основе сложения двоичных чисел — к этому мы вернёмся в уроке про сумматор.

Универсальные вентили NAND и NOR

Здесь начинается самое красивое. NAND — это И с инверсией на выходе ($\neg(A \land B)$), а NOR — ИЛИ с инверсией ($\neg(A \lor B)$). На схеме это знакомые символы И или ИЛИ, но с кружком инверсии на выходе.

Их называют функционально полными, или универсальными: из одних только NAND (или одних только NOR) можно собрать любой другой вентиль, а значит и любую логическую схему вообще. Например, инвертор из NAND получается, если подать один сигнал на оба входа:

$$ \neg A = \neg(A \land A) = A \,\overline{\land}\, A $$

А обычное И — это NAND, за которым стоит инвертор (то есть ещё один NAND): $A \land B = \neg(\neg(A \land B))$. Для производства это золото: завод может выпускать чипы из одного типа вентиля и собирать из него всё подряд.

Как это работает

Физически вентиль — это несколько транзисторов, работающих как управляемые ключи. В технологии CMOS, на которой сделана почти вся современная электроника, инвертор — это всего два транзистора: один пропускает ток к выходу при входном нуле, второй — заземляет выход при входной единице. NAND и NOR требуют по 4 транзистора, а вот «чистые» И и ИЛИ внутри устроены как NAND/NOR плюс инвертор — то есть дороже. Поэтому инженеры реально предпочитают строить схемы на NAND и NOR: так получается меньше транзисторов и быстрее сигнал. Логическая «универсальность» NAND здесь не теория, а инженерная экономия.

Проверим таблицу истинности XOR программой — пусть компьютер сам переберёт все входы.

def XOR(a, b):
    return (a and not b) or (not a and b)

print("A B | XOR")
for a in (0, 1):
    for b in (0, 1):
        print(a, b, "|", int(XOR(a, b)))

Вывод:

A B | XOR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Частые ошибки

• Путают ИЛИ и XOR. Обычное ИЛИ при двух единицах даёт 1, а XOR — 0. В русском «или» бывает разговорным исключающим («чай или кофе»), но логическое $\lor$ — всегда включающее.
• Забывают про кружок инверсии. Кружок на выходе превращает И в NAND, а ИЛИ в NOR. Пропустишь его при чтении схемы — получишь противоположный результат.
• Думают, что у И единица «по умолчанию». Наоборот: для И единственная единица на выходе — когда все входы единицы; для ИЛИ единственный ноль — когда все входы нули.
• Считают XOR «суммой». XOR — это сумма по модулю 2 (без переноса): $1 \oplus 1 = 0$, а не 2. Перенос придётся ловить отдельным вентилем И.

Итоги

• Вентиль — физическая реализация одной булевой операции; вход и выход принимают только 0 или 1.
• Базовые вентили: НЕ ($\neg A$), И ($A \land B$), ИЛИ ($A \lor B$); XOR ($A \oplus B$) выдаёт 1 при различных входах.
• NAND ($\neg(A \land B)$) и NOR ($\neg(A \lor B)$) универсальны: из любого из них собирается вся логика.
• На практике железо строят на NAND/NOR — так дешевле по транзисторам и быстрее.