Канонические формы булевых функций

Введение

Стандартные формы булевых функций

В булевой алгебре любая булевая функция может быть выражена в канонической дизъюнктивной нормальной форме (CDNF) или канонической форме минтермов, а также в ее двойственной форме – канонической конъюнктивной нормальной форме (CCNF) или канонической форме макстермов. Другие канонические формы включают полную сумму простых импликантов или каноническую форму Блейка (и ее двойственную), и алгебраическую нормальную форму (также называемую формой Жегалкина или Рида — Мюллера). Минтермы называются произведениями, поскольку они представляют собой логическое И (AND) набора переменных, а макстермы называются суммами, поскольку они представляют собой логическое ИЛИ (OR) набора переменных. Эти понятия двойственны из-за их взаимодополняющей симметрии, выраженной законами Де Моргана. Две двойственные канонические формы любой булевой функции – это "сумма минтермов" и "произведение макстермов". Термин "Сумма произведений" (SoP или SOP) широко используется для канонической формы, которая является дизъюнкцией (ИЛИ) минтермов. Ее двойственная форма по Де Моргану – "Произведение сумм" (PoS или POS) для канонической формы, которая является конъюнкцией (И) макстермов. Эти формы могут быть полезны для упрощения функций, что имеет большое значение в оптимизации булевых формул в целом и цифровых схем в частности.

Минтермы

Для булевой функции от *n* переменных, произведением, в котором каждая из *n* переменных встречается ровно один раз (либо в прямой, либо в инвертированной форме), называется минтерм. Таким образом, минтерм – это логическое выражение от *n* переменных, использующее только операцию инверсии и операцию конъюнкции. Например, *x₁x₂'*, *x₁'x₂* и *x₁'x₂'* – это три примера из восьми минтермов для булевой функции от трех переменных *x₁*, *x₂* и *x₃*. Обычно последний из них читается как "a И b И НЕ c".

Всего существует 2<sup>*n*</sup> минтермов для *n* переменных, поскольку каждая переменная в выражении минтерма может быть либо в прямой, либо в инвертированной форме – два варианта для каждой переменной.

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

Минтермы часто нумеруются с помощью бинарного кодирования схемы инверсии переменных, где переменные записываются в стандартном порядке, обычно в алфавитном порядке. Эта конвенция присваивает значение 1 прямой форме и 0 инвертированной форме; тогда минтерм равен . Например, минтерм пронумерован 110₂ = 6₁₀ и обозначается .

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

Каждому макситерму присваивается индекс, основанный на обратном стандартном двоичном кодировании, используемом для минтермов. В соглашении для макситермов значение 0 соответствует прямой форме, а значение 1 – инвертированной форме. Например, мы присваиваем индекс 6 макситерму (110) и обозначаем его как M6. Аналогично, M0 для этих трех переменных равен (000), а M7 равен (111).

Дуализация

Дополнением миниметра является соответствующий максиметр. Это легко проверить, используя закон де Моргана. Например:

Пример применения

Приведенные выше примеры таблиц истинности для минтермов и макситермов достаточны для установления канонической формы для однобитной позиции при сложении двоичных чисел, но недостаточны для проектирования цифровой логики, если в вашем наборе логических элементов отсутствуют элементы AND и OR. Когда производительность критична (как в компьютере Apollo Guidance Computer), доступные компоненты, скорее всего, будут NAND и NOR из-за инвертирующего действия, присущего транзисторной логике. Значения определяются как уровни напряжения, один близкий к нулю, а другой – к напряжению питания Vcc, например, +5 В постоянного тока. Если более высокое напряжение определено как логическая "истина" (1), то NOR-элемент является самым простым полезным логическим элементом. В частности, 3-входной NOR-элемент может состоять из трех биполярных транзисторов с общим заземленным эмиттером, соединенными коллекторами и подключенными к Vcc через нагрузочный импеданс. Каждая база подключена к входному сигналу, а общая точка коллекторов представляет выходной сигнал. Любой вход, находящийся в состоянии "1" (высокое напряжение), закорачивает эмиттер и коллектор соответствующего транзистора, вызывая протекание тока через нагрузочный импеданс, что опускает напряжение на коллекторе (выходе) почти до нуля. Этот результат не зависит от других входов. Только когда все три входных сигнала находятся в состоянии "0" (низкое напряжение), сопротивление между эмиттером и коллектором всех трех транзисторов остается высоким. В этом случае ток протекает незначительно, и делитель напряжения, образованный нагрузочным импедансом, устанавливает на коллекторах высокое напряжение, близкое к Vcc. Инвертирующее свойство этих логических схем может показаться недостатком при реализации функции в канонической форме, но есть компенсирующий эффект: NOR-элемент с одним входом реализует функцию инвертирования, которая часто требуется в цифровой логике. В данном примере предполагается, что в распоряжении разработчиков Apollo были только 3-входные NOR-элементы, однако для упрощения обсуждения будем считать, что доступны и 4-входные NOR-элементы (в Apollo они собирались из пар 3-входных NOR-элементов).

The sample truth tables for minterms and maxterms above are sufficient to establish the canonical form for a single bit position in the addition of binary numbers, but are not sufficient to design the digital logic unless your inventory of gates includes AND and OR. Where performance is an issue (as in the Apollo Guidance Computer), the available parts are more likely to be NAND and NOR because of the complementing action inherent in transistor logic. The values are defined as voltage states, one near ground and one near the DC supply voltage Vcc, e. g. +5 VDC. If the higher voltage is defined as the 1 "true" value, a NOR gate is the simplest possible useful logical element. Specifically, a 3 input NOR gate may consist of 3 bipolar junction transistors with their emitters all grounded, their collectors tied together and linked to Vcc through a load impedance. Each base is connected to an input signal, and the common collector point presents the output signal. Any input that is a 1 (high voltage) to its base shorts its transistor's emitter to its collector, causing current to flow through the load impedance, which brings the collector voltage (the output) very near to ground. That result is independent of the other inputs. Only when all 3 input signals are 0 (low voltage) do the emitter collector impedances of all 3 transistors remain very high. Then very little current flows, and the voltage divider effect with the load impedance imposes on the collector point a high voltage very near to Vcc. The complementing property of these gate circuits may seem like a drawback when trying to implement a function in canonical form, but there is a compensating bonus: such a gate with only one input implements the complementing function, which is required frequently in digital logic. This example assumes the Apollo parts inventory: 3 input NOR gates only, but the discussion is simplified by supposing that 4 input NOR gates are also available (in Apollo, those were compounded out of pairs of 3 input NORs).

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

Одним из применений булевой алгебры является проектирование цифровых схем, с целью минимизации количества логических элементов и времени установления. Существует шестнадцать возможных функций двух переменных, но в аппаратном обеспечении цифровой логики простейшие схемы реализуют только четыре из них: конъюнкция (AND), дизъюнкция (ИЛИ), и соответствующие им инверсии (NAND и NOR). Большинство логических элементов принимают более двух входных переменных; например, бортовой компьютер Apollo Guidance Computer, который стал пионером в применении интегральных схем в 1960-х годах, был построен только на одном типе элемента – трехвходном NOR, выход которого истинен только при ложных значениях всех трех входов.