Что значит «функциональная полнота»
Набор типов вентилей называется функционально полным, если из вентилей только этого набора можно построить абсолютно любую булеву функцию. AND, OR и NOT вместе полны, но ни один из них не полон в одиночку — всегда нужны минимум два из трёх. NAND — удивительное исключение: один-единственный тип вентиля, используемый многократно, достаточен, чтобы построить NOT, AND, OR и вообще любую булеву функцию. То же самое верно и для NOR.
Строим NOT, AND и OR из одних NAND
Три конструкции покрывают всё:
- NOT: подать один и тот же сигнал на оба входа NAND. NAND(A,A) = ¬A.
- AND: инвертировать выход NAND вторым NAND, включённым как NOT. AND(A,B) = ¬(NAND(A,B)).
- OR: применить законы Де Моргана — сначала инвертировать оба входа (тем же трюком с NOT), затем подать их на NAND. OR(A,B) = NAND(¬A,¬B).
Почему производство предпочитает один тип вентиля
В КМОП-технологии вентиль NAND строится напрямую из четырёх транзисторов; вентиль AND — это те же четыре транзистора плюс ещё два, чтобы снова инвертировать выход. Поэтому NAND и NOR физически проще всего изготовить, и стандартные библиотеки ячеек строятся именно вокруг них — вентиль OR в реальной микросхеме обычно внутри устроен как NOR плюс инвертор, а не отдельный примитив. Сведение произвольной схемы к одному типу вентиля также упрощает тестовые шаблоны на производстве, поскольку каждая ячейка кристалла ведёт себя одинаково.
Попробуйте сами
Пересоберите полусумматор, используя только вентили NAND — без AND, OR и XOR — в редакторе схем, а затем сравните его таблицу истинности с исходной двухвентильной версией, чтобы убедиться, что они логически идентичны.