Каноническая нормальная форма

В булевой алгебре любая булева функция может быть выражена в канонической дизъюнктивной нормальной форме ( CDNF ), ^[1] каноническая форма минтерма , или Сумма произведений ( SoP или SOP ) как дизъюнкция (ИЛИ) минтермов. Двойственная форма Де Моргана — это каноническая конъюнктивная нормальная форма ( CCNF ), каноническая форма maxterm или произведение сумм ( PoS или POS ), которое представляет собой соединение (AND) maxterms. Эти формы могут быть полезны для упрощения булевых функций, что имеет большое значение при оптимизации булевых формул вообще и цифровых схем в частности.

Другие канонические формы включают полную сумму простых импликант или каноническую форму Блейка (и двойственную ей форму) и алгебраическую нормальную форму (также называемую Жегалкиным или Ридом – Мюллером).

Минтермс

Для логической функции $n$ переменные ${x_{1},\dots ,x_{n}}$ минтерм , — это термин продукта в котором каждый из $n$ переменные появляются ровно один раз (либо в дополненной, либо в недополненной форме). Таким образом, минтерм — это логическое выражение n переменных, в котором используются только оператор дополнения и оператор соединения ( логическое И ). Минтерм дает истинное значение только для одной комбинации входных переменных — минимальной нетривиальной суммы. Например, a b ' c истинно только тогда, когда a и c оба истинны, а b ложно — расположение входных данных, где a = 1, b = 0, c = 1, приводит к 1.

Индексирование минтермов

Есть 2 ^н минтермы из n переменных, поскольку переменная в выражении минтерма может быть либо в прямой, либо в дополненной форме — два варианта выбора для каждой переменной. Минтермы часто нумеруются с помощью двоичной кодировки образца дополнения переменных, где переменные записываются в стандартном порядке, обычно в алфавитном порядке. Это соглашение присваивает значение 1 прямой форме ( $x_{i}$ ) и 0 в дополненную форму ( $x'_{i}$ ); тогда минтерм $\sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})$ . Например, минтерм $abc'$ имеет номер 110 ₂ = 6 ₁₀ и обозначается $m_{6}$ .

Каноническая форма Минтерма

Учитывая таблицу истинности логической функции, ее можно записать как «сумму произведений» или «сумму минтермов». Это особая форма дизъюнктивной нормальной формы . Например, если дана таблица истинности для арифметической суммы бита u логики позиции одного бита сумматорной схемы, как функция x и y от слагаемых и переноса, ci :

Там	х	и	и(ci,x,y)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Заметив, что строки с выходным значением 1 — это 2-я, 3-я, 5-я и 8-я строки, мы можем записать u как сумму минтермов. $m_{1},m_{2},m_{4},$ и $m_{7}$ . Если мы хотим это проверить: $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)$ оцененное для всех 8 комбинаций трех переменных, будет соответствовать таблице.

Макстермс

Для логической функции от $n$ переменных ${x_{1},\dots ,x_{n}}$ , макстерм — это сумма, в которой каждая из $n$ переменных встречается ровно один раз (либо в дополненной, либо в недополненной форме). Таким образом, макстерм — это логическое выражение $n$ переменных, в котором используются только оператор дополнения и оператор дизъюнкции ( логическое ИЛИ ). Макстермы являются двойственными по отношению к идее минтермов, следуя дополнительной симметрии законов Де Моргана . Вместо использования AND и дополнений мы используем OR и дополнения и действуем аналогичным образом. Очевидно, что макстерм дает ложное значение только для одной комбинации входных переменных, т.е. он истинен при максимальном числе возможностей. Например, макстерм a ′ + b + c ′ ложен только тогда, когда a и c оба истинны, а b ложен — расположение входных данных, при котором a = 1, b = 0, c = 1, приводит к 0.

Индексирование maxterms

