Информатика · объяснение и практика
Один элемент NAND: как собрать НЕ, И и ИЛИ
Собираем НЕ, И и ИЛИ из одинаковых двухвходовых NAND: читаем промежуточные сигналы и проверяем эквивалентность схем по полной таблице, а не по одному удачному входу.

В теме Логика и логические схемы · Учебная карта
Главная мысль
Двухвходовый NAND выдаёт отрицание конъюнкции: N(a,b)=¬(a∧b). Если подать один сигнал на оба входа, получится НЕ. Отрицая результат NAND ещё одним таким элементом, получим И. Для ИЛИ сначала отдельно инвертируют оба входа, затем подают их на NAND. Так один вид элемента позволяет построить базовые булевы операции.
Разделяем значение сигнала и устройство схемы
Каждый вход в этой модели принимает только ноль или единицу. NAND даёт ноль лишь тогда, когда оба входа единичные; при остальных трёх сочетаниях результат равен единице. Это не сложение чисел и не запрет совместного появления сигналов. Схема просто вычисляет определённую функцию. Дальше допускается соединять выход одного элемента со входами других и разветвлять провод, сохраняя на ветвях один и тот же логический сигнал.
Подавая a сразу на два входа, получаем N(a,a)=¬a: при нуле на входе выходит единица, при единице — ноль. Теперь обозначим t=N(a,b). Чтобы получить конъюнкцию, подключим t к обоим входам следующего элемента: N(t,t)=¬t=a∧b. Два одинаковых по устройству элемента выполняют разные роли благодаря разным соединениям. Названия промежуточных проводов нужны для чтения, но не добавляют новую операцию.
Строим дизъюнкцию через отрицания
Для ИЛИ возьмём u=N(a,a) и v=N(b,b). Это отрицания исходных сигналов. Выход N(u,v) равен ¬(¬a∧¬b), то есть a∨b по закону де Моргана. Здесь нужны три двухвходовых элемента: два создают отрицания, а третий объединяет их. Если забыть инвертировать один из входов, получится другая булева функция, даже когда на некоторых парах она случайно совпадёт с ИЛИ.
Проверять такую сеть удобно по слоям. Сначала вычисляют u и v для заданной пары, затем значение последнего элемента. Нельзя подменять промежуточный провод его названием или считать, что все одинаковые элементы обязательно дают одинаковый выход. Их функция одна и та же, но значения зависят от подключённых сигналов. Для схем без обратных связей подобный порядок вычисления позволяет однозначно пройти от внешних входов к выходу.
Пример
В сети u=N(a,a), v=N(b,b), y=N(u,v). Вычислим результат для четырёх входов (a,b): (0,0), (0,1), (1,0), (1,1).
Пары (u,v) равны соответственно (1,1), (1,0), (0,1), (0,0). Последний NAND выдаёт 0, 1, 1, 1. Это полная таблица ИЛИ, поэтому совпадение установлено для всех допустимых пар, а не только для одного выбранного опыта.
Что именно доказывает универсальность
Из НЕ, И и ИЛИ можно построить булеву формулу по таблице истинности конечного числа входов. Поэтому возможность собрать эти операции из NAND даёт способ выражать любые такие булевы функции. Но это утверждение о выразительности, а не обещание минимального количества элементов. Одна и та же функция может иметь несколько сетей разного размера и глубины. Доказательство правильности сети не доказывает, что более короткой схемы не существует.
Учебная таблица также не описывает задержки реальных электронных компонентов, уровни напряжения и поведение при смене входов. Здесь рассматриваются установившиеся двоичные значения идеальных элементов. Проверка одного входного набора может опровергнуть неверную схему, если найдено различие, но не подтверждает эквивалентность на остальных наборах. Для двух входов всего четыре строки, поэтому полная проверка остаётся простой и содержательной практикой.
От чтения к действию
А теперь — вы
Частые вопросы
Можно соединить один сигнал с обоими входами NAND?
В идеальной булевой модели это допустимое разветвление сигнала. Получится его отрицание: N(a,a)=¬a.
Универсальная схема обязательно самая короткая?
Нет. Универсальность означает возможность построения функции, а оптимизация числа элементов является отдельной задачей.
Углублённый разбор
Четыре NAND для исключающего ИЛИ
Совместное использование промежуточного NAND позволяет собрать исключающее ИЛИ четырьмя одинаковыми элементами. Полная таблица проверяет функцию, а отдельный конечный перебор различает правильность схемы и минимальность её размера.
Перед началом: Двухвходовый NAND; Таблица истинности.
Первый провод используется двумя ветвями
Обозначим N(a,b)=¬(a∧b). Построим u=N(a,b),v=N(a,u),w=N(b,u),Y=N(v,w). Провод u подключён к двум следующим элементам, поэтому это сеть с общим промежуточным результатом. Если вместо повторного использования дублировать поддерево u, число элементов увеличится, хотя логическая формула останется эквивалентной.
Выходы внутренних элементов нужно вычислять по слоям. u показывает, что оба входа не равны 1 одновременно. Ветви v и w избирательно реагируют на единственную активную сторону. Последний NAND возвращает 1, когда хотя бы одна из ветвей стала 0, что происходит ровно при различающихся исходных входах.
Алгебра и таблица дают независимые проверки
По де Моргану Y=¬v∨¬w=(a∧u)∨(b∧u)=u∧(a∨b). После подстановки u получаем ¬(a∧b)∧(a∨b): истинен хотя бы один вход, но не оба. Это и есть исключающее ИЛИ. Вывод не требует считать NAND ассоциативной операцией, которой она в общем случае не является.
Независимая таблица содержит четыре строки исходных входов и значения каждого провода. Совпадение только на смешанных наборах недостаточно: ошибочная сеть может вычислять включающее ИЛИ и ошибаться на 11. Проверка 00 также нужна, чтобы исключить отрицание либо постоянную единицу на выходе.
Минимальность относится к точно названной модели схем
Рассмотрим ациклические сети из двухвходовых NAND с двумя внешними входами a,b. Разрешим повторное подключение одного провода на оба входа и произвольное разветвление, но не дадим бесплатных инверсий, констант и иных операций. Любую такую сеть можно упорядочить топологически: новый элемент берёт два провода из уже доступных.
Для одного элемента имеется 3 неупорядоченные пары входов с повторениями; для второго —6; для третьего —10. Полный перебор выходов сетей размеров 1,2,3 проверяет 3+18+180=201 вариант подключения. Ни один не вычисляет XOR. Этот конечный сертификат вместе с построенной сетью доказывает минимум 4 именно в оговорённой модели, а не для любых физических библиотек.
Два включённых входа
Условие. Проверьте четырёхэлементную сеть на всех двоичных входах и определите значения внутренних проводов при a=b=1.
- При 00 получаем(u,v,w,Y)=(1,1,1,0). При 01 получаем(1,1,0,1).
- При 10 получаем(1,0,1,1). При 11 первый NAND даёт u=0.
- Тогда v=N(1,0)=1 и w=N(1,0)=1, а последний Y=N(1,1)=0.
- Столбец Y равен 0,1,1,0: это XOR. Исчерпывающий перебор всех сетей до трёх элементов не содержит такого столбца.
Ответ. При 11:u=0,v=1,w=1,Y=0. Четыре NAND достаточны и минимальны в заданной модели.
Проверка. Алгебраическая форма Y=(a∨b)∧¬(a∧b) независимо совпадает с таблицей. Перебор 201 меньшей схемы проверяет нижнюю границу, не подменяя её числом элементов готовой конструкции.
Где легко ошибиться. Правильная четырёхэлементная схема сама по себе доказывает лишь верхнюю границу. Для слова «минимум» нужна отдельная нижняя граница и точное описание разрешённых элементов.
Проверьте понимание
Вопросы к этой главе
Можно переставить NAND как скобки в сумме?
Нет. Например, N(N(0,0),1)=0, а N(0,N(0,1))=1. Промежуточные провода задают конкретную топологию, которую нельзя менять ассоциативным правилом.
Минимум остаётся тем же при бесплатных инверсиях?
Это уже другая библиотека и другая модель стоимости. Перебор этой главы её не покрывает; нижнюю границу нужно пересчитать с новыми доступными входными сигналами.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Nand2Tetris: Project1, Boolean Logic
Первичная спецификация авторов курса: вебом сверены функция NAND, необходимость реализовать XOR и проверка логических чипов. Четырёхвентильная сеть, её промежуточные таблицы и перебор ограничения≤3 в главе проверены самостоятельно.
Задержки схемы и краткий ложный импульс
Эквивалентные установившиеся значения не гарантируют одинакового поведения во время переключения. Неравные задержки двух сходящихся ветвей NAND-схемы могут создать краткий нулевой импульс при постоянно истинной логической функции.
Перед началом: NAND-сеть; Задержка распространения.
Временная модель должна быть задана до расчёта
Пусть n=N(a,a),u=N(a,b),v=N(n,c),Y=N(u,v). В установившемся состоянии Y=(a∧b)∨(¬a∧c). Предположим транспортную задержку каждого элемента: изменение его логической функции повторяется на выходе через указанный промежуток без подавления коротких импульсов. Входные изменения считаются мгновенными.
Назначим задержку n равной 3 нс, а u,v,Y — по 1 нс. До переключения сеть полностью установилась. При b=c=1 функция выхода тождественно равна a∨¬a=1. Но ветвь с прямым a реагирует раньше ветви через инвертор, поэтому в промежутке обе отрицательные ветви могут оказаться единичными и заставить последний NAND выдать 0.
Разделите моменты изменения внутренних проводов и выхода
Изменение входа в момент 0 не меняет все провода сразу. Сначала нужно вычислить событие каждого непосредственно затронутого элемента, затем запланировать последствия для следующих. Логический расчёт без временных отметок пропустит промежуточную комбинацию u=v=1, поскольку до и после перехода она отсутствует.
Выходной элемент имеет собственную задержку. Интервал опасной комбинации на его входах нужно перенести по времени ещё на 1 нс, а не выдавать за готовый выходной импульс. При транспортной модели обе границы переносятся одинаково, поэтому длительность сохраняется. Для инерционной модели короткий импульс мог бы подавляться; это потребовало бы отдельного правила фильтрации.
Статический импульс не опровергает булево тождество
Если выход должен был оставаться 1, но кратко стал 0, говорят о статической опасности единицы. Булева функция по-прежнему верна для установившихся состояний. Чтобы схема удовлетворяла временному требованию, нужно контролировать пути, запас времени считывания либо изменить топологию, а не просто ещё раз проверить четыре логические строки.
Алгебраически избыточный член b∧c может обеспечить постоянное покрытие при таком одиночном переключении: при b=c=1 он не зависит от a. Но конкретную реализацию добавленной ветви и выходного объединения всё равно проверяют с её задержками. Логическая избыточность иногда полезна для времени, но сама фраза «добавили член» ещё не является измерением физической схемы.
Нулевой импульс после падения входа
Условие. Для указанной сети b=c=1,a до t=0 равен 1, а в t=0 падает до 0. Найдите события внутренних проводов и интервал нулевого выхода Y.
- До перехода n=0,u=0,v=1,Y=1. Падение a запускает изменение u через 1 нс и n через 3 нс.
- В t=1 получаем u=1, пока v ещё равен 1. Последний NAND планирует Y=0 на t=2.
- В t=3 сигнал n становится 1. Ещё через 1 нс, в t=4, ветвь v становится 0.
- Это возвращает Y в 1 в t=5. Значит Y=0 на полуинтервале [2,5) нс, длительность импульса 3 нс.
Ответ. Нулевой выход появляется от 2 до 5 нс, при длительности 3 нс.
Проверка. Проверка кусочных функций даёт u=1 после 1 нс, v=1 до 4 нс. Их NAND без задержки нулевой на [1,4), а транспортная задержка последнего элемента переносит этот интервал в [2,5).
Где легко ошибиться. Не смешивайте интервал опасной комбинации на входах последнего элемента с интервалом импульса на его выходе. Задержка последнего NAND сдвигает обе границы.
Проверьте понимание
Вопросы к этой главе
При обратном переходе a тоже будет импульс?
Не обязательно. При подъёме a прямая ветвь u успевает стать 0 раньше, чем v станет 1, поэтому хотя бы один вход последнего NAND остаётся 0. Порядок событий зависит от направления перехода.
Этот расчёт предсказывает любую реальную микросхему?
Нет. Он точен для заданной транспортной модели и чисел задержек. Реальные компоненты имеют интервалы задержек, пороговые уровни и фильтрацию, которые нужно включить в более подробную модель.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Georgia Tech ECE2020: Propagation Delay and Timing Hazards
Первичные учебные материалы: прочитаны определение задержки и статического ложного импульса. Собственная NAND-топология с задержками 3,1,1,1 и вычисленные моменты событий отличаются от схемы и одинаковых 5ns источника.
Критерий Поста для функциональной полноты набора связок
Построение одной полезной связки ещё не доказывает функциональную полноту всего набора. Критерий Поста перечисляет пять сохраняемых свойств: достаточно проверить, не заперт ли базис целиком в одном из соответствующих классов. Отрицательный ответ получает короткий структурный сертификат.
Перед началом: Композиция булевых функций; Полином Жегалкина.
Пять классов замкнуты относительно построения формул
Фиксируем обычную полноту по композиции функций и проекций; внешние константы бесплатно не добавляются. Класс T₀ сохраняет нуль, то есть f(0,…,0)=0; T₁ сохраняет единицу. Класс M состоит из монотонных функций, S — из самодвойственных: f(¬x)=¬f(x). Класс L содержит аффинные функции a₀⊕a₁x₁⊕…⊕aₙxₙ, включая свободный член.
Каждый класс замкнут относительно композиции и содержит проекции. Например, композиция самодвойственных функций при одновременном дополнении всех входов дополняет каждый промежуточный результат и итог. Поэтому из одних самодвойственных операций нельзя построить функцию, нарушающую самодвойственность. Аналогично сохраняются нуль, единица, монотонность и аффинность. Это даёт пять разных способов доказать неполноту.
Для полноты надо выйти из каждого класса, но разными функциями
Теорема Поста утверждает обратное: набор функционально полон тогда и только тогда, когда он не содержится целиком ни в одном из пяти классов. Для каждого класса достаточно найти в наборе хотя бы одну нарушающую его функцию. Не требуется одна операция, одновременно нарушающая все свойства. И не требуется, чтобы каждый элемент набора нарушал каждое свойство.
Практическая таблица должна содержать принадлежность каждой операции каждому классу. Если в одном столбце все ответы положительные, найдено препятствие. Если в каждом столбце есть отрицательный ответ, критерий доказывает полноту. Проверки класса L удобно делать по коэффициентам полинома Жегалкина: наличие хотя бы одного монома степени больше 1 означает неаффинность.
| Операция | T₀ | T₁ | M | S | L |
|---|---|---|---|---|---|
| ¬ | нет | нет | нет | да | да |
| maj | да | да | да | да | нет |
Добавление константы может изменить ответ
Самодвойственная функция не бывает постоянной: постоянный нуль при дополнении входов остаётся нулём, хотя должен стать единицей. Поэтому добавление константы к самодвойственному базису снимает именно это препятствие. Но общий результат всё равно нужно проверить по остальным столбцам либо явной конструкцией полного базиса. Молчаливо разрешённые константы меняют задачу и способны превратить правильный отрицательный вывод в неверный.
Отрицание и большинство почти выходят из всех классов
Условие. Проверьте набор {¬,maj}, где maj(x,y,z)=1 при хотя бы двух единицах. Константы исходно не разрешены. Объясните, что изменится после добавления постоянного нуля.
- Отрицание не сохраняет 0 и1, а также не монотонно: при переходе 0≤1 значение падает с1 до0. Поэтому набор не содержится в T₀,T₁,M.
- Большинство имеет полином xy⊕xz⊕yz и не является аффинным. Следовательно набор не содержится в L.
- Обе операции самодвойственны. Для большинства дополнение трёх битов меняет большинство единиц на большинство нулей; для отрицания равенство проверяется на двух входах. Весь набор лежит в S и неполон.
- Добавив 0, получаем x∧y=maj(x,y,0). Вместе с отрицанием это полный базис: через де Моргана строится OR, затем любая ДНФ. Неполнота исходного набора действительно была существенной.
Ответ. Без констант набор неполон из-за S; с постоянным 0 становится полным.
Проверка. Все 8 входов независимо подтверждают полином большинства и самодвойственность. На четырёх парах проверяется конструкция AND через maj с0; отрицание нарушает остальные три сохраняемых свойства.
Где легко ошибиться. Не считайте константы автоматически доступными и не требуйте одну универсальную функцию-нарушитель. Критерий проверяет отсутствие общего замкнутого класса для всего набора.
Проверьте понимание
Вопросы к этой главе
Почему большинство нелинейно, если его правило выглядит симметрично?
Симметрия аргументов не означает аффинность над F₂. В полиноме xy⊕xz⊕yz присутствуют квадратичные мономы, а таблица не совпадает ни с одной суммой одиночных переменных и константы.
Можно ли вывести постоянный 0 только из отрицания и большинства?
Нет. Любая такая композиция остаётся самодвойственной, а постоянный 0 этим свойством не обладает. Именно поэтому добавление 0 является новым разрешением, а не сокращённой записью старой схемы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Mariya Soskova, Math571: Honors Assignment I
Прочитаны Definition2 пяти классов и Theorem1 Поста, включая замкнутость по композиции и отсутствие бесплатных констант в определении полноты. Базис отрицание/большинство и свидетели его единственного препятствия собственные.
Обратимая схема Тоффоли вычисляет NAND с сохранёнными входами
Обычный NAND теряет сведения о двух входах и потому не является перестановкой состояний. Вентиль Тоффоли вычисляет тот же полезный бит, сохраняя входы и используя дополнительную линию. Построим таблицу восьми состояний, затем отдельно сохраним результат и очистим рабочую линию обратным вычислением.
Перед началом: Булевы AND, NAND и исключающее ИЛИ; Взаимно однозначное отображение конечного множества.
Обратимость относится ко всему состоянию
Классический обратимый вентиль на k битах — перестановка всех 2^k битовых строк. У каждого выхода ровно один вход; число входных и выходных линий одинаково. Функция NAND от двух битов к одному не обладает этим свойством: пары 00,01,10 имеют один и тот же результат 1. Поэтому обратимым нельзя назвать только её единственный полезный выход.
Тоффоли действует на тройку по правилу T(a, b, c)=(a, b, c⊕(a∧b)). Первые два бита являются управляющими и сохраняются. Третий переворачивается только при a=b=1. Если повторить T, одно и то же значение a∧b прибавится по XOR дважды и исчезнет. Следовательно, T² является тождественным отображением, а обратный вентиль совпадает с прямым.
Дополнительная единица превращается в NAND
При заранее подготовленном c=1 третий выход равен 1⊕(a∧b)=¬(a∧b). Получены четыре перехода 001→001,011→011,101→101,111→110. Полные выходные тройки различаются, хотя три полезных бита равны 1. Именно сохранённые a, b различают соответствующие входы. Если вместо единицы начать с c=0, полезный выход будет AND, а не NAND.
На всех восьми состояниях T меняет местами 110 и 111, оставляя остальные шесть на месте. Эта полная таблица проверяет обратимость, тогда как проверка только четырёх подготовленных входов показывает вычисление NAND. Две проверки отвечают на разные вопросы. Дополнительную линию называют ancilla, но здесь это обычный классический бит с явно указанным начальным состоянием.
Сохранить результат перед обратным вычислением
Если после вычисления просто повторить T, рабочая c вернётся к 1 и результат в ней исчезнет. Для сохранения введём выходную d=0 и разрешённый обратимый CNOT(c, d)=(c, d⊕c). Последовательность T, затем CNOT, затем T оставляет a, b и d=NAND(a, b), а рабочую c возвращает к 1. Сохранение результата происходит до очистки, а не после неё.
Проверка этой схемы на четырёх значениях a, b даёт законченный пример вычислить—сохранить—обратить. Она не утверждает, что можно без следа удалить все исходные данные: a, b остаются частью полного обратимого состояния. И математическая перестановка битов сама по себе не задаёт энергопотребление физической схемы; здесь проверяется информационная обратимость, а не устройство аппаратуры.
NAND и восстановленная рабочая линия
Условие. Для всех a, b∈{0,1} начните с(a, b, c, d)=(a, b,1,0). Примените T к(a, b, c), CNOT от c к d и ещё раз T к(a, b, c). Определите четыре выхода и проверьте обратимость T.
- Первый T даёт c=1⊕ab=NAND(a, b), сохраняя a, b.
- CNOT переводит d из 0 в c. Результат теперь хранится отдельно в d.
- Второй T возвращает c=(1⊕ab)⊕ab=1. Получено(a, b,1, NAND(a, b)).
- Для восьми входных троек T только переставляет 110 и 111. Поэтому все выходы различны, и повтор T восстанавливает любую исходную тройку.
Ответ. a, b сохраняются; c снова равна 1; d содержит NAND. Полный T — самообратимая перестановка восьми троек.
Проверка. Для a, b=00,01,10,11 итоговые четвёрки равны 0011,0111,1011,1110. Прямой перебор также подтверждает T(T(a, b, c))=(a, b, c) для всех восьми входов.
Где легко ошибиться. Не стирайте рабочий результат обратным вентилем до его сохранения на отдельной подготовленной выходной линии.
Проверьте понимание
Вопросы к этой главе
Можно ли отбросить сохранённые a, b и всё ещё считать NAND обратимым?
Как полезный вывод их можно не читать, но удаление из полного информационного состояния снова делает отображение неоднозначным. Это уже другая операция.
Почему для NAND нужна именно начальная 1?
Третий выход равен c⊕ab. При c=0 получается ab, а при c=1 — его отрицание. Начальное состояние дополнительной линии входит в условия вычисления.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Aaronson–Grier–Schaeffer: reversible bit operations, §1.1
Определения классических обратимых вентилей, Тоффоли и CNOT. Полная таблица и четырёхбитная проверка сохранения с очисткой выведены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Полный сумматор: бит результата и перенос из трёх входов
Полный сумматор на трёх битах: младший бит суммы, перенос в соседний разряд и сложение многобитных беззнаковых чисел.
Открыть темуКак читать составное условие с И и ИЛИ
Как проверять составные условия с И и ИЛИ: логические значения частей, включающее «или», скобки и короткое вычисление в Python.
Открыть тему