4.3. Минимизация логических функций

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

Смежными называют те минтермы, которые отличаются формой вхождения только одного аргумента ( и ). При склеивании по ИЛИ в результате исчезает этот элемент (X3). Результат склеивания называется импликантой . При склеивании импликант первого уровня получим более короткие импликанты второго уровня и т.д. Таким образом, в результате склеивания 2^m соседних минтермов получаем импликанту, которая не зависит от m переменных. Импликанты, которые не поддаются склеиванию, называют простыми. Из минтермов, не имеющих соседних, и простых минтермов получается сокращенная ДНФ. Некоторые импликанты в ней могут быть избыточными. В результате удаления этих импликант получают тупиковую ДНФ (несколько вариантов).

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

Метод Карно-Вейча

Карты Карно – прямоугольные таблицы, состоящие из 2ⁿ клеток, где n – число переменных. Каждая клетка соответствует уникальному набору переменных и заполняется соответствующим значением функции. Соседние клетки должны соответствовать соседним минтермам.

Для склеивания минтермов следует объединять их так, чтобы охватить всю совокупность единичных ячеек минимальным числом импликант.

Следует иметь в виду, что:

1. можно включать одну клетку в несколько импликант;

2. смежными являются клетки на противоположных краях таблицы;

3. объединять можно только 2^К клеток, где К – целое;

4. объединение надо начинать с клеток, у которых соседняя только одна единичная клетка.

П ример_2.

X0	X1	X2	X3	f	X0	X1	X2	X3	f
0	0	0	0	1	1	0	0	0	1
0	0	0	1	0	1	0	0	1	0
0	0	1	0	1	1	0	1	0	1
0	0	1	1	1	1	0	1	1	1
0	1	0	0	0	1	1	0	0	0
0	1	0	1	1	1	1	0	1	1
0	1	1	0	1	1	1	1	0	Результат 1
0	1	1	1	1	1	1	1	1	1

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

Пример 3

X0	X1	X2	X3	f	X0	X1	X2	X3	f
0	0	0	0	0	1	0	0	0	1
0	0	0	1	Ф	1	0	0	1	Ф
0	0	1	0	0	1	0	1	0	1
0	0	1	1	1	1	0	1	1	0
0	1	0	0	1	1	1	0	0	Ф
0	1	0	1	Ф	1	1	0	1	Ф
0	1	1	0	0	1	1	1	0	1
0	1	1	1	1	1	1	1	1	0

Результат

В то же время задача разработки электрических схем комбинационных устройств состоит не в минимизации логических функций по числу вхождений аргументов, а в том, чтобы реализовать каждую из функций с минимальным количеством и разнообразием микросхем (минимальный элементный базис). С целью унификации элементной базы не следует вводить дополнительных микросхем для выполнения простых функций, если в уже установленных микросхемах есть неиспользуемые логические элементы, выполняющие более сложные функции. В частности, элементы с инвертированием можно использовать как инверторы, объединяя входы таких элементов. Например, функцию удобно реализовывать на одной микросхеме ЛА3, используя один элемент для инвертирования Х₁, второй – для логического умножения с инвертированием, третий – для повторного инвертирования результата . Для выражений вида Y_K = M_AVM_BVM_C, где M_A, M_B, M_C – три минтерма (конъюнктивных выражения), удобно использовать преобразование (M_AVM_B)V(M_AVM_C), где в качестве M_A следует выбрать тот из минтермов, который позволит оптимально упростить обе скобки (вынести общие множители). В скобках должны остаться функции неравнозначности, эквивалентности, импликации, которые затем следует выразить так, чтобы их можно было реализовать в минимальном элементном базисе (см. /2/).

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