4.7. Минимизация функций алгебры логики

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

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

Рис. 4.7.1. Диаграммы Вейча для функций 2-х, 3-х и 4-х переменных

Каждой клетке диаграммы соответствует определенная конситуэнта единицы. Метод минимизации с помощью диаграмм Вейча заключается в следующем. Конституэнты единицы, входящие в СДНФ булевой функции, заносятся в соответствующие клетки диаграммы. Удобно наличие соответствующей конституэнты единицы изображать в клетке диаграммы цифрой 1, а отсутствие - 0. Все диаграммы построены таким образом, что рядом расположенные единицы по горизонтали или вертикали соответствуют конституэнтам единицы, склеивающимися между собой в соответствии с законом об исключенном третьем (склеивании). Одну и ту же конституэнту единицы можно использовать для склеивания с несколькими другими конституэнтами единицы с целью получения наиболее простого окончательного выражения. Цель всех операций - получить как можно меньшее число прямоугольников (в том числе квадратов), чтобы число членов СДНФ уменьшилось, получив в итоге МДНФ.

Формировать прямоугольники можно только при включении в них хотя бы одного нового члена, в том числе используя и склеивание путем замыкания крайних ребер в «бочку». На рис. 4.7.2 приведены некоторые правила склеивания конституэнт единицы для функций 2-х и 3-х переменных.

Рис. 4.7.2. Примеры для иллюстрации правил склеивания

Для переключательных функций 3-х переменных диаграмма представляет как бы развертку цилиндра, разрезанного по , и поэтому единицы, расположенные по краям таблицы (например, как это изображено на рис.(4.7.1.)) считаются расположенными рядом.

Метод минимизации с помощью диаграмм Вейча включает в себя следующие шаги:

1. производиться занесение в соответствующую диаграмму конституэнт единицы, входящих в СДНФ минимизируемой функции;

2. используя приведенные выше правила склеивания, находят простые импликанты функций (простой импликантой называется некоторая конъюнкция, полученная в результате склеивания конституэнт единицы, не участвующая в склеивании ни с одной другой из конъюнкций);

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

В качестве примера найдем МДНФ функции, заданной табл. 4.5. Диаграмма Вейча этой функции представлена на рис. 4.7.3.

Рис. 4.7.3. Пример минимизации функции, заданной таблицей

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

Рис. 4.7.4. Карты Карно для функций 3-х и 4-х переменных

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