Минимизация логических функций (уменьшение числа букв в логической формуле) необходима для реализации функции минимальным числом логических элементов. Минимизация осуществляется путем преобразования логической формулы по правилам, приведенным в табл.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