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

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

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

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

.

Запишем комплекс для всей системы в одном массиве, при этом отметим номера функций, к которым принадлежит тот или иной 0-куб.

0 0 0 1 2 3

0 0 1 1

0 1 0 1 2

1 0 0 3

0 1 1 1 2 3

1 0 1 2 3

1 1 0 2

1 1 1 1 2 3

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

Здесь, например 0-кубы 001(1) и 101(2,3) образуют импликанту х01() с пустым множеством соответствующих функций, поэтому импликанта не вносится в результирующий комплекс.

 

 

0 0 х 1

0 х 0 1 2

х 0 0 3

0 х 1 1

0 1 х 1 2

х 1 0 2

1 0 х 3

х 1 1 1 2 3

1 х 1 2 3

1 1 х 2

 

0 0 0 1 2 3

0 х 0 1 2

х 0 0 3

Покрытие

0 1 х 1 2

1 0 х 3

х 1 1 1 2 3

1 х 1 2 3

0 х х 1

х 1 х 2

Построим таблицу покрытий, с учетом принадлежности 0-кубов к соответствующим функциям (табл. 5.5).

 

Таблица 5.5

 

000 1 2 3

Ù

0x0 1 2

Ù

x00 3

01x 1 2

10x 3

Ú

x11 1 2 3

1

1

Ú

1x1 2 3

1

Ú

0xx 1

1

Ú

x1x 2

1

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

 

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

Далее выберем импликанты х00(3) и 0х0(1,2), покрывающие всю остальную часть таблицы, пометим их знаком “Ù”, а столбцы, покрываемые данной импликантой, пометим “+” во второй строке под таблицей. Таким образом:

 

0 х 0 1 2

х 0 0 3

х 1 1 1 2 3

1 х 1 2 3

0 х х 1

х 1 х 2

 

Отсюда запишем покрытия для каждой функции в отдельности:

 

;

;

.

 

Выполнив поглощения в каждой группе, запишем минимальные покрытия:

 

;

;

.

 

Запишем выражения в виде сокращенной ДНФ:

 

;

;

 

Вопросы для самоконтроля

1. Различными способами минимизировать булеву функцию от четырех аргументов, описывающую работу порогового элемента с порогом: а)T=2, б)Т=3. Пороговый элемент срабатывает (устанавливается в истинное значение), если число истинных значений аргументов больше или равно значению порога.

2. Минимизировать систему двух булевых функций от трех переменных, описывающую работу секции сумматора (входные переменные: разряд первого операнда (a_i), разряд второго операнда (b_i), перенос из предыдущей секции (p_i-1); функции: разряд суммы (s_i), перенос в следующую секцию (p_i)).

3. Минимизировать систему четырех булевых функций от четырех переменных дешифратора, осуществляющего перевод из двоичного кода в D-код (8421).