1.10. Минимизация переключательных функций

Физическое устройство, реализующее одну из основных операций алгебры логики или простейшую переключательную функцию, называется логическим элементом (ЛЭ). Схема, составленная из конечного числа ЛЭ по определенным правилам (см. § 2.3), называется логической схемой (ЛС). Если ЛС полностью описывается переключательными функциями (одной или несколькими), то она называется комбинационной схемой (КС).

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

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

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

Два минтерма будем называть соседними, если они различаются только одним первичным термом т.е., если для одного из минтермов а для другого (все же остальные первичные термы одинаковые). Так, например, если то минтермы являются соседними, так как они различаются только одним первичным термом Для минтерма соседними будут также минтермы Понятно, что каждый минтерм переменных имеет по соседних из общего числа минтермов.

Рассмотрим контерм переменных не зависящий от одной переменной т. е. случай, когда контерм является конъюнкцией -го первичного терма. Данный контерм можно представить в СДНФ:

где Очевидно, что полученные минтермы являются соседними, так как они различаются только одним первичным термом

Отсюда следует правило минимизации: дизъюнкцию двух соседних минтермов можно заменить одним контермом, не зависящим от одной переменной.

Пусть контерм переменных не зависит от двух переменных Выполним тождественные преобразования контерма для его представления в СДНФ:

где Из этих соотношений видно, что каждый из четырех полученных минтермов

имеет среди остальных по два соседних.

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

Рассмотрим пример. В § 1.9 было показано, что контерм трех переменных т. е. данный контерм является вырожденной функцией, независящей от двух переменных и Тогда легко показать, что

где каждый минтерм имеет по два соседних.

Продолжив вышеприведенные рассуждения дальше, можно установить общее правило минимизации: одним контермом переменных не зависящим от переменных можно заменить дизъюнкцию минтермов, если каждый из них имеет по соседних среди остальных минтермов.

Если контерм не зависит от m переменных, то принято говорить, что он покрывает минтермов. На этом свойстве контермов и основывается минимизация функций заданных в СДНФ, которая в соответствии с выражением (1.72) представляет собой дизъюнкцию некоторого числа минтермов А:

и

Заменив в данном выражении дизъюнкцию минтермов в случаях, когда какие-либо минтермы не имеют ни одного соседнего) соответствующими контермами функцию можно представить в виде дизъюнкции некоторого числа контермов, покрывающих все минтермы входящие в СДНФ функции:

Такая форма представления функций называется дизъюнктивной нормальной формой (ДНФ). Если ДНФ содержит минимально возможное число первичных термов то она называется минимальной дизъюнктивной нормальной формой (МДНФ). Следует отметить, что любые правила минимизации

сводятся к сформулированному выше общему правилу, в то время как алгоритмы (методы) минимизации могут сильно различаться между собой.

На основании идемпотентных законов один и тот же мин-терм входящий в СДНФ, может использоваться несколько раз для образования различных контермов так как

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

Рассмотрим пример. Пусть задана СДНФ функции трех переменных

Здесь для получения МДНФ минтерм необходимо использовать три раза:

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

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

Пусть получена МДНФ некоторой функции Тогда, используя закон двойного отрицания и закон двойственности, будем иметь:

Это соотношение и дает минимальную нормальную форму в базисе И-НЕ функции так как для ее реализации требуются только операции И-НЕ. В качестве примера запишем в

базисе И-НЕ МНФ функции трех переменных, МДНФ которой была найдена выше:

Конъюнкция любого числа дизтермов называется конъюнктивной нормальной формой. Получение минимальной конъюнктивной нормальной формы (МКНФ) функции легко сводится к получению МДНФ инверсной функции и преобразованию ее с помощью закона двойственности:

где дизъюнктивные термы (1.78).

Рассмотрим пример. Пусть требуется найти МКНФ функции трех переменных значения которой равны 0 только в точках и . СДНФ инверсной функции

Используя минтерм дважды, легко показать, что МДНФ (1.81) инверсной функции Тогда МКНФ функции получается с помощью закона двойственности:

Минимальная нормальная форма в базисе ИЛИ-НЕ функции может быть получена непосредственно из МКНФ (1.82) с помощью закона двойного отрицания и закона двойственности:

Найдем МНФ в базисе ИЛИ-НЕ для функции рассмотренной в предыдущем примере:

Таким образом, получение МКНФ и МНФ в базисах И-НЕ и ИЛИ-НЕ функции всегда можно свести к получению МДНФ либо функции либо ее инверсии Это позволяет использовать для всех нормальных минимальных форм представления переключательных функций только метод их минимизации, приводящий к получению МДНФ.