Их снова 2 ^н maxterms из $n$ переменных, поскольку переменная в выражении maxterm также может быть как в прямой, так и в дополненной форме — два варианта выбора для каждой переменной. Нумерация выбрана таким образом, чтобы дополнением минтерма был соответствующий макстермм. То есть каждому макстерму присваивается индекс, основанный на противоположном обычном двоичном кодировании, используемом для минтермов. Соглашение maxterm присваивает значение 0 прямой форме. $(x_{i})$ и 1 в дополненной форме $(x'_{i})$ . Например, мы присваиваем индекс 6 maxterm $a'+b'+c$ (110) и обозначим этот максимальный термин как M ₆ . Дополнение $(a'+b'+c)'$ это минтерм $abc'=m_{6}$ , используя закон де Моргана .

Каноническая форма Макстерма

Если дана таблица истинности логической функции, можно записать функцию как «произведение сумм» или «произведение максимальных членов». Это особая форма конъюнктивной нормальной формы . Например, если дана таблица истинности для бита переноса co логики позиции одного бита сумматорной схемы, как функция x и y от слагаемых и переноса, ci :

Там	х	и	со(ci,x,y)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Заметив, что строки с выходным значением 0 — это 1-я, 2-я, 3-я и 5-я строки, мы можем записать co как произведение maxterms $M_{0},M_{1},M_{2}$ и $M_{4}$ . Если мы хотим это проверить:

co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+y)(ci'+x+y)

оцененное для всех 8 комбинаций трех переменных, будет соответствовать таблице.

Минимальные формы PoS и SoP

Часто каноническая форма минтерма эквивалентна меньшей форме SoP. Эта меньшая форма по-прежнему будет состоять из суммы терминов продукта, но будет содержать меньше терминов продукта и/или терминов продукта, которые содержат меньше переменных. Например, следующая функция с тремя переменными:

а	б	с	е(а,б,в)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

имеет каноническое представление минтерма $f=a'bc+abc$ , но он имеет эквивалентную форму SoP $f=bc$ . В этом тривиальном примере очевидно, что $bc=a'bc+abc$ , а меньшая форма имеет меньше терминов продукта и меньше переменных внутри каждого термина. Минимальные минимальными представления SoP функции в соответствии с понятием «наименьший» называются формами SoP . В общем, может быть несколько минимальных форм SoP, ни одна из которых явно не меньше и не больше другой. ^[2] Аналогичным образом каноническая форма макстерма может быть сведена к различным минимальным формам PoS.

Хотя этот пример был упрощен за счет применения обычных алгебраических методов [ $f=(a'+a)bc$ ], в менее очевидных случаях удобным методом поиска минимальных форм PoS/SoP функции с числом переменных до четырех является использование карты Карно . Алгоритм Куайна – МакКласки может решать несколько более крупные проблемы. Область логической оптимизации возникла из проблемы поиска оптимальных реализаций булевых функций, таких как минимальные формы PoS и SoP.

Пример приложения

Приведенных выше примеров таблиц истинности для минтермов и макстермов достаточно, чтобы установить каноническую форму для одной битовой позиции при сложении двоичных чисел, но недостаточно для разработки цифровой логики, если ваш инвентарь вентилей не включает И и ИЛИ. Там, где производительность является проблемой (как в управляющем компьютере Apollo), доступными частями, скорее всего, будут NAND и NOR из-за дополняющего действия, присущего транзисторной логике. Значения определяются как состояния напряжения: одно около земли, другое около напряжения питания постоянного тока V _cc , например +5 В постоянного тока. Если более высокое напряжение определяется как «истинное» значение 1, логический элемент ИЛИ-НЕ является самым простым и полезным логическим элементом.

В частности, вентиль ИЛИ-НЕ с 3 входами может состоять из 3 биполярных переходных транзисторов, все эмиттеры которых заземлены, а коллекторы связаны вместе и связаны с V _cc через сопротивление нагрузки. Каждая база подключена к входному сигналу, а точка общего коллектора представляет выходной сигнал. Любой вход, который имеет значение 1 (высокое напряжение) по отношению к своей базе, замыкает эмиттер транзистора на коллектор, вызывая протекание тока через сопротивление нагрузки, что приводит напряжение коллектора (выход) очень близко к земле. Этот результат не зависит от других входных данных. Только когда все три входных сигнала равны 0 (низкое напряжение), импедансы эмиттер-коллектор всех трех транзисторов остаются очень высокими. Тогда ток течет очень мало, и эффект делителя напряжения с сопротивлением нагрузки налагает на точку коллектора высокое напряжение, очень близкое к V _cc .

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

В этом примере предполагается наличие запасных частей Apollo: только вентили NOR с 3 входами, но обсуждение упрощается, если предположить, что также доступны вентили NOR с 4 входами (в Apollo они были составлены из пар вентилей NOR с 3 входами).

Канонические и неканонические последствия вентилей НО

Набор из 8 вентилей ИЛИ-НЕ, если их входные данные представляют собой все комбинации прямых и дополнительных форм трех входных переменных ci, x и y , всегда создают минтермы, а не макстермы, то есть из 8 вентилей, необходимых для обработки всех комбинаций. из 3 входных переменных только одна имеет выходное значение 1. Это потому, что вентиль ИЛИ-НЕ, несмотря на его название, лучше рассматривать (используя закон Де Моргана) как И дополнений его входных сигналов.

Причина, по которой это не является проблемой, заключается в двойственности минтермов и макстермов, т.е. каждый макстерм является дополнением минтерма с аналогичным индексом, и наоборот.

В приведенном выше примере минтерма мы написали $u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}$ но чтобы выполнить это с помощью вентиля ИЛИ-НЕ с 4 входами, нам нужно переформулировать его как произведение сумм (PoS), где суммы являются противоположными максимальными условиями. То есть,

u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).

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

Там	х	и	M_М0	M ₃	М ₅	M_М6	И	и(ci,x,y)
0	0	0	0	1	1	1	0	0
0	0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	1	0	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	1	1	0	1	0	0
1	1	0	1	1	1	0	0	0
1	1	1	1	1	1	1	1	1

Там	х	и	м ₀	m ₃	м ₅	м ₆	НИ	и(ci,x,y)
0	0	0	1	0	0	0	0	0
0	0	1	0	0	0	0	1	1
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	0	0	0
1	0	0	0	0	0	0	1	1
1	0	1	0	0	1	0	0	0
1	1	0	0	0	0	1	0	0
1	1	1	0	0	0	0	1	1

В приведенном выше примере maxterm мы написали $co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}$ но чтобы выполнить это с помощью вентиля ИЛИ-НЕ с 4 входами, нам нужно заметить равенство ИЛИ-НЕ тех же минтермов. То есть,

