Штрих Шеффера и стрелка Пирса: NAND и NOR в логике

В классической булевой алгебре три основные операции - конъюнкция ($\land$), дизъюнкция ($\lor$) и отрицание ($\lnot$) - образуют полный базис: любую булеву функцию можно записать через них. Но можно ли обойтись одной-единственной операцией? Оказывается, да. Именно это и делают штрих Шеффера (NAND) и стрелка Пирса (NOR): каждый из них в отдельности уже функционально полон. Ниже разберём, что означают эти операции, как устроены их таблицы истинности и как через один базовый элемент воспроизвести весь арсенал классической логики. Покрутите калькулятор - он сразу покажет значения NAND и NOR для любой пары входов и формулы разложения основных операций.

Определения и таблицы истинности

Штрих Шеффера (обозначение $A | B$ или $A \uparrow B$, читается «A штрих B» или «NAND») определяется как отрицание конъюнкции:

$A | B \;=\; \lnot(A \land B).$

Операция принимает значение 0 только тогда, когда оба аргумента равны 1; во всех остальных случаях результат равен 1. Название дано в честь Генри Моуриса Шеффера, который в 1913 году доказал, что эта единственная операция порождает всю классическую логику высказываний.

Стрелка Пирса (обозначение $A \downarrow B$, читается «A стрелка B» или «NOR») - это отрицание дизъюнкции:

$A \downarrow B \;=\; \lnot(A \lor B).$

Результат равен 1 только тогда, когда оба аргумента равны 0. Назвать операцию в честь логика Чарльза Сандерса Пирса предложил Бертран Рассел - сам Пирс использовал этот символ ещё в 1880-х, хотя в его рукописях он не получил широкого распространения сразу.

Рассчитать для своей задачи

Совместная таблица истинности штриха Шеффера и стрелки Пирса:

Характерная черта NAND - он выдаёт 0 только при входах 1,1; характерная черта NOR - он выдаёт 1 только при входах 0,0. Именно этим «крайним» поведением обе операции и отличаются от привычных AND и OR.

Функциональная полнота: что это и почему важно

Говорят, что набор операций функционально полон (образует полный базис), если любую булеву функцию от любого числа переменных можно выразить через операции из этого набора. Классический полный базис - $\{\lnot, \land\}$ или $\{\lnot, \lor\}$. Добавление избыточных операций не нарушает полноты, но делает формулы короче.

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

Рассчитать для своей задачи

Доказательство полноты строится по шагам: сначала показывают, что через данную операцию можно получить отрицание, затем - конъюнкцию или дизъюнкцию, а поскольку $\{\lnot, \land\}$ уже полный базис, задача решена.

Как выразить NOT, AND и OR через NAND

Все три классические операции получаются из штриха Шеффера за 1-3 шага:

Отрицание ($\lnot A$): подаём один и тот же вход на оба входа NAND:

$\lnot A \;=\; A | A.$

Это логично: $A | A = \lnot(A \land A) = \lnot A$. Один вентиль NAND заменяет инвертор.

Конъюнкция ($A \land B$): применяем NAND дважды - сначала к $A$ и $B$, затем инвертируем результат:

$A \land B \;=\; (A | B) | (A | B).$

Нужно два вентиля NAND. По сути, второй вентиль работает как инвертор из предыдущего пункта.

Дизъюнкция ($A \lor B$): по закону де Моргана $A \lor B = \lnot(\lnot A \land \lnot B)$, откуда:

$A \lor B \;=\; (A | A) | (B | B).$

Три вентиля NAND: два инвертора для $\lnot A$ и $\lnot B$, один NAND для итога.

Импликация ($A \to B$): поскольку $A \to B = \lnot A \lor B$, получаем:

$A \to B \;=\; A | (B | B).$

Два вентиля NAND: сначала $\lnot B = B|B$, затем $A | \lnot B$.

Как выразить NOT, OR и AND через NOR

Симметричная картина для стрелки Пирса:

Отрицание ($\lnot A$): так же, как у NAND - дублируем вход:

$\lnot A \;=\; A \downarrow A,$

потому что $A \downarrow A = \lnot(A \lor A) = \lnot A$.

Дизъюнкция ($A \lor B$): применяем NOR дважды:

