Минимизация частично определенных булевых функций

При минимизации частично определенных булевых функций в клетки карты Карно, соответствующие наборам аргументов, на которых функция не определена, ставится символ d (don’t care). Эти наборы используются для построения кубов возможно большей размерности, в результате чего уменьшается цена покрытия функции.

Определим минимальную ДНФ функций, используемых для построения комбинационной схемы, в которой выполняется операция суммирования двоичных кодов по mod 3: у₁у₂ = (а₁а₂ + b₁b₂)_{mod 3}.

Предполагается, что слагаемые имеют значения а₁а₂ £ 2; b₁b₂ £ 2, т.е. наборы а₁а₂ = 11 и b₁b₂ = 11 отсутствуют и рассматриваются как несущественные. Таблицы истинности для функций

y₁ = f₁(a₁,a₂,b₁,b₂); y₂ = f₂(a₁,a₂,b₁,b₂)

представлены на рис. 6 в виде карт Карно. На картах нулевые значения y₁ и y₂ обозначены 0, единичные – 1, несущественные – знаком d.

а)	б)

Рис. 6. Минимизация частично определенных булевых функций.

С использованием несущественных вершин определяются минимальные покрытия:

001X 00X1

C(y₁) = 1X00 ; C(y₂) = X100

X1X1 1X1X

с ценами S^а = 8 каждое, которым соответствуют минимальные ДНФ:

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

В качестве примера использования карт Карно для определения минимальных ДНФ и КНФ функций рассмотрим функцию, представленную на картах рис. 7,а, б.

а)	б)

Рис. 7. Определение минимальных ДНФ (а) и КНФ (б) функции.

Данной функции соответствует минимальная ДНФ (рис. 7, а) вида:

Нахождение нулевого покрытия этой функции представлено на рис. 7, б. Минимальная КНФ:

Для минимизации функций от пяти и шести переменных используются соответственно две и четыре четырехмерные карты Карно.

Пример использования карт Карно для минимизации функции пяти переменных f = Ú (0,1,8,10,13,15,16,17,22,23,29,30,31) приведен на рис. 8.

Рис. 8. Минимизация булевой функции от пяти переменных.

Функции f с ценой S^а = 65

соответствует минимальное покрытие

с ценой S^а = 13.

Принцип размещения карт для представления функций шести переменных показан на рис. 9. На этом рисунке представлена функция от шести переменных, заданная комплексом

с ценой S^а = 48.

Ее минимальное покрытие имеет цену S^а = 8.

При минимизации функций от большого числа переменных карты Карно неудобны, в этом случае для решения задач минимизации используются алгебраические методы. Минимальным ДНФ и КНФ функций соответствуют минимальные двухуровневые логические схемы.

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

Рис. 9. Карты Карно функции шести переменных.

Так, булевой функции

f(x₁,x₂,x₃,x₄,x₅) = Ú (5,6,7,13,14,15,21,22,23,25,26,27,29,30,31)

соответствует минимальная ДНФ: f = x₃x₄ Ú x₃x₅Ú x₁x₂x₄ Ú x₁x₂x₅,

по которой строится двухуровневая логическая схема (рис. 10, а) с ценой

S^b = 14. Минимальная ДНФ преобразуется в скобочную форму:

f = (x₁x₂ Ú x₃)x₄ Ú (x₁x₂ Ú x₃)x₅ = (x₁x₂ Ú x₃) (x₄ Ú x₅),

по которой строится схема (рис. 10, б) с ценой S^b = 8.

Рис. 10. Схема, построенная по МДНФ (а) и по скобочной форме (б).