9.5. МИНИМИЗАЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ

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

Задача минимизации систем булевых функций хорошо исследована в классе функционально полных систем: «дизъюнкция», «конъюнкция», «отрицание». Рассмотрим один из наиболее распространенных методов минимизации.

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

Все различные элементарные конъюнкции системы функций объединим в множество А, которое назовем полным множеством элементарных конъюнкций системы функций. В нашем случае Сумма рангов (число букв) элементарных конъюнкций множества А является удобным критерием оценки сложности заданной системы булевых функций.

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

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

Таблица 9.45

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

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

Пусть система булевых функций задана таблицей истинности (табл. 9.45). Найдем минимальную ДНФ системы булевых функций.

Представим каждую из функций системы в СДНФ;

1. Построим полное множество А элементарных конъюнкций полу ченной системы, приписывая каждой конституенте единицы признак вхождения в функции

2. Построим СДНФ функции

Для удобства выполнения склеивания пронумеруем каждую конституенту единицы из СДНФ функции и выполним все склеивания;

Таблица 9.46

После проведения всех поглощений, с учетом признака каждой конъюнкции, получим

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

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

В соответствии с этим имеем

Выделив для функции импликанты с признаком, включающим получим следующую минимальную дизъюнктивную нормальную форму системы функций:

К недостаткам изложенного метода следует отнести большую трудоемкость проведения операций склеивания и поглощения с признаками.