$A \lor B \;=\; (A \downarrow B) \downarrow (A \downarrow B).$

Второй NOR снова работает как инвертор. Два вентиля NOR.

Конъюнкция ($A \land B$): по де Моргану $A \land B = \lnot(\lnot A \lor \lnot B)$, откуда:

$A \land B \;=\; (A \downarrow A) \downarrow (B \downarrow B).$

Три вентиля NOR, аналогично OR через NAND.

Импликация ($A \to B$): чуть длиннее из-за ассиметрии - $A \to B = \lnot A \lor B$:

$A \to B \;=\; ((A \downarrow A) \downarrow B) \downarrow ((A \downarrow A) \downarrow B).$

Четыре вентиля NOR. В этом единственном пункте NOR «дороже» NAND на два вентиля.

Применение в цифровой электронике

В реальных интегральных схемах NAND и NOR - не просто удобные абстракции. Вентиль NAND реализуется через транзисторы TTL или CMOS проще и компактнее, чем AND, потому что AND фактически содержит внутри NAND плюс инвертор. Поэтому серия 74xx (стандарт TTL) содержит микросхемы «четыре двухвходовых NAND» (7400) и «четыре двухвходовых NOR» (7402) как базовые строительные блоки.

Именно из набора 7400 можно собрать любой цифровой узел: регистр, счётчик, сумматор. Аналогично в CMOS-технологии NAND и NOR реализуются через комплементарные пары транзисторов и потребляют меньше тока, чем более сложные вентили. В программируемых схемах (FPGA) базовый элемент LUT (lookup table) по смыслу близок к многовходовому NAND.

Рассчитать для своей задачи

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

• Путаница NAND и NOR с AND и OR. NAND - это НЕ «И», а «НЕ-И»: результат инвертирован. При A=1, B=1 результат NAND равен 0, а не 1.
• Забывают перевести $\lor$ в $\land$ через де Моргана. При выводе OR через NOR нужна не прямая подстановка, а закон де Моргана: $A \lor B = \lnot(\lnot A \land \lnot B) = \lnot((\lnot A) \lor (\lnot B)) \ldots$ - лучше пользоваться готовой формулой $(A \downarrow B) \downarrow (A \downarrow B)$.
• Смешивают нотации. $A | B$ в булевой алгебре (штрих Шеффера) и $A | B$ в языках программирования (побитовое ИЛИ) - разные операции. В логике вертикальная черта обозначает NAND.
• Неправильно считают вентили. Для AND через NAND нужно два вентиля (NAND + инвертор-NAND), а не один. Один NAND даёт «НЕ-И», а не «И».
• Игнорируют ассоциативность. Импликация через NAND ($A | (B|B)$) не равна $(A|B)|B$ - порядок скобок меняет результат.

FAQ

Чем штрих Шеффера отличается от стрелки Пирса? NAND ($A|B$) равен 0 только при $A=1$ и $B=1$; NOR ($A \downarrow B$) равен 1 только при $A=0$ и $B=0$. По сути это дуальные операции: NOR - это NAND с инвертированными входами и выходом (принцип двойственности де Моргана).

Почему их называют «функционально полными»? Потому что через каждый из них можно выразить отрицание и хотя бы одну из двух операций - конъюнкцию или дизъюнкцию. Поскольку $\{\lnot, \land\}$ - полный базис, любая булева функция выразима и через NAND, и через NOR в отдельности.

Существуют ли другие одноэлементные полные базисы? Из всех 16 бинарных булевых функций от двух переменных одноэлементный полный базис образуют только NAND и NOR. Остальные 14 операций либо не полны сами по себе, либо требуют дополнения хотя бы одной константой или ещё одной операцией.

Коротко

Штрих Шеффера ($A|B = \lnot(A \land B)$, NAND) и стрелка Пирса ($A \downarrow B = \lnot(A \lor B)$, NOR) - единственные бинарные булевы операции, каждая из которых образует самостоятельный функционально полный базис. Через NAND выводятся NOT (один вентиль), AND (два вентиля) и OR (три вентиля); через NOR - NOT (один), OR (два) и AND (три). Именно поэтому в цифровой схемотехнике NAND и NOR служат универсальными строительными блоками: из одного типа вентилей можно собрать любую логическую схему.