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

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) Тон или стиль этой статьи может не отражать энциклопедический тон , используемый в Википедии .Рекомендации см. в руководстве Википедии по написанию лучших статей . ( Февраль 2009 )( Узнайте, как и когда удалить это сообщение ) Для проверки данной статьи необходимы дополнительные цитаты .Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденный материал может быть оспорен и удален. Найти источники:  "Каноническая нормальная форма" – новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2010 г. )( Узнайте, как и когда удалить это сообщение ) В данной статье представлен неполный взгляд на предмет . ( Узнайте, как и когда удалить это сообщение )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle u(ci,x,y)=\mathrm {И} (M_{0},M_{3},M_{5},M_{6})=\mathrm {НОР} (m_{0},m_{3},m_{5},m_{6}).}$

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

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

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

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

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

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

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

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

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

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

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

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

Большинство схем вентилей принимают более 2 входных переменных; например, бортовой управляющий компьютер Apollo , который стал пионером применения интегральных схем в 1960-х годах, был построен только с одним типом вентиля, 3-входовым NOR, выход которого является истинным только тогда, когда все 3 входа являются ложными. ^{[3] [ нужна страница ] [4]}

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

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

В Wikibook Electronics есть страница по теме: Булева алгебра.

• Буль, Джордж (1848). «Исчисление логики». Cambridge and Dublin Mathematical Journal . III . Перевод Уилкинса, Дэвида Р.: 183–198.