co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).

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

Там	х	и	M_М0	М ₁	M_М2	M_М4	И	со(ci,x,y)
0	0	0	0	1	1	1	0	0
0	0	1	1	0	1	1	0	0
0	1	0	1	1	0	1	0	0
0	1	1	1	1	1	1	1	1
1	0	0	1	1	1	0	0	0
1	0	1	1	1	1	1	1	1
1	1	0	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

Там	х	и	м ₀	м ₁	m_м2	м ₄	НИ	со(ci,x,y)
0	0	0	1	0	0	0	0	0
0	0	1	0	1	0	0	0	0
0	1	0	0	0	1	0	0	0
0	1	1	0	0	0	0	1	1
1	0	0	0	0	0	1	0	0
1	0	1	0	0	0	0	1	1
1	1	0	0	0	0	0	1	1
1	1	1	0	0	0	0	1	1

Компромиссы при проектировании, рассматриваемые в дополнение к каноническим формам

Можно было бы предположить, что работа по проектированию сумматора на этом завершена, но мы не учли тот факт, что все три входные переменные должны присутствовать как в прямой, так и в дополнительной форме. В этом отношении нет никаких сложностей с слагаемыми x и y , поскольку они статичны на протяжении всего сложения и, таким образом, обычно удерживаются в схемах-защелках, которые обычно имеют как прямой, так и дополнительный выход. (Простейшая схема-защелка, состоящая из вентилей ИЛИ-НЕ, представляет собой пару вентилей, перекрестно связанных в триггер: выход каждого подключен как один из входов к другому.) Также нет необходимости создавать дополнительную форму. суммы u . Однако перенос одной битовой позиции должен передаваться как перенос в следующую битовую позицию как в прямой, так и в дополнительной форме. Самый простой способ сделать это — пропустить co через вентиль ИЛИ-НЕ с 1 входом и пометить выход co ′, но это добавит задержку вентиля в самом худшем месте, замедляя пульсацию переносов справа налево. Дополнительный вентиль ИЛИ-НЕ с 4 входами, создающий каноническую форму co ′ (из противоположных минтермов, таких как co ) решает эту проблему.

