Способы минимизации логических функций

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

4.2.3.1. Для получения ДНФ (КНФ) все единицы (нули) объединяются в прямоугольные контуры, не содержащие внутри нулей (единиц), с числом клеток в контуре , где n = 0, 1, 2, 3,...

4.2.3.2. Контур проводится через соседние клетки, т.е. клетки, отличающие значением только одной переменной.

4.2.3.3. Контуры могут частично накладываться друг на друга и должны иметь максимальные возможные размеры.

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

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

4.2.3.6. ДНФ получается в виде суммы значений всех единичных контуров.

4.2.3.7. КНФ получается в виде произведения значений всех нулевых контуров.

Таблица 4.3

Законы (правила преобразования) алгебры логики

Логические формулы Закон
a b = b a ; a + b = b + a Переместительный
( a + b ) c = a c + b c Распределительный
( a + c ) ( b + c ) = a b + c Распределительный
a.a = a ; a + a = a Повторения
a .1 = a ; a + 1 = 1 Множества
Дополнения
де Моргана
де Моргана
Склеивания

 

ПРИМЕР 2: Минимизировать карту Карно, приведенную на рис.4.2.

 

Рис.4.2 Карта Карно с единичными и нулевыми контурами

Анализ единичных контуров дает следующее выражение для ДНФ

(4.3)

/

контур 1 контур 2

Анализ нулевых контуров дает следующее выражение для КНФ

(4.4)

/

контур 3 контур 4