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

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

«Программа работы» «Основные функции» «Содержание»

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

Таблица 5.2

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

Логические формулы	Закон
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	Множества
	Дополнения
	де Моргана
	де Моргана
	Склеивания

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

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

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

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

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

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

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

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