co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).

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

Там	х	и	M ₃	М ₅	M_М6	M_М7	И	со'(ci,x,y)
0	0	0	1	1	1	1	1	1
0	0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	0	1	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	1	0	1	1	0	0
1	1	0	1	1	0	1	0	0
1	1	1	1	1	1	0	0	0

Там	х	и	m ₃	м ₅	м ₆	м ₇	НИ	со'(ci,x,y)
0	0	0	0	0	0	0	1	1
0	0	1	0	0	0	0	1	1
0	1	0	0	0	0	0	1	1
0	1	1	1	0	0	0	0	0
1	0	0	0	0	0	0	1	1
1	0	1	0	1	0	0	0	0
1	1	0	0	0	1	0	0	0
1	1	1	0	0	0	1	0	0

Компромисс для поддержания полной скорости таким образом включает в себя неожиданные затраты (помимо необходимости использовать ворота большего размера). Если бы мы просто использовали этот элемент с 1 входом в дополнение к co , минтерм был бы бесполезен. $m_{7}$ , и ворота, которые его породили, могли быть устранены. Тем не менее, это по-прежнему хорошая сделка.

Теперь мы могли бы реализовать эти функции точно в соответствии с их каноническими формами SoP и PoS, превратив вентили NOR в указанные функции. Вентиль ИЛИ-НЕ преобразуется в вентиль ИЛИ путем пропускания его выхода через вентиль ИЛИ-НЕ с 1 входом; и он превращается в логический элемент И путем пропускания каждого из его входов через логический элемент ИЛИ-НЕ с 1 входом. Однако этот подход не только увеличивает количество используемых вентилей, но и удваивает количество задержек вентилей при обработке сигналов, сокращая скорость обработки вдвое. Следовательно, всякий раз, когда производительность имеет решающее значение, стоит выйти за рамки канонических форм и применить булеву алгебру, чтобы нерасширенные логические элементы NOR выполняли свою работу.

Дизайн сверху вниз и снизу вверх

Теперь мы увидели, как инструменты minterm/maxterm можно использовать для разработки каскада сумматора в канонической форме с добавлением некоторой булевой алгебры, требуя всего 2 задержки вентиля для каждого из выходов. Это «нисходящий» способ проектирования цифровой схемы для этой функции, но является ли он лучшим способом? Дискуссия сосредоточилась на определении «самого быстрого» как «лучшего», и дополненная каноническая форма безупречно соответствует этому критерию, но иногда преобладают другие факторы. Основная цель проектировщика может заключаться в минимизации количества вентилей и/или минимизации разветвлений сигналов на другие вентили, поскольку большие разветвления снижают устойчивость к ухудшенному источнику питания или другим факторам окружающей среды. В таком случае дизайнер может разработать проект канонической формы в качестве основы, затем попробовать разработку снизу вверх и, наконец, сравнить результаты.

