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

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

В булевой алгебре любую булеву функцию можно преобразовать в каноническую дизъюнктивную нормальную форму ( CDNF ) ^[1] или в минтерм-каноническую форму и ее дуальную каноническую конъюнктивную нормальную форму ( CCNF ) или в макстерм-каноническую форму . Другие канонические формы включают полную сумму простых импликант или каноническую форму Блейка (и двойственную к ней), а также алгебраическую нормальную форму (также называемую Жегалкин или Рид-Мюллер).

Minterms называются продуктами, потому что они являются логическим И для набора переменных, а maxterms называются суммами, потому что они являются логическим ИЛИ для набора переменных. Эти концепции двойственны из-за их отношения дополнительной симметрии, выраженной законами Де Моргана .

Две двойственные канонические формы любой булевой функции - это «сумма minterms» и «произведение maxterms». Термин « сумма произведений » ( SoP или SOP ) широко используется для обозначения канонической формы, которая представляет собой дизъюнкцию (OR) минтермов. Его дуал Де Моргана - это « произведение сумм » ( PoS или POS ) для канонической формы, которая является конъюнкцией (И) maxterms. Эти формы могут быть полезны для упрощения этих функций, что имеет большое значение при оптимизации булевых формул в целом и цифровых схем в частности.

Minterms [ править ]

Для булевой функции от переменных , А термин продукта , в котором каждый из переменных появляется один раз (либо в его дополненном или Недополняемой форме) называется minterm . Таким образом, minterm - это логическое выражение n переменных, в котором используются только оператор дополнения и оператор конъюнкции .${\ displaystyle n}$${\ displaystyle {x_ {1}, \ dots, x_ {n}}}$${\ displaystyle n}$

Так , например, , и 3 примеров 8 минтермов для булевой функции от трех переменных , и . Обычно последнее из них читается как AND b AND NOT-c .${\ displaystyle abc}$${\ displaystyle ab'c}$${\ displaystyle abc '}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$

Существует 2 ⁿ minterm n переменных, поскольку переменная в выражении minterm может быть либо в своей прямой, либо в дополненной форме - два варианта для каждой переменной.

Индексирование минтермов [ править ]

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

Функциональная эквивалентность [ править ]

Данный minterm n дает истинное значение (т. Е. 1) только для одной комбинации входных переменных. Например, minterm 5, a b ' c , истинно только тогда, когда a и c оба истинны, а b ложно - расположение входных данных, где a = 1, b = 0, c = 1, приводит к 1.

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

Заметив, что строки, которые имеют на выходе 1, являются 2-й, 3-й, 5-й и 8-й, мы можем записать u как сумму minterms и . Если мы хотим проверить это: оцененные для всех 8 комбинаций трех переменных будут соответствовать таблице.${\ displaystyle m_ {1}, m_ {2}, m_ {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)}$

Maxterms [ править ]

Для булевой функции от п переменных , срок суммы , в которой каждый из п появляется переменных сразу (либо в его дополненного или Недополняемые форме) называется maxterm . Таким образом, maxterm - это логическое выражение n переменных, в котором используются только оператор дополнения и оператор дизъюнкции . Maxterms двойственны идее minterm (т. Е. Демонстрируют дополнительную симметрию во всех отношениях). Вместо использования И и дополнений мы используем ИЛИ и дополнения и действуем аналогичным образом.${\ displaystyle {x_ {1}, \ dots, x_ {n}}}$

Например, следующие два из восьми maxterms трех переменных:

а + Ь ′ + с

а '+ Ь + с

Снова имеется 2 ⁿ maxterm от n переменных, поскольку переменная в выражении maxterm также может быть либо в своей прямой, либо в дополненной форме - два варианта для каждой переменной.

Индексирование maxterms [ править ]

Каждому maxterm назначается индекс, основанный на противоположном традиционном двоичном кодировании, используемом для minterms. Соглашение maxterm присваивает значение 0 прямой форме и 1 - дополнительной форме . Например, мы присваиваем maxterm (110) индекс 6 и обозначаем maxterm как M ₆ . Точно так же M ₀ этих трех переменных равно (000), а M ₇ равно (111).${\ displaystyle (x_ {i})}$${\ Displaystyle (х '_ {я})}$${\ displaystyle a '+ b' + c}$${\ displaystyle a + b + c}$${\ displaystyle a '+ b' + c '}$

Функциональная эквивалентность [ править ]

Очевидно, что maxterm n дает ложное значение (т. Е. 0) только для одной комбинации входных переменных. Например, maxterm 5, a ′ + b + c ′, является ложным только тогда, когда a и c оба являются истинными, а b - ложным - расположение входных данных, где a = 1, b = 0, c = 1, приводит к 0.

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

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

${\ displaystyle 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 комбинаций трех переменных будут соответствовать таблице.

Дуализация [ править ]

Дополнением minterm является соответствующий maxterm. В этом легко убедиться, используя закон де Моргана . Например:${\displaystyle M_{5}=a'+b+c'=(ab'c)'=m_{5}'}$

Неканонические формы PoS и SoP [ править ]

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

имеет каноническое представление minterm: , но она имеет эквивалентную упрощенную форму: . В этом тривиальном примере это очевидно , но в упрощенной форме меньше терминов продукта и меньше переменных.${\displaystyle f=a'bc+abc}$${\displaystyle f=bc}$${\displaystyle bc=a'bc+abc}$

Наиболее упрощенное представление функции SoP называется минимальной формой SoP .

Аналогичным образом каноническая форма maxterm может иметь упрощенную форму PoS.

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

Минимальные формы PoS и SoP важны для поиска оптимальных реализаций логических функций и минимизации логических схем.

Пример применения [ править ]

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

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

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

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

Канонические и неканонические последствия ворот NOR [ править ]

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

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

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

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

В приведенном выше примере maxterm мы написали, но чтобы выполнить это с 4-входным вентилем ИЛИ-НЕ, нам нужно заметить равенство ИЛИ-ИЛИ тех же самых 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 , потому что они статичны на протяжении всего сложения и, таким образом, обычно удерживаются в схемах защелок, которые обычно имеют как прямой, так и дополнительный выходы. (Простейшая схема защелки, состоящая из вентилей ИЛИ-НЕ, представляет собой пару вентилей, перекрестно связанных, чтобы образовать триггер: выход каждого соединен как один из входов с другим.) Также нет необходимости создавать форму дополнения суммы u. Однако перенос одной битовой позиции должен передаваться как перенос в следующую битовую позицию как в прямой, так и в дополнительной форме. Самый простой способ сделать это - пропустить co через вентиль ИЛИ-НЕ с 1 входом и пометить выход co ', но это добавит задержку гейта в худшем из возможных мест, замедляя колебание переносов справа налево. Дополнительный вентиль ИЛИ-НЕ с четырьмя входами, создающий каноническую форму 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 в указанные функции. Логический элемент ИЛИ-НЕ превращается в логический элемент ИЛИ, пропуская его выход через вентиль ИЛИ-НЕ с 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 значительно быстрее. Сравнение разветвлений представлено в виде таблицы:

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

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

Чтобы увидеть, как логика логического элемента ИЛИ-НЕ использовалась в ALU управляющего компьютера Apollo, посетите http://klabs.org/history/ech/agc_schematics/index.htm , выберите любую из записей 4-БИТНОГО МОДУЛЯ в Указателе чертежей и разверните изображения по желанию.

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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

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