Разработка снизу вверх включает в себя замечание того, что u = ci XOR ( x XOR y ), где XOR означает исключающее ИЛИ [истина, когда любой из входных данных истинен, но не когда оба ввода истинны], и что co = ci x + xy + y ci . Одна из таких разработок требует всего двенадцать вентилей ИЛИ: шесть вентилей с 2 входами и два вентиля с 1 входом для создания u за 5 задержек, плюс три вентиля с 2 входами и один вентиль с 3 входами для создания co ' за 2 задержки. Каноническая базовая линия включала восемь вентилей ИЛИ-НЕ с 3 входами плюс три вентиля ИЛИ-НЕ с 4 входами для создания u, co и co ′ с задержкой в 2 вентиля. Если в состав схемы действительно входят вентили ИЛИ-НЕ с 4 входами, каноническая конструкция сверху вниз выглядит выигрышной как по количеству вентилей, так и по скорости. Но если (вопреки нашему удобному предположению) схемы на самом деле представляют собой 3-входовые вентили ИЛИ-НЕ, из которых два требуются для каждой 4-входовой функции ИЛИ-НЕ, тогда каноническая конструкция требует 14 вентилей по сравнению с 12 для восходящего подхода, но по-прежнему вычисляет цифру суммы u значительно быстрее. Сравнение разветвлений представлено в таблице:

Переменные	Сверху вниз	Вверх дном
х	4	1
х'	4	3
и	4	1
и'	4	3
Там	4	1
Там'	4	3
М или м	4@1,4@2	Н/Д
х исключающее ИЛИ у	Н/Д	2
Разное	Н/Д	5@1
Макс	4	3

В описании развития «снизу вверх» упоминается co в качестве результата ′, но не co . Неужели этот дизайн просто никогда не нуждается в прямой форме выполнения? Ну и да и нет. На каждом этапе вычисление co ′ зависит только от ci ′, x ′ и y ′, что означает, что распространение переноса колеблется вдоль битовых позиций так же быстро, как и в каноническом проекте, без какого-либо развития co . Вычисление u , которое действительно требует, чтобы ci было сделано из ci ' с помощью NOR с 1 входом, происходит медленнее, но для любой длины слова схема платит этот штраф только один раз (когда появляется крайняя левая цифра суммы). Это связано с тем, что эти вычисления перекрываются, каждый в своем маленьком конвейере, не влияя на то, когда может быть вычислен суммарный бит следующей битовой позиции. И конечно, co ' из крайней левой позиции бита, вероятно, придется дополнить как часть логики, определяющей, произошло ли сложение. Но при использовании вентилей ИЛИ-НЕ с 3 входами схема «снизу вверх» почти так же быстро выполняет параллельное сложение при нетривиальной длине слова, сокращает количество вентилей и использует меньшие разветвления... так что она выигрывает, если количество вентилей и/или разветвление имеют первостепенное значение!

Мы оставим точную схему восходящей конструкции, в которой все эти утверждения верны, в качестве упражнения для заинтересованного читателя, опираясь на еще одну алгебраическую формулу: u = ci ( x XOR y ) + ci ′( x XOR y )']'. Такое отделение распространения переноса от формирования суммы повышает производительность сумматора с упреждающим переносом по сравнению с сумматором со пульсирующим переносом .

Применение в проектировании цифровых схем

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

Существует шестнадцать возможных функций двух переменных, но в цифровых логических устройствах простейшие вентильные схемы реализуют только четыре из них: конъюнкцию (И), дизъюнкцию (включающее ИЛИ) и соответствующие дополнения к ним (И-НЕ и ИЛИ-НЕ).

Большинство вентильных схем принимают более двух входных переменных; например, космический управляющий компьютер «Аполлон» , который стал пионером в применении интегральных схем в 1960-х годах, был построен только с одним типом вентиля, ИЛИ-НЕ с тремя входами, выходной сигнал которого истинен только тогда, когда все три входа ложны. ^[3]^{[ нужна страница ]}^[4]

См. также

Список тем по булевой алгебре

Ссылки

^ Питер Дж. Пал; Рудольф Дамрат (06 декабря 2012 г.). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. стр. 15–. ISBN 978-3-642-56893-0 .
^ Лала, Параг К. (16 июля 2007 г.). Принципы современного цифрового дизайна . Джон Уайли и сыновья. п. 78. ИСБН 978-0-470-07296-7 .
^ Холл, Элдон К. (1996). Путешествие на Луну: история компьютера управления Аполлоном . АААА. ISBN 1-56347-185-Х .
^ «Схема НАВИГАЦИОННОГО КОМПЬЮТЕРА АПОЛЛОНА (AGC)» . klabs.org . Рич Кац . Проверено 19 июня 2021 г. Чтобы увидеть, как логика вентиля ИЛИ использовалась в АЛУ управляющего компьютера Apollo, выберите любую из записей 4-БИТНОГО МОДУЛЯ в Указатель чертежей и разверните изображения по желанию.

Дальнейшее чтение

Бендер, Эдвард А.; Уильямсон, С. Гилл (2005). Краткий курс дискретной математики . Минеола, штат Нью-Йорк: ISBN Dover Publications, Inc. 0-486-43946-1 .
Авторы демонстрируют доказательство того, что любая булева (логическая) функция может быть выражена как в дизъюнктивной, так и в конъюнктивной нормальной форме (см. стр. 5–6); доказательство просто продолжается путем создания всех 2 ^Н строк из N логических переменных и демонстрирует, что каждая строка («minterm» или «maxterm») имеет уникальное логическое выражение. Любая булева функция от N переменных может быть получена из совокупности строк, минимальный или максимальный термин которых равен логическим единицам («истина»).
Маккласки, Э.Дж. (1965). Введение в теорию коммутационных цепей . Нью-Йорк: Книжная компания McGraw – Hill. п. 78. LCCN 65-17394 . Канонические выражения определены и описаны
Хилл, Фредрик Дж.; Петерсон, Джеральд Р. (1974). Введение в теорию переключения и логическое проектирование (2-е изд.). Нью-Йорк: Джон Уайли и сыновья. п. 101. ИСБН 0-471-39882-9 . Обозначение функций Minterm и maxterm

Внешние ссылки

Буль, Джордж (1848). «Логическое исчисление» . Кембриджский и Дублинский математический журнал . III . Перевод Уилкинса, Дэвида Р.: 183–198.

[PahlDamrath2012-1] Питер Дж. Пал; Рудольф Дамрат (06 декабря 2012 г.). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. стр. 15–. ISBN 978-3-642-56893-0 .

[2] Лала, Параг К. (16 июля 2007 г.). Принципы современного цифрового дизайна . Джон Уайли и сыновья. п. 78. ИСБН 978-0-470-07296-7 .

[3] Холл, Элдон К. (1996). Путешествие на Луну: история компьютера управления Аполлоном . АААА. ISBN 1-56347-185-Х .

[4] «Схема НАВИГАЦИОННОГО КОМПЬЮТЕРА АПОЛЛОНА (AGC)» . klabs.org . Рич Кац . Проверено 19 июня 2021 г. Чтобы увидеть, как логика вентиля ИЛИ использовалась в АЛУ управляющего компьютера Apollo, выберите любую из записей 4-БИТНОГО МОДУЛЯ в Указатель чертежей и разверните изображения по желанию.

[1]

[2]

[3]

[4]

v т и Цифровая электроника
Components	Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU)
Theory	Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent
Design	Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine
Applications	Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature
Design issues	Metastability Runt pulse

v т и Нормальные формы в логике
Propositional logic	Negation normal form Conjunctive normal form Disjunctive normal form Algebraic normal form (Zhegalkin polynomial) Blake canonical form Canonical normal form Horn clause
Predicate logic	Skolem normal form Herbrandization Prenex normal form
Other	Beta normal form Modal clausal form Normal form (natural deduction)